March of the Goblins

1. Problem Statement. So, Goblins live in the underground mining town of Moria. They sleep together in one giant communal bedroom, which has a single door to the great hall.

To get to work, the bosses literally throw the sleeping goblins into the hall several at a time. We can model the hall as a lattice.

Goblins are mindless, and just go to neighboring vertices of the lattice with fewer goblins. Time can be discrete for computational simplicity.

However, once awaken, goblins cannot go back to sleep nor return to their communal bedroom. But they can leave the mine shaft (the end of the great hall) to the surface, never to return again.

Describe the dynamics of goblins. Assume there are an infinite number of goblins sleeping in the communal bedroom.

2. So we have in this puzzle one “source” of goblins and one “sink”, namely, the vertex where goblins are added (thrown out of the bedroom) and the vertex indicating where the exit is.

We can leave the source completely random, i.e., each turn a random number of goblins are thrown out (added to a certain vertex).

The tricky bit is the goblin-dynamics. Since goblins are idiots, they don’t coordinate with each other.

Intuitively there may be the situation when the goblins are close to the exit in one giant group. So the density function would assign 0 to all the nodes except one.

Half the goblins would exit, and the other half would return down the hall. In other words: half would oscillate, half would leave.

A continuous approximation to this density function might look like 2^{-n}\sin(\mbox{something}).

3. Generalizations. Suppose there were several bedrooms, not just one. Suppose the lattice is a more complicated graph.

This problem originally was about a car engine producing exhaust (“goblins”) and how to most efficiently expel it. So you may want to modify the lattice and boundary conditions accordingly (e.g., use a source function like \lceil A\sin^{2}(\omega t)\rceil or something).


About Alex Nelson

I like math. I like programming. Most of all, I love puzzles.
This entry was posted in Puzzle and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s