All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
3x3 Nim (Posted on 2009-06-25) Difficulty: 3 of 5
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?

See The Solution Submitted by Jer    
Rating: 4.0000 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips nim value equivalents | Comment 24 of 26 |

The game board is not modified by rotating or reflecting it, obviously.  It is also not affected by permuting the rows or colums.  The two boards below are equivalent, differing only in the permutation of rows and columns:

X..  XX.
XXX  X..

This can be applied to all game boards to reduce the number of cases to a core of 26.  Each board is labeled with an ID, the nim value of the board, and a list of boards which are results of legal moves.  The nim value is calculated by looking at the nim values of the possible results of legal moves and finding the smallest number not in that list.

...  ...  ...  ...  ...  ...   ...   X..
...  ...  ...  X..  ...  X..   X..   .X.
...  X..  XX.  .X.  XXX  .XX   XX.   ..X
Z    A    B1   B2   C1   C2    C3    C4
0    1    2    0    3    3     3     1
     Z    Z,A  A    Z,A  A,B1  A,B1  B2
                    B1   B2    B2

...    ...    ...    X..    ..X    ...    X..    XX.    ..X    X..
X..    XX.    XX.    X..    XX.    XX.    X..    .XX    XX.    XX.
XXX    XX.    .XX    .XX    .X.    XXX    XXX    .X.    XX.    .XX
D1     D2     D3     D4     D5     E1     E2     E3     E4     E5
4      0      1      0      2      5      1      5      1      4
A,B1   B1,C3  B1,B2  B1,C2  B2,C2  B1,C1  B1,C1  B2,C2  C2,D2  C3,D3
B2,C1         C2,C3         C3,C4  C2,C3  C2,D1  C3,C4  D5     D4,D5
C2,C3                              D1,D2  D4     D1,D3
                                   D3            D5

...    X..    X..    .XX    X..    XX.    XX.    XXX
XXX    XX.    XXX    X.X    XXX    X.X    XXX    XXX
XXX    XXX    .XX    XX.    XXX    XXX    XXX    XXX
F1     F2     F3     F4     G1     G2     H      I
1      0      6      0      2      2      3      0
C1,D1  C3,D1  C2,D1  D3,E5  D1,D2  D3,E1  E1,F1  F1,G1
D2,E1  D3,D5  D2,D3         E1,E2  E3,E5  F2,F3  H
       E1,E2  D4,D5         E3,E4  F2,F3  G1,G2
       E3,E5  E1,E3         F1,F2  F4
              E4,E5         F3

The zero nim values I calculated are the full board (I), the empty board (Z), and boards B2, D2, D4, F2, and F4.

  Posted by Brian Smith on 2009-06-29 01:15:18
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information