Nims game strategy

To get into the winning position, we must always make sure that the nim-sum is equal to zero. In this case, we have to perform such operation, which will set the middle digit to zero — we have to remove two objects from the first heap.

It can be proved, that the opponent cannot turn the game — he cannot make the nim-sum equal to zero and if he takes any step, we will be able to reset nim-sum again. The only difference is in endgame, when there remain only heaps of size 1 — in this situation we remove objects in a way that there remains always an odd number of heaps in standard game, there will always remain even number of heaps. Nim - initial situation. A mental arithmetic strategy game for a wide range of abilities.

Play against the computer to select three numbers that add up to fifteen. An online interactive game for two players or teams celebrating the order of mathematical operations. The first to claim four cells in a line wins. Do you have any comments? It is always useful to receive feedback and helps make this free resource even more useful for those learning Mathematics anywhere in the world.

Click here to enter your comments. They are all powers of To write a number in decimal notation, you first write it as a sum of consecutive powers of 10 with the largest power on the left and then pull out the coefficients of these powers.

We can do the same with powers of 2 rather than For example, the binary number stands for. You can convince yourself that a binary number only consists of the digits 0 or 1: when you write a number as a sum of consecutive powers of 2, no other coefficients are necessary.

One of the first ever gaming computers, called Nimrod , was designed to play the game of Nim and exhibited at the Festival of Britain. The secret to finding the winning strategy hinges on writing the sizes of the heaps the number of coins in each heap in binary, and then adding those numbers up — but not using the ordinary way of adding numbers, but something appropriately called Nim addition.

To add some given binary numbers using Nim addition, you first write them underneath each other, as you might for ordinary addition. Then you look at each of the columns in turn. If the number of 1s in a column is odd, you write a 1 underneath it; if it's even, you write a 0 underneath it.

Doing this for each column gives a new binary number, and that's the result of the Nim addition. As an example, let's Nim-add the binary numbers 10, 11, and which stand for the decimal numbers 2, 3 and 4 :. So the result, which is called the Nim sum , is the binary number When Charles Bouton analysed the game of Nim, he figured out two facts which hold the key to the winning strategy.

Fact 1: Suppose it's your turn and the Nim sum of the number of coins in the heaps is equal to 0. Then whatever you do, the Nim sum of the number of coins after your move will not be equal to 0. Fact 2: Suppose it's your turn and the Nim sum of the number of coins in the heap is not equal to 0. Then there is a move which ensures that the Nim sum of the number of coins in the heaps after your move is equal to 0. It is not too difficult to prove that these to facts are always true see for example this article but you can also convince yourself by playing around with heaps of coins.

Now suppose you are player A, so you go first. Also suppose that the Nim sum of the number of coins in the heaps is not equal to 0. Your strategy will be this: if possible always make a move that reduces the next Nim sum, the Nim sum after your move, to 0. This would then mean that whatever player B does next, by fact 1 the move would turn the next Nim sum into a number that's not 0.

This ping-pong between zero and non-zero Nim sums means that you are guaranteed a win! If player B were to win, she would have to make a move that leaves over no coins at all.

That is; she would have to make a move that results in a zero Nim sum which, as we can see, is impossible. Your moves, on the other hand, always reduce the Nim sum to zero.

And at some point in the game, the zero Nim sum will correspond to there actually being zero coins left — you've won. This shows that if the Nim sum of coins in the heaps at the start of the game is not 0, then player A has a winning strategy. The strategy is to always make a move that reduces the next Nim sum to 0.

You can check that this is the strategy played by player A in the example at the beginning of this article. If the Nim sum of coins in the heaps at the start of the game is equal to 0, then player B has a winning strategy. Whatever player A does on the first move will result in a non-zero Nim sum when it's B's turn.

And by the same reasoning as above, this means that the winning strategy is now in B's hands. Nim addition is clearly very useful when you're playing Nim, but that's about it, right? It turns out that much of our everyday life depends on this curious way of adding up numbers. Computers are binary machines.

All the information they store, including numbers, is translated in to strings of 0s and 1s. For example, given a user name and a password, they need to ask the questions "is the user name correct?

Note that this operation takes two inputs user name correct? Writing 0 for "no" and 1 for "yes", these logical operations can also be turned into operations involving 0s and 1s.

Luckily, it turns out that any logical operation you might ever want to perform can be made out of six basic ones. You simply have to compose them in the correct way. One of these basic operations is called XOR. It also takes two inputs, each of which can be a 0 or a 1, and returns one output, which can also be a 0 or a 1. Here is the table of outputs XOR returns for a given combination of inputs:.

In normal play, the winning strategy is to finish every move with a nim-sum of 0. This is always possible if the nim-sum is not zero before the move. If the nim-sum is zero, then the next player will lose if the other player does not make a mistake. To find out which move to make, let X be the nim-sum of all the heap sizes. Find a heap where the nim-sum of X and heap-size is less than the heap-size - the winning strategy is to play in such a heap, reducing that heap to the nim-sum of its original size with X.

The only heap that is reduced is heap A, so the winning move is to reduce the size of heap A to 1 by removing two objects. As a particular simple case, if there are only two heaps left, the strategy is to reduce the number of objects in the bigger heap to make the heaps equal.