Math Detours · Grade 6 · Around the corner · 34

Nim where the last counter loses

Change one word in the rules of Nim and the perfect strategy almost survives. The one place it breaks tells you exactly what the original proof was quietly assuming.

Name ____________________Date ____________

Tonight's idea

In Nim you learned a complete strategy: write the piles in binary and always hand your opponent a balanced position, one where every column has an even number of 1s. Tonight we change the last rule only. Whoever takes the last counter loses. Every move is still legal. Does the strategy survive?

Start tiny. A single pile of 1: you must take it, and you lose. Two piles of 1: you take one, your opponent must take the last, you win. Yet 1-1 is balanced, which in ordinary Nim meant the player to move was lost. The rule has flipped.

So the theorem breaks. The interesting question is where. Try 2-1, then 2-1-1, then positions with two or more piles bigger than one. Keep a list of solved positions and look for the boundary between where the old rule works and where it fails. Then state a repaired rule and beat the computer with it.

Same moves, opposite ending. Which part of "balanced is bad" is about the moves, and which part is about the ending?

Watch one: 2-1-1

Binary: 2 = 10, 1 = 01, 1 = 01. The 2s column has one 1, so the position is unbalanced, and ordinary Nim says: balance it by taking the whole 2, leaving 1-1. Try that here. Your opponent takes a counter, you take the last one, and you lose. The balancing move is a losing move.

Instead take one counter from the 2, leaving 1-1-1. Now your opponent faces three lone counters. Whatever they do, two are left, you take one, and they are forced to take the last. So in 2-1-1 the winning move is to shrink the big pile to 1, not 0. In 2-1, by contrast, taking the whole 2 leaves a single counter and wins. The big pile must leave behind an odd number of lone counters.

Your turn

  1. Who wins 1-1-1, 1-1-1-1 and 1-1-1-1-1, if everyone plays well? State the rule for positions where every pile is a single counter, and say how it compares with ordinary Nim.
  2. 5-1-1 and 5-1-1-1. In each, should the 5 be cut down to 0 or to 1? Explain the rule for one big pile with some lone counters.
  3. Someone claims "the Nim strategy works unchanged in the last-counter-loses game". Give them a position and a move that proves them wrong.
  4. Now two or more piles bigger than one: 3-4, 2-2, 1-2-3 and 3-5-7. For each, decide whether the player to move can win the last-counter-loses game and, if so, give a winning move. Compare with ordinary Nim.
  5. Write your complete rule in a few sentences, then test it against the computer at mathdetours.com/demos/nim.html with the last counter loses box ticked.

Stretch: which sentence of the proof broke?

Reread the stretch of the Nim sheet. Its two facts about balancing are still true tonight, because the moves have not changed. Only one sentence relied on the last-counter rule. Find it. Then explain why the balance strategy keeps working right up until a single big pile remains, and why that is exactly where you had to improvise.

Answers

  1. 1-1-1: the player to move loses. 1-1-1-1: wins. 1-1-1-1-1: loses. When every pile is a single counter, the player to move wins exactly when the number of counters is even. In ordinary Nim it is the other way round: an even number of 1s is balanced and loses.
  2. 5-1-1: cut the 5 down to 1, leaving 1-1-1 (three lone counters, odd, so the opponent loses). 5-1-1-1: take all 5, leaving 1-1-1. The rule: when exactly one pile is bigger than one, cut it to 0 or to 1, whichever leaves the opponent an odd number of lone counters. One of the two choices always works.
  3. 2-1-1 is the simplest. Ordinary Nim says take both counters from the 2, leaving the balanced 1-1. In the last-counter-loses game that hands your opponent the win. (1-1 itself is another: the old rule says the player to move is lost, but they win.)
  4. 3-4: unbalanced (011, 100), so the player to move can win by taking 1 from the 4 to leave 3-3. 2-2: balanced; the player to move loses. 1-2-3: balanced; loses. 3-5-7: unbalanced; take 1 from any pile, exactly as in ordinary Nim. While two or more piles are bigger than one, the answers are the same as ordinary Nim: balanced loses, and the balancing move wins. The only change is the endgame.
  5. Look at the piles at the start of your turn. If two or more piles are big (two counters or more), play ordinary Nim and hand over a balanced position. If exactly one pile is big, cut it to 0 or 1 so your opponent gets an odd number of lone counters. If every pile is a lone counter, just take one. This rule was checked by computer on every position with up to four piles of at most six counters: from every winning position, it picks a winning move. (Careful: "balance unless your move would leave one big pile" is wrong. In 2-1-1 the balancing move leaves no big piles at all, and it loses.)

Stretch. The sentence is "the empty position 0-0-0 is balanced, and the player facing it has already lost". Tonight the player facing 0-0-0 has won, because the other player took the last counter. Everything else in the proof is about moves, so handing over balanced positions still forces your opponent to unbalance, until one big pile is left. A balanced position can never have exactly one big pile (its top column would have a single 1), so the big-pile endgame is always yours to choose, and you choose the odd number of lone counters.

← PreviousNext: Add with a ruler →