In 1901 Charles Bouton, a mathematician at Harvard, published a short paper called "Nim, a game with a complete mathematical theory." It contained everything in this chapter: the binary trick, the proof, and the name Nim, which he may have taken from the German word nimm, meaning "take", though that is a guess. It was the first time anyone had published a complete solution to a game like this. Fifty years later, in 1951, a computer called Nimrod, built by the British company Ferranti, played Nim against visitors at the Festival of Britain in London. It was one of the first computers ever built to play a game. And Nim is more than a curiosity: in Chapter 10 you will see that every game that has to end, where both players have the same moves and the last move wins, is secretly a game of Nim.
Nim and binary
Three piles of stones instead of one. Take as many as you like from a single pile, and the last stone wins. Robo still plays perfectly, and the backwards trick from Chapter 5 still works, but the losing positions are hiding somewhere new: inside the pile sizes, written in base 2.
Chapter 5 had one pile. This game, called Nim, has several. The rules: there are some piles of stones. On your turn, pick one pile and take as many stones from it as you like, at least one, up to the whole pile. Whoever takes the last stone wins.
That one change breaks the remainder trick. There is no single number to divide by 4 any more. But there is still a secret, and it is a good one. Play Robo a few times first. Pay attention to the moment when only two piles are left.
Nim
Take any number of stones from one pile. Last stone wins.Did you catch it? Once only two piles are left, Robo makes them the same size the first chance it gets, and then Robo copies you: whatever you take from one pile, Robo takes from the other. Robo always has an answer, and Robo gets the last stone. Two equal piles, with nothing else, is a losing position for the player who must move. Three piles are harder to see through. The secret that handles any number of piles needs a new way of writing numbers.
Numbers in base 2
You write numbers in base 10. The places are worth 1, 10, 100, and so on, and each place holds a digit from 0 to 9. Base 2, also called binary, uses places worth 1, 2, 4, 8, 16, each one double the last, and each place holds only a 0 or a 1. You write a number by choosing which places to switch on.
Take 13. The biggest place that fits is 8. That leaves 5. The 4 fits, leaving 1. The 2 does not fit, so it gets a 0. The 1 fits. So 13 = 8 + 4 + 1, and in binary it is 1101. Every number from 0 to 15 can be written with the four places 8, 4, 2, 1, and each number has exactly one way to be written. Try it below, in both directions.
Base 2
Type a number, or click the boxes to switch places on and off.Computers use base 2 because a wire is either carrying a current or it is not, which is exactly two choices, and two choices is all you need to hold a 0 or a 1. A single 0 or 1 is called a bit, and everything a computer holds, from this page to a video game, is a very long list of bits.
Adding without carrying
Here is the secret. Write every pile size in binary, one under the other, with the places lined up. Then add each column in a strange way: a column comes out 1 if it holds an odd number of 1s, and 0 if it holds an even number. Never carry anything into the next column. The answer is called the nim-sum. With piles of 3, 4, and 5:
The 8s column has no 1s at all, which is an even number, so it is 0. The 4s column has two 1s, even, so 0. The 2s column has one 1, odd, so 1. The 1s column has two 1s, so 0. The nim-sum is 0010, which is 2. This way of combining numbers is called XOR (say: EX-or), short for "exclusive or", and here is the rule that solves the whole game:
A Nim position is L for the player who must move exactly when its nim-sum is 0. Every other position is W.
Check it against Chapter 5. With one pile, the nim-sum is just that pile's size, and it is 0 only when the pile is empty. Facing an empty pile means the other player just took the last stone: L. That matches. Two equal piles: the two binary rows are identical, so every column holds either two 1s or none, and the nim-sum is 0. L again, which is exactly what Robo's copying trick showed you. Now practice the column sum until it is automatic. You will need it fast.
Nim-sum by hand
Click each answer box: 1 if the column has an odd number of 1s, otherwise 0.Why it works
A rule you cannot check is just a rumor. Here is the proof, in three steps. Read each one slowly and make sure you believe it before moving to the next.
- From a nim-sum of 0, every move breaks it. A move changes exactly one pile. Changing a number changes at least one of its binary digits, and flipping one digit in a column changes that column's count of 1s from even to odd. So after any move, some column is odd, and the nim-sum is no longer 0. Whoever faces 0 must hand the other player something that is not 0.
- From a nim-sum that is not 0, there is always a move back to 0. Here is the recipe. Find the leftmost column where the nim-sum has a 1. Some pile has a 1 in that column too, otherwise the column would hold no 1s at all. Take that pile and rewrite it: in every column where the nim-sum has a 1, flip the pile's digit. The new number is smaller, because the leftmost digit you flipped went from 1 to 0, and no digit further left changed. So it is a legal move. Each flipped column was odd before and is even now, and the columns you did not flip were already even. So every column is even: nim-sum 0.
- Facing 0 means losing. The board with no stones has nim-sum 0. Suppose you face 0. By step 1 you must move to a nonzero position, and by step 2 the other player can move back to 0. The 0s keep landing on you, the piles only shrink, and the last 0 of all is the empty board. Facing the empty board means the other player just took the last stone. So a player who faces 0 loses, as long as the other player knows the recipe. And a player who faces anything else can win, by using it.
Now you know the recipe, so use it. Each position below has a nim-sum that is not 0, which means there is at least one move that leaves Robo stuck on 0. Find it. "Show binary" writes out the piles for you, but the column sum and the choice of move are up to you.
Find the winning move
Click a stone to choose your move, then check it.The recipe as a formula. Mathematicians write the nim-sum with a circled plus, ⊕, and read it "XOR". Call the nim-sum of all the piles s. Pick a pile of size p that has a 1 in the leftmost column where s has a 1. Then the move is:
which means you take p − (p ⊕ s) stones from that pile. Flipping the digits of p wherever s has a 1 is the same thing as computing p ⊕ s.
Worked example. Piles 3, 4, 5. In binary, 011, 100, 101 (three columns are enough for numbers up to 7). Column by column: 4s: 0 + 1 + 1 is two 1s, so 0. 2s: 1 + 0 + 0 is one 1, so 1. 1s: 1 + 0 + 1 is two 1s, so 0. So s = 010 = 2. The leftmost 1 of s is in the 2s column, and only the pile of 3, 011, has a 1 there. New size: 3 ⊕ 2 = 011 ⊕ 010 = 001 = 1. Take 2 from the pile of 3, leaving 1, 4, 5. Check: 001 ⊕ 100 ⊕ 101 = 000. Robo is stuck.
Two facts about ⊕ worth keeping. For any number a, a ⊕ a = 0 (that is why two equal piles are an L) and a ⊕ 0 = a. The order never matters, so you can add the piles in any order you like.
To solve Nim with any number of piles, write the sizes in base 2 and add the columns without carrying. If the result is 0, the player about to move is losing. If it is anything else, there is always a move that makes it 0. The whole game hides inside one strange kind of addition.
1. Piles of 1, 2, and 3. You go first. Who wins with perfect play?
Answer
1 ⊕ 2 ⊕ 3 = 01 ⊕ 10 ⊕ 11 = 00. The nim-sum is 0, so the player to move is losing. Robo wins. Offer to go second, or ask for different piles.
2. Piles of 5 and 7, your move. What do you take?
Answer
5 ⊕ 7 = 101 ⊕ 111 = 010 = 2. The leftmost 1 is in the 2s column, and only the 7 has a 1 there. New size 7 ⊕ 2 = 5: take 2 from the pile of 7, leaving 5 and 5. Then copy Robo until the end.
3. Piles of 2, 2, and 2. What is the nim-sum? Is this W or L for the player to move, and if W, what is the move?
Answer
2 ⊕ 2 ⊕ 2 = 2, because the first two cancel and leave the third. Not 0, so W. Every pile has a 1 in the 2s column, so pick any of them and replace it with 2 ⊕ 2 = 0: take a whole pile, leaving 2 and 2, a copying position.
Switch the board at the top to Last stone loses, the misère version from Chapter 5. Play the nim-sum rule as if nothing had changed. It works for most of the game and then betrays you at the very end. Find exactly where it goes wrong and how to fix it. Start on paper with piles of 1, 1 and then 1, 1, 1 and then 2, 1, 1, and decide which of those are L when the last stone loses. Then test your fix against Robo, with "Show the secret" on so you can watch the nim-sum.
Answer
When every pile is 1 or 0, the players can only take one stone at a time, so the player to move loses exactly when the number of single stones is odd. In normal play, nim-sum 0 with only single stones means an even number of them, which is the opposite. So the fix is small: play the normal recipe, aiming for nim-sum 0, as long as some pile has at least 2 stones, except on the move that would leave nothing but single stones. On that move, leave an odd number of them instead. From 2, 1, 1 the normal recipe says leave 0, 1, 1, but the misère move is to leave 1, 1, 1 and let Robo take the first of three. Robo knows this rule too, so you will have to play it exactly.
Stars in this chapter
Earn them by doing the clever thing, not by clicking around.
- Beat a perfect Robo at three-pile Nim
- Get five nim-sums right in the column tool
- Find the winning move in three positions in a row