Nim - 3, 4, 5

Last updated January 29, 2022

This is my favourite version of Nim.  I first met it in Martin Gardner's Mathematical Puzzles and Diversions when I was 16.

Nim 345.jpg

Rules

  • Players take turns to take as many counters as they like from just one row.
  • Taking the last counter wins.

I often used this as an end of term time filler with sixth form mathematicians.  I used a whiteboard to play against individuals from a group, with their friends giving advice - often bad advice!  I gave them the choice to go first or second, but I would still expect to win 6 or more times before my first defeat.

Strategy

  • It soon becomes apparent that leaving just two equal rows wins.  For example: -
    ...
    OOOO
    OOOO.
    Whatever you take from the middle or bottom row, I take the same from the other row.
    Student play then concentrates on trying not to give me the option to leave two equal rows.
  • It is harder to spot my next type of winning position, i.e. 1 - 2 - 3 (the order does not matter).  For example: -
    OO.
    O...
    OOO..
    You have 6 possible moves: 1 or 2 from the top, 1 from the middle and 1 or 2 or 3 from the bottom.
    In each case, I can make a move to leave two equal rows and win.
  • Now they have two types of position to avoid leaving me, i.e. two equal rows and 1 - 2 - 3.
    By carefully considering all possible first moves, it is not hard to see that they can win by playing first and taking 2 from the top row.
    O..
    OOOO
    OOOOO
    Now, after any move I make, they can create a winning position of two equal rows or 1 - 2 - 3 , so 1 - 4 - 5 is also a winning position.
  • This is all you need to play a perfect game.
    In the early stages of my class tournament, if they chose to let me go first, then I made a deliberate bad move (say take 1 from the top row), so that copying my starting strategy would fail!  Similarly, if they left 1 - 4 - 5 without realising they were in a winning position, I'd muddy the water by perhaps taking one from the middle, leaving them the maximum scope to make an error.

This 3, 4, 5 game can be extended, and so made more difficult, by adding more counters to the rows, or adding more rows.  Using the above approach would become very tedious for a large game, but the idea of a pair of equal rows giving a win can be extended mathematically for an easy winning strategy.  Martin Gardner tells me that in 1901, Charles Bouton published a complete strategy for any number of counters in any number of rows!  His method uses binary numbers.

Mathematics

  • We normally count using base 10, e.g. 2047 represents 7 units, 4 tens, 0 hundreds and 2 thousands.
  • Binary arithmetic uses base 2 and counts using units, twos, fours, eights, sixteens,  . . . , only requiring the digits 0 and 1.
    For example 110101 represents 1 unit, 0 twos, 1 four, 0 eights, 1 sixteen and 1 thirty-two, giving 53 in normal base 10.
  • Let's use a 3, 4, 6, 7 game as an example, and convert each of these numbers to binary.  I will also find the column sums (using usual base 10).
    OOO      3    11
    OOOO     4   100
    OOOOOO   6   110
    OOOOOOO  7   111
                 332
  • To create a winning position, we need to make all the column totals even (a bit like having pairs of equal rows).
  • This can't be done by taking counters from the top row, as we need to change the fours column and there are only 3 counters.
    It can be done by taking 2 from the second row, or 6 from the third row, or 6 from the bottom row.  Here is the result in each case: -
    3    11    OR    3    11    OR   3    11
    2    10          4   100         4   100
    6   110          0               6   110
    7   111          7   111         1     1
        242              222             222
  • Each of these is a winning position - Bouton called them safe.
  • Any move by your opponent will make one of the columns odd, giving an unsafe position.
  • You can always make them all even again and so safe once more!
  • I've not shown a full proof of the strategy, but I think it is clear enough?
  • This safe - unsafe - safe - unsafe . . . strategy continues until all counters are taken and you win!
  • The strategy works for any number of counters in any number of rows.
    If you are faced with a safe position on your turn then you will automatically make it unsafe, so perhaps take just one counter to avoiding simplifying the position, and hope your opponent makes a mistake.

I have read that this version of Nim used to be played in pubs (though I can't really imagine that these days) and in the school where I taught (many years ago), there was lab technician who had done so.  He had no idea of the binary strategy but played the 3, 4, 5 game perfectly and was excellent with larger versions.  He could not describe how he made his moves but surely it involved ideas of pairing?  I had to play a pretty large game with him before my maths beat his acquired instinct!

Nim 3, 4, 5 and its larger cousins can also be played where the person taking the last counter loses!  Amazingly, the above mathematical strategy still works, requiring just a small adjustment when there is only one row with more than one counter.  I will leave you to work this out, or read Gardner.