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?
Before I begin on the four man game, first consider the two man game. If a player puts a man on step 0, the other player wins by placing the other man on step 1. Similarily, if a player puts a man on step 1, the other player wins by placing the other man on step 0. Therefore whoever is first to force their opponent to put a man on step 0 or 1 wins.
The first to put a man on 2 or 3 will lose since the opponent can take the other of 2 or 3, thereby forcing the first player to move to 0 or 1.
The general strategy for the two man game is to create a couple on steps (0,1), (2,3), (4,5), ..., (2n, 2n+1), ... etc. If the game started as {9,16} then the winning move is to move 16 to 8.
The three man game is just like the four man game with a man on step 0 and the others shifted up by one step. The three man game {2,4,7}, it is equivalent to the four man game {0,3,5,8}
The four man game breaks into three cases:
1) There are two couples. This is essentially two two-man games played simultaneously.
2) There is one couple. The player will want to reduce the game to case 1.
3) There are no couples. The player will want to keep it this way to force the opponent to make the first couple.
We can plan case 3 by using a recursion. We will zoom out and view two steps as one. The case 3 game X{1,4,7,11} becomes Y{0,2,3,5}. In game Y, the winning move is moving 5 to 1. So we will want to move X5 to X2 or X3, but which one?
When we zoomed out, we lost some detail, that detail is whether the original game's men were on even or odd steps. We want to keep the number of odd steps to an even number. That way if the opponent moves within a couple (1 to 0 or 7 to 6), we can respond with an identical kind of move.
In game X there were three odd steps (1,7,11), so we will want to choose 11 to 2 over 11 to 3 to make the number of odd steps even.
Sometimes the recursion will show us two couples at the higher level. Consider X{1,3,9,10} (9,10 is not a couple). The recursion gives Y{0,1,4,5}. The two couples are (0,1) and (4,5).
The player will want to keep the couples as they are, so we will make a move within a single element of a couple. The odd men in game X are 1, 3, and 9. Our move is to move one of those down by one. Note this is a winning move because there are three odd steps. If there were only two odd steps like in game {1,3,8,10}, there would be no winning move due to parity.
Sometimes multiple recursions are necessary. One such example is game A{5,12,33,43}. The first recursion gives B{2,6,16,21}, the second gives us C{1,3,8,10} and finally the third gives us D{0,1,4,5}. D has two couples, so we want to keep it as two couples and move within the scope of a single step on D.
A has three odd steps, an adjustment of 1 is needed. B has one odd step, an adjustment of 2 is needed. C has two odd steps, an adjustment of 4 is NOT needed. We need to find which of the steps in A satisfies (n nim 3) mod 8 = 0. n=43 works so the move is 43 to 40.
Another example is game A{3,18,29,41} Then we have B{1,9,14,20}, C{0,4,7,10} and D{0,2,3,5}. Clearly from game D, we need to move from 5 to 1. This entails moving 41 to some value in the range 8 to 15 (D1 covers A8 to A15).
A has three odd steps, B has two odd steps, and C has one odd step. An adjustment of 1+0+4=5 mod 8 is needed. (41 nim 5) mod 8 = 4 and 12 mod 8 = 4, so our move is 41 to 12.
Four man game
