A 3x3 array of counters is laid out. Players take turns removing counters. The rule for removing counters is to pick a row or column and take any 1,2 or 3 from it. Whoever removes the last counter wins.

Does the first or second player have a winning strategy?
What is this strategy?

(In reply to computer solution by Charlie)

I recall that the winning strategy for the Game of Nim is achieved using the binary system:

The initial configuration is:

               *
             *  *
           *  *  *
         *  *  *  *
       *  *  *  *  *

The rule was: you are allowed to remove any number of counters from just one row and the player who removes the last counter loses. (opposite from the problem im question).

The strategy is as follows:

Write the numbers of counters in each row, in binary system:

line1: 001
line2: 010
line3: 011
line4: 100
line5: 101

Sum up these numbers, without carrying. We achieve:
in the first column, 0+0+0+1+1=0
in the second column, 0+1+1+0+0=0
in the third column, 1+0+1+0+1=1

or: 001

The player who leaves 000 (in his play) always win. So, to the first player to win, he must leave 000, which he can achieve removing, for example, the unique counter in the first row, leaving in:
line1: 000
line2: 010
line3: 011
line4: 100
line5: 101

Now, summing up the columns (always without carrying) we have 000, a winning position.

And so forth.

It seems, at first sight (I confess that I didnīt analyze all the winning positions Charlie achieved, that a winning position (since the actual problem is the opposite of the one I described) must not present the same number when summing up the rows and the columns, written as a binary number.

For example: the configuration Charlie indicated as 457, using the binary value of the rows:

*                100 (4)
*    *          101 (5)
* * *          111 (7)

row1: 100
row2: 101
row3: 111

summing up the rows: 110

column1: 111
column2: 001
column3: 011

summing up the columns: 101

110 != 101......... a winning position.

The player who left the configuration exemplified by Charlie:

      *
*    *
*    *

row1: 001
row2: 101
row3: 101

summing up the rows: 001

column1: 011
column2: 000
column3: 111

summing up the columns: 100 (which is the same as 001, the order of digits doesnīt matter).

Thus, this is a loser configuration.

I donīt know if I make myself clear and doesnīt even know if my assumption (for this problem) based in the strategy for the Game of Nim, is right.

Just a thought to be confirmed.

Posted by pcbouhid on 2009-06-26 12:08:12