Consider the following scenario:
- 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).
- 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.
- Each builder doesn't have any knowledge about what block numbers the other builders may have, though he knows how many.
- 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.
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?