How to play a winning move at this Nim board?

200 Views Asked by At

assuming that I have this situation at Nim:
1,6,12,34,45,23,56,101,212

If I understand right, the is a winning situation because the Nim number is: 154. This is the binary numbers of the piles: '00000001', '00000110', '00001100', '00100010', '00101101', '00010111', '00111000', '01100101', '11010100'.
When I do addition without carry (XOR) - I got the result - 10011010 = $154$.

So first of all I want to know if I'm right, and then I trying to understand what is the next move that will bring the Nim-Value to $0$, but I don't understand how to to so this.
If I'm taking 154 from the 212 pile, it's still not $0$...

Can you help me please?

Thank you!

2

There are 2 best solutions below

0
On BEST ANSWER

You do not want to subtract 10011010 from a heap, you want to XOR a heap with 10011010, that is, you want to turn the 11010100 heap into 11010100 $\oplus$ 10011010 = 01001110.

0
On

You are right to take beans from the 212 heap, but not because 212 is arithmetically greater than 154. Rather, the key property is that 212 and 154 each have the same maximum power of 2 contained within them, namely 128. Therefore, you are sure that the XOR combination of 212 with 154 will be less than 128, and so you can reach the required winning condition by removing beans instead of having to add them.

The XOR combination has already been done by Hagen von Eitzen, giving $212\oplus154=78$, so you would remove 134 beans from the 212 heap.