Mental matchsticks

Learning patterns is the key to winning a game of Nim.

NIM IS A POPULAR strategy game the world over. Play is simple: Players take turns removing counters (coins or matchsticks are perfect playing pieces) from any one of three piles. The loser is the person who is forced to take the last object. An equally popular variant is to have the person taking the last object win the game rather than lose. The strategic concepts for either version are essentially the same. Nim is one of the oldest strategy games known. Its origins date back to at least the 1500s and possibly earlier. It’s very similar to an ancient Chinese game using only two piles of stones called Tsyan-shizi (Picking Stones).

Although there are potentially dozens of starting arrangements, we’ll examine the one I was first shown by my father, an excellent Nim player. He arranged three piles of matchsticks. Pile A had 3 matchsticks, Pile B had 5 and Pile C had 7. He explained that the person who took the last matchstick would lose. My father also added the stipulation that players could only remove 1, 2 or 3 matchsticks at a time. I’ll explain why he did this in a moment. The starting setup looked like this:

III IIIII IIIIIII

My father went first. He removed 1 matchstick from Pile A. With the misplaced confidence of youth, I removed the remaining 2 matchsticks from Pile A. My father removed 2 from Pile C, leaving me staring at two groups of 5. I took 2 from Pile B. He took 2 from Pile C. As I looked at the two remaining groups of 3 matchsticks each, I knew I was in trouble. In desperation, I took 3 from Pile B. He took 2 from Pile C and left me staring at the last (losing) matchstick. I was 8 years old and I was hooked.

After crushing me several games in a row, my father allowed me to go first. I still lost a dozen or so games until I finally won one. Unfortunately, I couldn’t remember the move sequence, so I didn’t know how I’d won! Eventually he tipped me to his strategy. Grab some coins, buttons or matchsticks and follow along. Make up a pile of 3, a pile of 5 and a pile of 7. Here’s the secret: Your goal is to get to certain patterns while leaving your opponent with the move. The most obvious losing “pattern” is a single pile with only 1 matchstick. Whoever is on move is lost. Ok, so that’s not much of a pattern but we build from there! Imagine you have a 1-1 pattern (1 matchstick in Pile A and another in Pile B). If you have the move, you take 1 from either pile and leave your opponent to take the final matchstick. Leaving your opponent staring at any of these configurations while he has the move is a win for you: 2-2, 3-3, 4-4, 5-5, 1-1-1, 1-23, 1-4-5, 2-2-4, 2-4-6, 2-5-7, 3-4-7 or 3-56. If you like, you can do a quick internet search for “Nim” and you’ll find a fairly simple explanation for why these patterns are losers for the person that’s on move. A basic understanding of binary numbers is all that’s required to understand it and the “proof” is rather elegant. But for now, just memorise these patterns.

Let’s look at an example. For instance, if you can ever get to a 1-2-3 pattern and your opponent is on move, then your opponent has no way to win. If he takes 3 from Pile C, you take 2 from Pile B and he’s left with the last move in Pile A. Likewise, if he takes 1 from Pile 2, you can take 2 from Pile C. He’ll have to take 1 from some Pile and leave you with a 1,1 scenario.

Consider another example: You leave your opponent staring at 2-4-6. We know that’s a losing pattern for whoever is on move. No matter which pile your opponent takes from, and no matter how many he takes, you will still be able to leave him with another losing pattern after your move. Let’s say he takes 1 from Pile C. That leaves you with 2-4-5. Well, we know from our memorised list that 1-4-5 is a losing pattern if you have the move, so take 1 from Pile A and your opponent is again looking at a losing pattern. If he were to take 2 from Pile B (giving you 2-2-6), you would take 2 from Pile C giving him back the losing pattern 2-2-4.

You may have noticed that if the first player takes a single matchstick from any of the three starting piles, he will always be leaving his opponent staring at a losing pattern. This means that the first player can always force a win! By taking a single matchstick at the beginning of the game, your opponent has to be looking at 2-57, 3-4-7, or 3-5-6. And all of those are guaranteed losers. But wait, I mentioned earlier that my father let me go first and he was still able to beat me. How is that possible? It’s simple – I made a mistake at some point in the game and he was able to get me to a losing pattern. And now we see the reason for his additional rule that you can only take up to 3 matchsticks at a time. This rule has the effect of extending the number of turns. And the more turns I had, the more likely I was to make a mistake at some point – a mistake that he could capitalise upon. If you play this game against your friends, I suggest you add the rule of only taking a maximum of 3 matchsticks per turn. It won’t hurt you when you go first, but it will give your opponent more opportunities to mess up when you allow them to go first.