Re: NIM-game
Posted: 19 Oct 2011 20:55
Last time I was there, which was awhile ago, he eventually felt sorry for me after too many failed attempts, so he allowed me leave.
Actually, it is quite simple. The outcome depends totally on who starts the game. What you've got to do is; turn the numbers from decimal system into the binary system. The fastest and easiest way is to re-roll, until you get 3 heaps of stones. Write down your numbers in a row (Windows calculator can turn them for you from deci to bin)
Lets assume you've got something like e.g
1001 (1st pile= 9)
1100 (2nd pile= 12)
1011 xor (3rd pile= 11)
---------
1110
How to perform xor? Basicly if the quantity of '1's in a row can be divided by 2, the result of a row is '0'. If not, then it is '1'. To win the game, you've got to take away enough stones to guarantee the result of the xor is 0 in each row. This can be always done, if you start first. In other words, you need to transform any of the lines in such way, that the number of '1's in each row can be devided by 2. For 3 piles it means that there are either two '1's or none of them in each row.
For instance we are going to transform 1001 (9) ---> 0111 (7) - just remember you cannot transform it into a higher number.
This gives us the following:
0111
1100
1011 xor
----------
0000
The result is OK, as we've got the total outcome of '0', which means we've got to take 2 stones from the first heap, because 1001(9)-0111(7)= 2. You've got to follow the pattern, until your next move is going to result in no heap of size 2 or higher. When this occurs, you just need to make sure you leave either 1 or 3 heaps with 1 stone (for 3 piles), (1,3 for 4), (1,3,5) for 5 piles. Which is why it is fastest to re-roll until you've got 3 heaps. Hope this helps. This is if course very simplified way. I'm sure anyone who has at least slight idea on how the binary system works, can easily figure it out from the information provided by wikipedia.
Actually, it could be explained in a much simpler way. But I believe we are now getting close to actually posting explicit quest solutions here (I think the NIM game is part of a quest).