Illuminations: Fibonacci Nim

# Fibonacci Nim

## Static Nim

 Static Nim is a one-pile game between two players. In this game, the maximum number of tokens that can be removed on each turn remains constant throughout the game. In this lesson, students will learn to represent the positions as the vertices of a directed graph and the moves as the edges of the graph. Also, they will learn that solving a game means finding a partition of the vertices into two sets such that three important properties are satisfied.

### Learning Objectives

 Students will: Represent the positions as the vertices of a directed graph and the moves as the edges of the graph. Understand that solving Nn(k) means finding the set S of safe positions. Understand the winning strategy when playing the games Nn(k). Learn to analyze games with selected subsets of allowed moves.

### Materials

 Subtraction Games Activity Sheet 25-30 tokens or other items for counting per pair of students Nim Games Activity

### Instructional Plan

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:

1. 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.)

2. 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.)
3. 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 xy, 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:

1. Every move from a position of S (one with no dots) inevitably goes to a position of U (one with some dots).
2. For each position in U, there is some move that will lead to a position in S.
3. 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.

 10 9 8 7 6 5 4 3 2 1 0

The 0 position is safe, since moving to this position will win the game. Therefore, label it with an S:

 10 9 8 7 6 5 4 3 2 1 0 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).

 10 9 8 7 6 5 4 3 2 1 0 U S

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.

 10 9 8 7 6 5 4 3 2 1 0 U S U S

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.

 10 9 8 7 6 5 4 3 2 1 0 U S U S U U U U S U S

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.

### Questions for Students

 Explain the optimal strategy for winning a Nim game with an initial pile of n tokens and a maximum move of k tokens on each turn. [Divide n by k + 1; the remainder is the number of coins that should be taken on the first turn. (If the remainder is 0, allow the other player to go first.) This will leave a pile with a multiple of (k + 1) tokens remaining. On successive turns, take (k + 1 – p) tokens, assuming the other player took p tokens. That way, the other player and you combined will remove (k + 1) tokens on each pair of turns, and because the pile had a multiple of (k + 1) tokens remaining, you will eventually win the game.]

### Assessment Options

 Ask students to create a Nim game like the ones described in this lesson and analyze it. You may wish to help students select a game to analyze. Students who are experiencing difficulty should be given a simple game to analyze, such as N3(15). Students who are having success can be given a more complex game, perhaps N1,3,6(30). Have students complete the Subtraction Games Activity Sheet in pairs. Call on students to present their solutions to the class.

### Extensions

 The online Nim Games activity allows students to play other variations, such as Identity Nim (each player can take no more than the number of coins taken by their opponent on the previous turn) and Doubling and Tripling Nim (each player can take no more than double or triple the number of coins taken by their opponent on the previous turn). These games are harder to analyze than the games in this lesson, but you may wish to let students play them. In fact, some students may be able to determine an optimal strategy for Identity Nim on their own. Allow students to investigate Nim Games that use more than one pile of tokens. The classic game of Nim uses three piles of 3, 5, and 7 tokens. On a turn, players can remove as many tokens as they want, but only from one pile. Again, the player who takes the last token wins. The winning strategy for this game is based on addition of binary numbers.

### Teacher Reflection

 Were students engaged throughout this lesson? How do you know? Because this lesson is based on a game, some would argue that students are spending more time playing than learning. What mathematics did students learn while participating in this lesson? How could the lesson be enhanced to increase the mathematics that students learn? In what ways could the lesson be modified so that students discover some of the concepts on their own, rather than having them explained by the teacher?

### NCTM Standards and Expectations

 Geometry 9-12Use vertex-edge graphs to model and solve problems. Number & Operations 9-12Develop fluency in operations with real numbers, vectors, and matrices, using mental computation or paper-and-pencil calculations for simple cases and technology for more-complicated cases.
 This lesson prepared by Harold Reiter.

2 periods

### Activities

 More and Better Mathematics for All Students
 © 2000 National Council of Teachers of Mathematics Use of this Web site constitutes acceptance of the Terms of Use The National Council of Teachers of Mathematics is a public voice of mathematics education, providing vision, leadership, and professional development to support teachers in ensuring mathematics learning of the highest quality for all students. The views expressed or implied, unless otherwise noted, should not be interpreted as official positions of the Council.