The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
DrJones
Daedalian Member

Posted: Fri May 27, 2005 11:04 pm    Post subject: 1

Nim is a well-known game usually played with three heaps of elements, in which players are required to take any number of elements from any single heap. The player which takes the last element loses the game.

There have been many variations of this game, limiting the number of elements a player can take, or the number/size of the heaps. However, there has been found a simple winning strategy for all of them.

I was wondering if there's a general winning strategy for any kind of Nim games, so I came up with this 2-dimensional variation.

1. The start position is a 10x10 array of elements, like the following:
 Code: 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111

2. During each player's turn, that player may choose a row or column, and take any number (greater than zero, of course) of consecutive elements of the array, for example:

 Code: 1111111111      1111111111 1111110111      1111111111 1111110111      1111111111 1111110111  or  1111111111 1111110111      0000000011 1111110111      1111111111 1111111111      1111111111

3. The following example is not a valid move, because the elements aren't consecutive:

 Code: 1111111111        1111111111 1111110111        1111110111 1111110111        1111110111 1111110111  then  1111110111 1111110111        0000000001 1111110111        1111110111 1111111111        1111111111

4. The player who has to take the last element loses the game.

Sorry if the explanation is poor.

Do you think this variation would affect in some noticeable way the winning strategy for this game?
Lucky Wizard
Daedalian Member

 Posted: Sun May 29, 2005 5:45 am    Post subject: 2 That game's actually been proposed before; it's called Tac Tix. In chapter 15 of Martin Gardner's "Hexaflexagons and other Mathematical Diversions" he discusses both Nim and Tac Tix. For nim, he discusses a simple strategy that works regardless of how many heaps or elements there are. For Tac Tix, he says there's no simple strategy, and that it is very difficult to analyze 4x4, so 10x10 is no doubt even more difficult.
DrJones
Daedalian Member

 Posted: Sun May 29, 2005 9:44 am    Post subject: 3 Thank you very much, your answer surpassed my expectations. I'm surprised that you even know the chapter's number. Do you have the book, or it just appeared on a web search?
Lucky Wizard
Daedalian Member

 Posted: Tue May 31, 2005 4:51 am    Post subject: 4 Yeah, I have the book (it was in this room actually). By the way, Piet Hein invented Tac Tix. And by the way, people have undertaken the task of analyzing 4x4 Tac Tix; the second player has the win in that.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersDrJonesLucky Wizard Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum