Static Nim

  • Static Nim

    Fibonacci Nim
    Grades: High School
    Periods: 2
    Author: Harold Reiter

    Materials

     
     

    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
    A422
    B319
    A712
    B48
    A26
    B6none

    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:

    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.

    20181514109520
    |||||||...|||||....|||....|..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.

    109876543210
               

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

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

    109876543210
             US

    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.

    109876543210
           USUS

    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.

    109876543210
    USUSUUUUSUS

    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.

    pdficon 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.

    pdficon Subtraction Games Answer Key

    Assessments and Extensions

    Assessment Options

    1. 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).
    2. Have students complete the Subtraction Games Activity Sheet in pairs. Call on students to present their solutions to the class.

    Extensions

    1. 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.
    2. Move on to the last lesson, Optimal Strategies.
     

    Questions and Reflections

    Question 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.]

    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?
     

    Objectives and Standards

    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.
    Common Core State Standards – Mathematics

    9th to 12th

    • Number & Quantity
      • CCSS.Math.Content.HSN-VM.C
        Perform operations on matrices and use matrices in applications.

    Related Resources

    Unit Icon

    Fibonacci Nim

    Grade: High School

    Represent numbers in other bases and convert to and from decimal representations, and then, learn how to play Static Nim.  

    2392icon

    Number Representations

    Number and Operations

    Grade: High School

    Understand place-value by translating between numerical representations.

    Optimal Strategies

    Number and Operations

    Grade: High School

    Determine the optimal strategy for dynamic one-pile nim.