The Secret of NIM

By Arthur Holshouser

Harold Reiter

Drew Boyuka

John Mahoney

 

            In the October 24, 2002 episode of the CBS television show “Survivor: Thailand”, the two tribes were presented with a mathematically based Immunity Challenge. They faced a circle of 21 flags.  The two tribes had to take turns removing flags from the circle and they could either remove 1, 2, or 3 flags in each turn.  At the end of the game, called Thai 21 on the TV show, the tribe that took the last flag would win the challenge.  In the show, the Chuay Gahn tribe outsmarted the Sook Jai tribe. What is the mathematics behind this game and what is a successful strategy for winning? 

            Try the game with your students.  Use Cheerios instead of flags and divide the students into pairs.  Have them count out 21 Cheerios and alternate picking (and probably eating) 1, 2, or 3 at a time.  See if they can figure out a strategy for winning.  The winning strategy is based on patterns, so encourage your students to look for them.  [With my students, I have the loser of each game decide whether s/he wishes to go first or second in the next game.]

Figure 1

            In the TV game, the teams drew straws to determine which team went first. Both teams seemed to have strategies, but a member of the Sook Jai team slipped up in the middle of the game and enabled the Chuay Gahn team to win.  The Chuay Gahn team apparently realized that they needed to leave exactly four flags remaining after their next to last move.  Then no matter how many (1, 2, or 3) flags the Sook Jai tribe took, there would be either 1, 2, or 3 flags for the Chuay Gahn tribe to take on their final move.  Therefore, the Chuay Gahn tribe’s strategy was to make sure that they left exactly 4 flags in the circle after their next to last move.  

            To be sure they would be able to do this, the Chuay Gahn tribe needed to leave exactly 8 flags in the circle after their third to last move.  If they did this, then no matter how many (1, 2, or 3) flags Sook Jai tribe took, the Chuay Gahn tribe could then take 1, 2, or 3 to leave exactly 4 flags in the circle.  This pattern leads to the strategy for this game: “Leave a multiple of 4 flags at the end of each player’s turn.”

            We ask our students to play this and other mathematical games with their parents and siblings at home.  Playing games encourages students to explore and explain the value of mathematical patterns.  It also, we believe, raises their self esteem and mathematical confidence.  Your students may also want to change the rules of the game by allowing players to pick 1, 2, 3, or 4 items each turn. They should be able to figure out winning strategies for these rules, too. These games are variations of the mathematical game Nim. The strategy for playing Nim and its variations is based on patterns.  The game of Nim and its variations lend themselves to being played at restaurants with sugar packets!

            Consider the original game with 21 flags again. Did your students find a strategy?  The winning strategy is to leave your opponent with a multiple of four flags.  This strategy works because any move (taking 1, 2, or 3 flags) from a multiple of four flags leaves a number of flags which is not a multiple of four.  And, if the number of flags is not a multiple of four, then there is some move which will leave a multiple of four.  Numbers that are not multiples of four are in the form of 4k + 1, 4k + 2, or 4k + 3, where k is an integer, and thus they can be reduced to a multiple of 4 by taking 1, 2, or 3 flags respectively.  Since taking the last flag leaves 0 flags which is itself a multiple of 4, this strategy assures a victory.

            We call the previous type of Nim, Static Nim, as the number of counters that can be removed on each turn is fixed throughout the game.  In contrast, Dynamic Nim has rules that allow the maximum number of counters that can be removed to change during the play of the game. One variation of dynamic called Identity Nim.  In this version each player can take only as many as was taken on the previous play.  On the first move, up to one less than the total number of counters can be taken.  Have your students try this game with 20 counters or by using the applet: Illuminations  Can they figure out a strategy? Are there good moves for the first player? Bad moves?

 

            Discussion of Identity Nim:

            Suppose the first player takes one counter, then the second player will continue to move to the positions with an even number of counters, including (eventually) the zero position. So the first player must not take 1 counter.  Suppose the first player takes an odd number of counters.  Then the second player can take 1 counter, and we are back to the same situation as above, a win for the second player.  Thus, the first player must take an even number of counters and, by the same reasoning, each move after that should also be an even number of counters.  Hence, we may as well assume that the counters are glued together in pairs, and that we start with only 10 pairs.  Applying the same reasoning as above, the first player cannot take just 1 of these pairs.  In fact he must take an even number, and so must the second player.  Hence we may as well be playing the game with five counters that are glued together in bunches of four.  Now there is a move for the first player that clearly wins: take one bunch of four. This suggests an easy to remember rule for winning an Identity Nim game: Remove the largest power of 2 counters that divides the size of the pile. [1]  The proof of this strategy relates to a binary representation of the number of counters in the pile.  Consider the following table:

 

Number of counters in pile

Binary representation of the number of counters

The largest power of 2 which

Divides the pile

Number of counters which remain after the move

Binary representation of the # of counters which remain

20

10100

4

16

10000

19

10011

1

18

10010

18

10010

2

16

10000

17

10001

1

16

10000

