Nim game 3 5 7

As an example of how the game works, suppose there are three heaps with three, four and five coins respectively. Here is how the game could develop:.

The question we're interested in is this: given a particular configuration of heaps and coins, is there a winning strategy for one of the players? That is; is one of the players guaranteed to win if he or she plays the right moves? Let's start by playing with some examples. Suppose the two players are called A and B, and suppose that A goes first. Suppose there are two heaps with a coin each. Then clearly, player B is guaranteed to win: A has to take one of the two coins, leaving B to take the last one.

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.

Imagine you have a 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: , , , , , , , , , , or But for now, just memorise these patterns. For instance, if you can ever get to a pattern and your opponent is on move, then your opponent has no way to win.

Likewise, if he takes 1 from Pile 2, you can take 2 from Pile C. Consider another example: You leave your opponent staring at 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. That leaves you with Well, we know from our memorised list that 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 , you would take 2 from Pile C giving him back the losing pattern 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 , , or 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. There are 4 tokens left. This is the easy but dirty way - with prompt for input, and console. The Nim class was structured so that input and output could be customized, for example to use HTML DOM elements for in and out, instead of the terminal. Programming notes: extra error checking was done with specific informative error messages. Also included was a method of quitting the game. The number of starting tokens the pot can be specified on the command line, the default is Necessary image files: Images file Output: Nim Game - video.

Create account Log in. Toggle navigation. Page Discussion Edit History. Main menu Search. Hide Menu. You may also like Have You Got It? Can you explain the strategy for winning this game with any target? Traffic Lights The game uses a 3x3 square board. Yih or Luk Tsut K'i or Three Men's Morris Some puzzles requiring no knowledge of knot theory, just a careful inspection of the patterns.