Now suppose that there are two heaps, one of which contains two coins and the other one. Now player A has a winning strategy: take one of the coins in the two-coin heap. This leaves two heaps with a coin each and B to go next. And as we saw in the previous example, this means that A will win. Let's do one more: suppose that there are two heaps with two coins each.
Now player B has a winning strategy. If A takes an entire heap, then B should take the remaining heap and win. If A takes only one coin of one of the heaps, then we are in the same situation as in the previous example, with B to go first.
Therefore, B is guaranteed to win if she takes one coin from the two-coin heap. From this series of examples you can't help but feel that there is some sort of pattern here: that there should be some sort of clever trick that tells you for a given arrangement of coins and heaps whether there is a winning strategy for one of the players.
The American mathematician Charles Bouton felt the same and set himself the daunting task of analysing the game completely. In he found the trick — and it's subtle! To figure out whether there is a winning strategy and for which player, you first need to The secret is to write the sizes of the heaps as binary numbers if you already know how to do this, skip this part.
To see how to do this, let's first remind ourselves of how the ordinary decimal way of writing numbers works. Let's take the number as an example. The digit 4 in this number doesn't stand for the number 4, rather it stands for , or 4 x So means. What do the numbers , , 10 and 1, which appear in these expressions, have in common? 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.
First European references to this game are from A winning strategy for Nim was proved and published by Charles L. Bouton in in the article Nim, a game with a complete mathematical theory. At first, we have to convert a number of objects matchsticks to the binary numeral system.
Let's suppose that we have 3 heaps with 3, 4 and 5 objects. The player may remove at most 3 objects from exactly one heap. Now we sum the binary sum sizes together, while neglecting carries from one digit to another we perform XOR operation. For reference, the first few powers of 2, starting with power 0, are: 1, 2, 4, 8. In this table, for example, 5 can be thought of as. For decimal numbers greater than 15, one simply adds the successively larger powers of 2 as new columns to the left.
What we are going to do is convert the number of tokens in each pile of a given position to binary form. Suppose we have the position 4,5,6 giving us three piles, having 4, 5, and 6 tokens respectively.
We want to convert 4, 5 and 6 into binary and put them in a little table like this. Notice that in each column, there are an odd number of 1s. This tells us that this is a winning position! The simple rule for classifying all positions is that if every column has an even number of 1s, the position is a loser!
So, to produce a losing position for our opponent, we want to select a move such that afterwards, all columns will end up even. Look what happens if we simply take one from the pile of 4, leaving 3.
Removing one token from the pile of 4 will yield a loser for your opponent. Is this the only possible move here? Take 3 from the pile of 5 to leave 2, changing 0 1 0 1 into 0 0 1 0.
0コメント