There are 15 stairs arranged in a line. There are 6 people on various different steps.
The only rule is you can only move a person if you move it to any lower vacant stair.
In a two player game, you alternate moving single people. The last one to move a person wins! What strategy should you use in order to win?
What strategy would be used if the people couldn't pass each other when moving down the stairs?
This post expands on the method described in the Four man game post.
The six man game has four possible cases:
1) There are no couples
Use the recursion technique to reduce the game to one of the three other cases.
2) There are three couples
This is similar to the four man game with two couples.
3) There are two couples
This is similar to the four man game with one couple.
4) There is one couple
To solve this case, a new technique is needed, extraction.
Extraction is creating a related game by removing the couple(s) and
splicing together the remaining parts of the game. If a man is on
a higher step than an extracted couple, he is moved down in the new
game according to the number of couples removed.
Lets use the
game A{2,6,8,9,16,21} as an example. The couple is (8,9).
Extract the couple (8,9) from the game. The new game is
B{2,6,14,19}.
Using the technique discussed in the 'Four Man Game'
post to find that the winning move in B is 19 to 18. Working from
game A to game B we find that 18 in game B is equivalent to 20 in game
A, so the winning move in game A is 21 to 20.
If we have a
larger game, the extraction strategy can be applied multiple times,
alongside recursion. Let the game be
A{2,6,14,34,56,98,100,122,156,197} The table below shows the
steps in reducing the game. The first column is a identifier for
the game, the second column is the sqeuence of reduced games and the
third column is the method used to generate that game.
A | 2,6,14,34,56,98,100,122,156,197 | Start
B | 1,3, 7,17,28,49, 50, 61, 78, 98 | Recursion
C | 0,1, 3, 8,14,24, 25, 30, 39, 49 | Recursion
D | 1, 6,12, 26, 35, 45 | Extraction
E | 0, 3, 6, 13, 17, 22 | Recursion
F | 0, 1, 3, 6, 8, 11 | Recursion
G | 1, 4, 6, 9 | Extraction
H | 0, 2, 3, 4 | Recursion
In game H it is easy to see that the winning move is 4 to 1.
Working backwards, the winning move for game A can be constructed:
H: 4 to 1
G: 9 to 3
F: 11 to 5
E: 22 to 11
D: 45 to 22
C: 49 to 26
B: 98 to 52
A: 197 to 104
A second example is A{5,25,33,43,61,63,96,101}
A | 5,25,33,43,61,63,96,101 | Start
B | 1,12,16,21,30,31,48, 50 | Recursion
C | 1,12,16,21, 46, 48 | Extraction
D | 0, 6, 8,10, 23, 24 | Recursion
E | 0, 3, 4, 5, 11, 12 | Recursion
F | 0, 3, 9, 10 | Extraction
G | 0, 1, 4, 5 | Recursion
In game G there is no winning move. So, while working backwards
through the game, we will continue to find there are no winning moves
until one of the earlier games shows a parity difference.
G: none
F: none
E: none
D: none
C: 21 to 20
B: 21 to 20
A: 43 to 40
This time a parity difference was found in game C, if we found no
parity difference in any of the games while working back, then there
would have been no winning move at all. If you are ever forced to
play when there is no winning move, I recommend moving the highest man
down one step and hope your opponent makes a mistake.
Edited on April 19, 2005, 3:42 pm
Finally, the solution for the no-passing game.
