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.

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 *N*_{k}(*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, *N*_{4}(20) means that there *n* = 20 tokens and that up to *k* = 4 tokens can be removed on each turn.

The optimal strategy for *N*_{4}(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 *N*_{4}(20) again. Notice that each position in the game *v* = 0, 1, 2, …, 20 can be represented in the form *v* = 5*t* + *u* where 0 ≤ *t* ≤ 4 and 0 ≤ *u* ≤ 4. With this in mind, for example, you could write 17 = 5*t* + *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 *N*_{4}(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 *N*_{5}(20) to check for understanding.

### Other Static Games

Consider the game *N*_{1,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 *N*_{1,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.

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.

Subtraction Games Answer Key