wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> NIM game
        
(Message started by: Altamira_64 on Apr 29^th, 2012, 1:32pm)

Title: NIM game
Post by Altamira_64 on Apr 29^th, 2012, 1:32pm

Force the other player to take the last matchstick. In this game there will be 9 rows of matchsticks: First row has 1 matchstick, second has 2 etc and last one has 9 and the two players alternate to take matchsticks from the rows. Each time a player can take any number of matchsticks from any one row, but he cannot take matchsticks from multiple rows. The one who is forced to take the last matchstick loses.
What is the strategy to always win the game?

Title: Re: NIM game
Post by towr on May 8^th, 2012, 2:59am

If you take the bitwise exclusive or (xor) of the binary representation of the counts of the number of matchsticks in each row, it should be 0 after your move, except when it would leave all the remaining rows with just one matchstick, in which case you should leave an odd number of rows.
Since we start with an xor of 1 (and some rows have more than 1 matchstick), this means we can win.

This the regular nim strategy.

Title: Re: NIM game
Post by Altamira_64 on May 8^th, 2012, 10:09am

Wow!
So I assume we write all the numbers from 1 to 9 in binary, that is:

0001
0010
0011
0100
0101
0110
0111
1000
1001

So the xor sum is 0001.
My first move is, for example, to take one matchstick from the last row and leave 8 (xor=0) and so on?

Title: Re: NIM game
Post by towr on May 8^th, 2012, 12:12pm

Yes.
(Just be sure to remember that the rule changes for the last moves: when there are only rows with a single matchstick left it must be an odd number)