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?

  Submitted by Jer    
Rating: 4.0000 (7 votes)
Solution: (Hide)
The beginning position (9 counters) is a losing position so the second player has a winning strategy.

This strategy is to always take the board to one of 20 losing positions shown below.

Every position with 1, 3, 5, 7, or 8 is a winning position so the second player must make the board become of the following positions with 2, 4, or 6:

X-- X-- X-- -X-
-X- --X --- X--
--- --- --X ---

These are positions with 2 counters on different columns/rows.

XX- XX- XX- X-X X-X -X-
XX- --X --- -X- --- X-X
--- --X XX- -X- X-X -X-

These positions are transformable to either the first or second by shifting row/columns.

-XX X-X --X --X --X --X -X- -X- X-X
X-X -XX -XX X-X XXX XXX -XX XXX --X
XX- XX- XXX XXX -XX X-X XXX -XX XXX

These positions have 3 empty spots either in 3 rows/columns or in 2 rows/columns.

In essence, then, there are 5 positions to memorize to be able to always force a win as the second player.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Math Strategy?Adrian Mason2013-03-26 00:03:43
Solutioni had to...Joselyn2010-01-01 07:43:30
Hints/Tipsnim value equivalentsBrian Smith2009-06-29 01:15:18
misère formCharlie2009-06-28 14:13:44
SolutionsimplificationCharlie2009-06-27 13:48:38
Strategeryed bottemiller2009-06-26 23:18:15
re(3): computer solutionpcbouhid2009-06-26 18:15:51
re(2): computer solutionCharlie2009-06-26 16:03:26
re: computer solutionpcbouhid2009-06-26 12:08:12
Solutioncomputer solutionCharlie2009-06-26 09:50:05
re(3): tes he can revisitedCharlie2009-06-26 09:45:54
Some Thoughtsre(2): tes he can revisitedAdy TZIDON2009-06-26 06:23:56
Some ThoughtsI agreeAdy TZIDON2009-06-26 06:08:05
re: tes he canbrianjn2009-06-26 00:53:44
re(3): tes he canbrianjn2009-06-26 00:50:44
re(2): Winning Strategy (spoiler)Steve Herman2009-06-25 21:55:12
Winning Strategy (for the wrong problem)Steve Herman2009-06-25 21:42:42
re: Winning Strategy (spoiler)Charlie2009-06-25 17:05:26
re: Winning Strategy (spoiler)Jer2009-06-25 17:02:11
SolutionWinning Strategy (spoiler)Steve Herman2009-06-25 16:18:07
re: tes he canCharlie2009-06-25 14:33:36
re(2): tes he canpcbouhid2009-06-25 13:42:27
re: yes he canbrianjn2009-06-25 12:50:00
re: tes he canbrianjn2009-06-25 12:45:19
Questionyes he canAdy TZIDON2009-06-25 11:48:26
Solutiontes he canAdy TZIDON2009-06-25 11:45:01
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


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

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information