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
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:
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
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:
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)
summing up the rows: 110
summing up the columns: 101
110 != 101......... a winning position.
The player who left the configuration exemplified by Charlie:
summing up the rows: 001
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