I have previously worked out a solution to Nim which is a simple game of strategy.
The game is played by two players who each take turns to pick up matches from two separate piles. The rules allow a player to take any number of matches from one of the piles when it is their turn. The winner is the player that takes the last match. This post explains the winning strategy.
This version of Nim is quite easy to work out the correct strategy for but there are versions where things get more difficult.
What about a game where there is one pile of matches and the first player can take can any number of matches up to one less than the total. For moves after that each player can only take a number of matches that is less than, or equal to, the number that was taken by the other player in their previous turn.
So if player one takes two matches then player two can take one or two. If player two then takes one, then player one can only take one match in their next turn. Each turn from then on will be to take only a single match.
If there are an odd number of matches in the pile then the solution is easy. Player one takes one match which leaves an even number of matches. Player two is only allowed to take one match since they cannot take more than their opponent took on the previous turn. This leaves an odd number of matches again. This game continues until player one take the final match and wins.
So the more interesting case is when there is an even number of matches in the pile. No player wants to leave an odd number of matches in the pile otherwise the other player will just take one and then each player will only be able to take one match each turn until the player that left an odd number of matches in the pile loses. This means that we know that player one’s first move must be to take an even number of matches, and he must take fewer than half the matches. If he takes more than half then player two will simply take all the remaining matches to win.
Looking at some examples should start to show the pattern.
We know that player one wins if there are an odd number of matches. Looking at the even numbers:
Start with 2 – player one must take one, player two then takes the last one to win. Player two wins
Start with 4 – player one loses if he takes an odd number so he must take two, player two then takes the final two and wins. Player two wins
Start with 6 – player one must take two to have a chance as it is the only even number less than half of six. This leaves four and is the case above, player two can take one or two and either way they lose. Player one wins
Start with 8 – player one must take two again which gives the same as starting with six but with player two to play so: Player two wins.
Start with 10 – If player one takes four then six are left and, as above, player two wins. But if player one takes two then eight are left, following the logic above, Player one wins.
Start with 12 – Player one takes four and will win. Player one wins
Start with 14 – Player one takes six and will win. Player one wins
Start with 16 – Player one cannot bring the number down to eight again otherwise player two will take all the eight remaining matches and win. Player one must take a number less than eight, we know that odd numbers will lose, and taking two, four or six leaves the cases above for 10,12 and 14 but we know that whoever goes first with a pile of 10, 12 or 14 will win, so Player two wins
We can now see the pattern and the strategy
Player two wins when the pile contains a number of matches that is a power of two (2, 4, 8, 16, etc) and player one wins otherwise. The winning strategy is to reduce the pile to a power of two that is more than half the remaining pile.
More complicated games can still be worked out by working up from the simplest cases.