16

10000

16

0

0

15

1111

1

14

1110

14

1110

2

12

1100

13

1101

1

12

1100

12

1100

4

8

1000

11

1011

1

10

1010

10

1010

2

8

1000

9

1001

1

8

1000

8

1000

8

0

0

7

111

1

6

110

6

110

2

4

100

5

101

1

4

100

4

100

4

0

0

3

11

1

2

10

2

10

2

0

0

1

1

1

0

0

 

 

Compare the binary representations in the second column with those in the fifth column above.  Note that the winning move in this game is equivalent to taking the right-most 1 in the binary representation of the number of counters in the pile.  What is less obvious is the fact that the second player cannot make a similar move.

            Try this strategy with a friend or with the aid of the applet.  Does it work?  Are there initial sizes of piles for which the first player can’t be assured of a win with this strategy?

           

            The next version of Nim is a game we call Doubling Nim.  Here we allow a player to take as many as twice the number taken on the previous move.  Again, the first player cannot take all of the counters. Again, have your students play this devilish game with each other with 20 counters or by using the applet. Encourage them to try to come up with a strategy by playing the game repeatedly.  Again, encourage them to identify good moves and bad moves for the first player.

            The strategy for this game is based on Fibonacci numbers.  Just as we can use binary notation to represent every positive integer as a sum of distinct powers of 2, we can use a similar process to write integers as a sum of Fibonacci numbers.  Here is an algorithm for doing so.  Pick the largest Fibonacci number not exceeding the given integer, then subtract the Fibonacci number and continue the process with the difference.  For example, to write 20 in Fibonacci, subtract 13 from it to get 7. Subtract 5 from 7 to get 2, which itself is a Fibonacci number.  Thus 20 = 1×13 + 0×8 + 1×5 + 0×3 + 1×2 + 0×1 = 101010.  The winning strategy for Doubling Nim involves removing the smallest of the Fibonacci summands.  Here we have expressed 20 = 13 + 5 + 2 and thus the winning move involves taking two counters.   This is equivalent to taking the right most “1” in the Fibonacci representation of the number of counters in the pile.

 

 

Number of counters in pile

Fibonacci representation of the number of counters

The smallest of the Fibonacci summands

Number of counters which remain after the move

Fibonacci representation of the # of counters which remain

20

101010

2

18

101000

19

101001

1

18

101000

18

101000

5

13

100000

17

100101

1

16

100100

16

100100

3

13

100000

15

100010

2

13

100000

14

100001

1

13

100000

13

100000

13

0

0

12

10101

1

11

10100

11

10100

3

8

10000

10

10010

2

8

10000

9

10001

1

8

10000

8

10000

8

0

0

7

1010

2

5

1000

6

1001

1

5

1000

5

1000

5

0

0

4

101

1

3

100

3

100

3

0

0

2

10

2

0

0

1

1

1

0

0

 

 

Compare the Fibonacci representations in the second column with those in the fifth column above.  Note that the winning move in this game is equivalent to taking the right-most 1 in the Fibonacci representation of the number of counters in the pile.  What is less obvious, is the fact that the second player cannot make a similar move.

Try this strategy with a friend or with the aid of the applet.  Does it work?  Are there initial pile sizes for which the first player can’t be assured of a win with this strategy?

 

The last version of NIM is what we call Tripling Nim.  Here we allow a player to take as many as three times the number taken on the previous move.  Again, the first player cannot take all of the counters. Try this devilish game with a friend or by using the applet.  Try to develop a strategy similar to the binary and Fibonacci based strategies given in the previous versions.

 

The game of Nim was a central aspect of Alain Resnais' 1961 avant-garde film “Last Year at Marienbad.”  In the film the counters (dominoes and cards in the movie) are arranged in four rows in a 1 – 3 – 5 – 7 pattern and the player who takes the last counter loses. A player can take any number of counters from any one row in each move.   You may want to show brief clips from that movie to your class.

            The secret of Nim is patterns.  Patterns are fundamentally important to successful strategies in most games, from tic-tac-toe and chess to basketball and softball.  When looking for patterns, one learns to recognize the salient aspects of particular situations and then act upon them. Playing math games stimulates communication about mathematics and mathematical reasoning and problem solving are used to develop winning strategies for the games.


References:

Anatole Beck, Michael Bleicher, Donald Crowe, “Excursions Into Mathematics”, Worth Publishers, Inc., 1969

Cut the Knot http://www.cut-the-knot.org/nim_st.shtml

Fruit Game http://www.2020tech.com/fruit/

Game Theory.net http://www.gametheory.net/html/games.html

Martin Gardner, “Mathematical Puzzles & Diversions”, Simon and Shuster, NY, 1959

Dynamic One-Pile Nim, with Arthur Holshouser and James Rudzinski, The

Fibonacci Quarterly, vol 41.3, June-July, 2003, pp 253-262.

Games and Representations, by Holshouser and Reiter, http://www.math.uncc.edu/~hbreiter/GamesandReps.pdf

.