Shortcuts Sitemap Contact Newsletter Store Books Features Gallery Games  Are you looking desperately for a puzzle solution? No panic, mail us your question and we'll try to solve your puzzle problem! All the Most wanted puzzle solutions in a look Nim-game on Wikipedia Nim-game explained # Most Wanted Puzzle Solutions

How to win at the Nim game  "A friend of mine beats me REPEATEDLY at Nim-game... That frustrates me immensely! Are there some winning algorithms you can apply to win at this game? Thanks for your kind help!" -- Antoine Category: Mathematical game of strategy / Combinatorial game Name: Nim-game (or Marienbad-game, aka tactix) Material: Matchsticks or any other counters. Aim of the game: The player who takes the last counter loses. Editor's notice: The second player can always win, that makes Nim a distinctly 'impartial game'.

SOLUTION The traditional Nim-game (aka Marienbad-game) consists of four rows of 1, 3, 5 and 7 matchsticks (or any other objects). Two players take any number of matchsticks from one row alternately. The one, who takes the last matchstick loses.

The winning strategy is:
You must always take as many matchsticks as possible so that the “Nim sum” of the rows remains ZERO.

What is a “Nim sum”?
Count the matchsticks in each row... And convert them mentally in multiples of 4, 2 and 1. Then, CANCEL pairs of equal multiples, and add what is left. So, when starting, the “Nim sum” of the rows is:

 Row1 = 1 = 1 x 1 = 1 = 1 Row2 = 3 = 1 x 2 + 1 x 1 = 2 1 Row3 = 5 = 1 x 4 + 1 x 1 = 4 1 Row4 = 7 = 1 x 4 + 1 x 2 + 1 x 1 = 4 2 1 Total of UNPAIRED multiples = 0 0 0

As you can see, there are currently TWO 4’s, TWO 2’s, and FOUR 1’s (= TWO + TWO + FOUR = 8). You have then an EVEN number of multiples, the remainder after dividing this number (8) by 2 gives 0.

To win at Nim-game, always make a move, whenever possible, that leaves a configuration with a ZERO “Nim sum”, that is with ZERO unpaired multiple(s) of 4, 2 or 1. Otherwise, your opponent has the advantage, and you have to depend on his/her committing an error in order to win.

How to leave a zero “Nim sum”:
Your opponent moves and leaves you the following configuration:

 Row1 = 1 = 1 x 1 = 1 Row2 = 3 = 1 x 2 + 1 x 1 = 2 1 Row3 = 5 = 1 x 4 + 1 x 1 = 4 1 Row4 = 5 = 1 x 4 + 1 x 1 = 4 1 Total of unpaired multiples = 0 1 0

Get rid of ONE 2, by taking 2 matchsticks from the 2nd row. That leaves your opponent at 1, 1, 5, 5 which is, for him, a losing configuration...

 Row1 = 1 = 1 x 1 = 1 Row2 = 1 = 1 x 1 = 1 Row3 = 5 = 1 x 4 + 1 x 1 = 4 1 Row4 = 5 = 1 x 4 + 1 x 1 = 4 1 Total of unpaired multiples = 0 0 0

Every time you leave your opponent a zero “Nim sum” configuration, you increase your chances to win! Here below are listed all the possible zero “Nim sum” configurations (sometimes, the order has no importance, for example: 3, 3, 1, 1 or 3, 1, 3, 1 has the same result). You can print the table and use it as a cheat sheet... But you can also improve your concentration skills by practicing “Nim sums” mentally!

 four rows three rows two rows 7, 4, 2, 1 6, 5, 2, 1 6, 4, 3, 1 5, 5, 1, 1 4, 4, 1, 1 3, 3, 1, 1 2, 2, 1, 1 7, 5, 2 7, 4, 3 6, 5, 3 6, 4, 2 5, 4, 1 3, 2, 1 1, 1, 1 5, 5 4, 4 3, 3 2, 2 Source: © G. Sarcone, www.archimedes-lab.org

Final considerations
As you can see, the starting configuration 1, 3, 5, 7 is a losing one for the player who starts the game. Furthermore, the player who starts the game first will obviously lose if his opponent takes care to keep during the whole game play a zero “Nim sum” configuration. In conclusion, it is ALWAYS disadvantageous to start the game first! Play now at Nim game against your computer!  Behind the challenge
You have learned that the key to win at Nim-game is the binary digital sum (Nim sum). This operation is also known as 'exclusive or' (xor) addition. Your scientific calculator can be of help to find any “Nim sum” of two or more integers thanks to its XOR operator button. To 'xor' or 'Nim-add' several numbers, just type into your calculator the first number then press the XOR button and type the following number to 'Nim-add', and so on... When you have entered all the numbers, press the equal sign, as follows:
1 xor 3 xor 5 xor 7 = 0

If you don’t have any scientific calculator you can use this online XOR calculator.

How does a XOR logic operator work?
The “Nim sum” of two (or more) integers is calculated by means of ‘xor’ bitwise operator (symbol ⊕). In logic,
a xor b = [(a or b) and (not (a and b))]
In other words, a ‘xor’ bitwise operation returns a 1 in a bit position if bits of one but not both operands are 1’s. For instance:
1012 -> 510 number A
1112 -> 710 number B
----
0102 -> 210 The “Nim sum” of numbers A and B, 5 ⊕ 7 = 2

Another example:
01112 ->   710 number B
10112 -> 1110 number C
-----
11002 -> 1210 The “Nim sum” of numbers B and C, 7 ⊕ 11 = 12

XOR logic operator in the graphic design world Graphic designers who work with vector-based softwares use a pathfinder feature, similar to the XOR operator, to get rid of everything is overlapped. For example, when 2 shapes are overlapped as shown in fig. a, the XOR button in the Adobe Illustrator pathfinder tool (called “exclude overlapping shape areas” button, see fig. below) allows to exclude any shape areas that were overlapping at all, like illustrated in fig. b.  All the Most Wanted Puzzle Solutions in a look!   Any comment? Any suggestion? Contact us! Game involving counting skills! Buy the book 'Creating Nim games' here  You cannot reproduce any part of this page without prior written permission
Archimedes' Laboratory™ | [email protected] About Us | Sponsorship | Press-clippings | [email protected] | ©opyrights | Link2us | Sitemap
© Archimedes' Lab | Privacy & Terms | The web's best resource for puzzling and mental activities   