Most Wanted Puzzle Solutions

"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

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:

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:

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...

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!

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:
101₂ -> 5₁₀ number A
111₂ -> 7₁₀ number B
----
010₂ -> 2₁₀ The “Nim sum” of numbers A and B, 5 ⊕ 7 = 2

Another example:
0111₂ ->   7₁₀ number B
1011₂ -> 11₁₀ number C
-----
1100₂ -> 12₁₀ 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!