The game of Static Nim (so named because the number of tokens that can be taken on each turn doesn’t change, that is, it’s static) is a two-player game with one pile. The rules of the game are as follows:
- There are n tokens arranged in a pile.
- On each turn, a player can take up to k tokens from the pile.
- The player who removes the last token wins.
For instance, the pile could contain 26 tokens, and a player can take up to 7 tokens on each turn. In such a case, the game might proceed as follows:
| Player | Number Removed | Number Remaining |
| Initial | | 26 |
| A | 4 | 22 |
| B | 3 | 19 |
| A | 7 | 12 |
| B | 4 | 8 |
| A | 2 | 6 |
| B | 6 | none |
You may wish to play this game against your students a few times so they understand the game. Do so by placing a pile of tokens on the overhead projector. Allow the students to decide if they want to go first, and then play the game according to the rules above.
You can then allow students to play the game a few times by themselves. They can play against one another, in which case you will need to distribute tokens to each pair of students. Alternatively, all students can play against the computer using the
Nim Games activity. (To play the game online, students should set the game type as Static Nim; they can then choose the initial pile size (n) and maximum move size (k). They can also decide whether the computer will use a random or optimal strategy; using the optimal strategy, the computer will win unless the student plays perfectly.)
Static Nim games are well understood, and there is a simple strategy for winning them. However, that is not to say that the strategy will be obvious to students. Quite the contrary, it may take several rounds of playing the game before students are able to figure out how to win. After the students have played the game several times on their own, require them to set the strategy to optimal (if using the online game), or allow them to play the game against you as you use the optimal strategy.
Playing to Win.The optimal strategy for Player A in this game is as follows:
- Divide n by (k + 1). The remainder is the number of tokens that Player A should take on the first move of the game. For instance, if n = 26 and k = 7, then 26 ÷ (7 + 1) = 3 R 2, so the first player should take 2 tokens on the first turn. (Note that if the remainder is 0, then Player A has no way to win unless Player B makes a mistake.)
- If Player A removed the correct number of tokens on the first turn, then the number taken by Player B on the next turn is irrelevant. Whatever number B takes (say, p), Player A should take p’, which is the complement of (k + 1). That is, Player A should take p’ tokens so that p + p’ = k + 1. The reason for taking this many is simple: no matter how many tokens Player B takes (1, 2, …, k), Player A can always take a number of tokens so that the total taken on consecutive turns by both A and B is k + 1. Continuing the example above, if B takes 3 tokens, then A should take (7 + 1) – 3 = 5 tokens. The total for those two turns is 5 + 3 = 8. (If B had taken 1, A would have taken 7; again the total is 8. If B had taken 6, A would have taken 2; again the total is 8. And so on.)
- Repeat Step 2 until Player A takes the last token.
At no point should you state the optimal strategy. Instead, play the game several times against the class using the optimal strategy, and see if any student is able to defeat you. As it may take some students longer to recognize the pattern than others, make a rule that no student is allowed to tell the strategy to another student.
After all, or at least most, students have discovered the optimal strategy, you can discuss the general process for finding the optimal strategy of Nim games.
Notation and terminology. The notation Nk(n) is used to represent a game with an initial pile size of n tokens and a maximum move size of k tokens. For instance, N4(20) means that there n = 20 tokens and that up to k = 4 tokens can be removed on each turn.
The optimal strategy for N4(20) is obtained by first noting that there are 21 positions in the game, represented by the integers 0, 1, 2, …, 20. The largest value, 20, is the initial position, and 0 is the terminal position. The sequence of positions 20 → 18 → 15 → 14 → 10 → 9 → 5 → 2 → 0, such that for each x → y, a pile of size y is obtainable from a pile of size x, is called a play of the game. Notice that there are 8 moves in this play of the game. Because 8 is an even number, the second player wins this game. In fact, any game with an even number of moves is won by the second player, and those plays with an odd number of moves are won by the first player. Thus, finding the optimal strategy is equivalent to determining whether the first player can force the game to have an odd number of moves. Alternatively, the second player would like to force the game to end after an even number of moves.
Solving a game. One approach to solving token pickup games like these is to find a handy representation for the pile sizes and an easily understood method for finding optimal moves. The following example illustrates this idea.
Consider the game N4(20) again. Notice that each position in the game v = 0, 1, 2, …, 20 can be represented in the form v = 5t + u where 0 ≤ t ≤ 4 and 0 ≤ u ≤ 4. With this in mind, for example, you could write 17 = 5t + u = 5(3) + 2. Another way to write this is in base 5 notation as 32. An alternative way to represent this is with the following notation:
|||..
Each bar represents a group of 5; each dot represents 1, so this representation is short hand for 5 + 5 + 5 + 1 + 1, which contains five summands.
Using this same representation, the numbers 5 through 13 can be written as follows:
| Number | Notation | Summands |
| 5 | | | 1 |
| 6 | |. | 2 |
| 7 | |.. | 3 |
| 8 | |... | 4 |
| 9 | |.... | 5 |
| 10 | || | 2 |
| 11 | ||. | 3 |
| 12 | ||.. | 4 |
| 13 | ||... | 5 |
If we represent the play of the game above using this notation, note that the second player reduces the number of summands on each move while the first player never does.
| 20 | → | 18 | → | 15 | → | 14 | → | 10 | → | 9 | → | 5 | → | 2 | → | 0 |
| |||| | → | |||... | → | ||| | → | ||.... | → | || | → | |.... | → | | | → | .. | → | 0 |
Notice that the number of summands changes from 4 to 6 to 3 to 6 to 2 to 5 to 1 to 2 to 0. The key to understanding the optimal strategy is to realize that one player will win if he can repeatedly reduce (or not increase) the number of summands while the other player cannot reduce (must increase) the number of summands. Of course, the player who repeatedly reduces (or leaves unchanged) the number of summands must win, because the terminal position has zero summands.
The S vs. U classification. There is a more general approach that works even when the positions cannot be represented in such a nice way. Returning to the game N4(20), note that the set P of positions can be divided into two subsets—the multiples of 5, and the others. These two subsets, S = {0, 5, 10, 15, 20} and U = {1, 2, 3, 4, 6, 7, …, 19}, are said to partition the set P of all possible positions. Using the bar-and-dot notation, consider the positions that are represented without any dots. This partition satisfies three fundamental properties:
- Every move from a position of S (one with no dots) inevitably goes to a position of U (one with some dots).
- For each position in U, there is some move that will lead to a position in S.
- The terminal position is an element of S.
Note that Player A must move from 20 (an position in S), thus leaving Player B with a position in U. Therefore, Player B can remove p’ = 5 – p (where Player A removed p) tokens to result in the position 15, which is in S. Player A must then move to another position in U, Player B can then return to S again, and so on, until Player B wins by moving to the 0 position.
Another way to look at this is to use the bar-and-dots representation. Player A cannot reduce the number of summands. For example, ||| → ||.., so that a player confronted with a pile size of 5, 10, 15, or 20 cannot reduce the number of summands, but a player confronted with a pile size that is not a multiple of 5 can reduce the number of summands.
At this point, ask the students to perform the same analysis on the game N5(20) to check for understanding.
Other Static Games. Consider the game N1,3,4(10). This is just like the previous game, but it begins with only 10 tokens, and a player can remove 1, 3, or 4 tokens on a turn. Unlike the previous game, it is not easy to find a representation for this game.
Students should play this game several times with a partner, taking turns as the starting player. Who wins? They should attempt to devise a strategy so that the first player will win.
To analyze the game, assign either an S or a U to each position of the game. Start with a table of positions 0, 1, 2, …, 10.
The 0 position is safe, since moving to this position will win the game. Therefore, label it with an S:
From Position 1, it is only possible to get to 0, so moving to 1 would be unsafe (the opponent would win by moving to 0).
Position 2 is safe because the only possible move is to Position 1. (Remember that this game does not allow a player to take 2 tokens on a turn, so it is impossible to get to 0.) From Position 3, a move can be made to either 2 or 0, both of which are safe. Therefore, Position 3 is unsafe.
Now consider Position 4. From 4, you can move to 0, 1, or 3. If you were playing this game and there were 4 tokens left, how many would you remove? Of course, you’d remove all of them to win! Consequently, Position 4 is unsafe. In general, if a position has any safe positions among its successors, it is unsafe.
Thus, when playing this game, you want to play first and take either one or three tokens. Following each move by your opponent, move to a position labeled S. Unfortunately, the table is too small to show a pattern. But if your students carry out the labeling for the game N1,3,4(100), they will see a definite pattern—the sequence repeats after seven positions.
After students understand this game, have them work with a partner to do the first question on the Subtraction Games Activity Sheet.
Additional questions can be completed in pairs or for homework. You may wish to read the
solutions prior to having students complete the activity sheet.
