How to win at Nim

Nim is a really fascinating game. Now for some of the math behind it…

The solution to the 1,2,3 one pile Nim game

Here is the answer to the 1,2,3 ten stone, one pile Nim game.

What we have to realise is that the player who is left with a pile of 3,2 or 1 stones is going to be the winner, but the player who is left with 4 stones in the pile is definitely a loser.

So, the winning strategy of the first player is to try and leave the second player with a four stone pile.
If we had 5,6 or 7 stones in the original pile, the first player could easily do this, by taking 1,2 or 3 stones to leave the second player with 4 stones and a losing position.
Unfortunately, the initial pile is bigger and has ten stones.
The question now becomes how can the first player force the second player to leave him with 5,6 or 7 stones – positions from which he (the first player) can win.

Luckily, the first player can do this by taking two stones from the initial ten stone pile, leaving 8 stones in the pile for the second player. However many stones the second player now takes, 1,2 or 3, he leaves 5, 6 or 7 stones in the pile from which the first player can take the necessary number of stones to leave the second player with the losing four stone position.

In fact, you may have realised by now, that any multiple of 4 is a losing position for the second player. This means that if you play Nim against someone using the 1,2 or 3 rule, make sure you don’t have a multiple of four number of stones in your initial pile…

A friend of mine, the stand up mathematician, Matt Parker, has a beautiful explanation of the 1,2,3 Nim game. You can see it in the following YouTube video.

Nim becomes much more complicated as the rules change and the number of piles becomes larger. In fact, there is a whole genre of games based on Nim that mathematicians are still studying today. One of the mathematicians who made many contributions to these so-called combinatorial games is One of the mathematicians who made many contributions to these so-called combinatorial games is Professor Aviezri Fraenkel, based here at the Weizmann Institute, who has been the recipient of many awards including Israel’s highest honour – the prestigious Israel Prize.

Indeed, Nim really deserves a course of it’s own, but going beyond what we have ‘tasted’ in this activity is beyond the scope of this introductory course. You might, however, want to experiment yourself with the online multi-pile Nim game in the related links below.

Discussion

What would be the losing positions in Nim if the rules are that each player can choose up to 5 stones (included)? Post your answers in the comments below. We’ll pin the correct answer once someone’s solved it.