Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the following scenario:

  1. We have a number of sequential building blocks (e.g. 12 building blocks, ordered from 1 to 12), distributed randomly (but not necessarily equally) on a number of builders (e.g. 3 builders).
  2. The builders are required to work in order and start building the wall from block number 4, both ways; down to block number 1 or up to block 12.
  3. Each builder doesn't have any knowledge about what block numbers the other builders may have, though he knows how many.
  4. Builders must try to finish first by preventing others from making their moves. They should not pass and have to place a block, if they can. Any builder who finishes all his blocks first will be granted the highest reward, then the second, and so on...

Can we predict who will finish first, second and last? Is there any algorithm the builders should follow to get their work done first?

The following is a practical example of the problem:

Let us say:

builder 1 has: b2 b5 b8 b9
builder 2 has: b1 b11
builder 3 has: b3 b4 b6 b7 b10 b12

builder 1, and builder 2 will have to wait for builder 3 to place b4.

builder 3 will place b4, and gives his place back to builder 1.

wall: b4

builder 1 will have to put up b5, as there are no other options for him.

wall: b4 b5

builder 2 will follow, but he cant place his blocks, he will have to wait for b2 or b10.

builder 3 now have two options: b3 or b6, he must choose the one which help him finish first.

wall: b4 b5 b6

builder 1 has nothing to do, he'll pass his turn to builder 2.

builder 2 is still waiting for the installation of b2 or b10.

builder 3 will have to place b7.

wall: b4 b5 b6 b7

builder 1 now will place b8.

wall: b4 b5 b6 b7 b8

builder 2 is still waiting patiently...

builder 3 is forced to put down b3, as there are no other options, he was hoping that builder 2 may place b9... but his hope faded!

wall: b3 b4 b5 b6 b7 b8

builder 1 is totally in charge now, and feeling very happy! but he is confused! after thinking he decided that b2 may allow him to keep preventing a larger number of blocks, which in turn increases his chance.

wall: b2 b3 b4 b5 b6 b7 b8

builder 2 says: finally! some action! and places b1.

wall: b1 b2 b3 b4 b5 b6 b7 b8

builder 3 lost his hope on becoming first!

builder 1 now will install his final block and go home with the biggest reward!

wall: b1 b2 b3 b4 b5 b6 b7 b8 b9

builder 2 will wait...

builder 3 sadly places b10

builder 2 places b11 and goes home with the second reward...

Any known algorithm for solving such problems?

share|improve this question
    
I guess I understand this game, although you didn't specify if a builder may choose to pass their turn. But I don't see why it's an interesting game. I gather that "finishing" means playing all your own blocks? So if I'm dealt the hand {4}, then I win automatically? –  Theo Johnson-Freyd Feb 16 '10 at 2:10
    
If you have b1, b3-b10, and b12, then you decide who wins, but you lose. This is a common phenomenon in games with 3 or more players, and it often makes it difficult to make sense of your equity. –  Douglas Zare Feb 16 '10 at 3:30
    
Range is a simple form of the probability density function of a continuous distribution. In our case the distribution is linear, isn't it? Is there any evaluation function that I can use here? –  Noor Feb 16 '10 at 15:36
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.