18
$\begingroup$

Here is a simple game I've invented (if the idea is not fresh, then please let me know):

The game is played on a board. The board has some (finite) number of lines drawn on it. A pawn is placed on each intersection point of (two or more) lines. Two players take alternate turns removing pawns. On each turn, a player removes one or more pawns. All pawns removed in a single turn have to be taken from the same line. The player who cannot make a move loses (alternatively: the player who takes the last pawn wins).

Here is my question: For what values of m and n does the player who begin have a winning strategy when the game is played on an $n\times m$ rectangular grid?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ The game on a rectangular or triangular board is called "Two-Dimensional Nim" by Aviezri Fraenkel in "The Lighter Side of Mathematics: Proceedings of the Eugène Strens Memorial Conference." Fraenkel organized combinatorial game displays at the conference, and suggested the $3 \times 5$ board as a good one to play. It is not the same game as the one called "Two-Dimensional Nim" in Winning Ways. Some results are given without proof by Jim Ferry at the discussion groups.google.com/forum/#!topic/sci.math/-EHfgnl74_0 $\endgroup$
    – Zack Wolske
    Commented Nov 5, 2014 at 21:49
  • $\begingroup$ In particular, in response to your specific question, one of the messages in the link says that the first player has a winning strategy in the $3\times 5$ and $3\times 7$ cases. $\endgroup$
    – Gabriel C. Drummond-Cole
    Commented Nov 6, 2014 at 4:50

1 Answer 1

Reset to default
20
$\begingroup$

Here is a partial answer. I'll assume $m$ and $n$ are the number of intersections rather than the number of squares.

If both values are even, then the second player can always win by rotating the first player's previous move by 180 degrees.

If precisely one value is odd, then the first player can win by removing one row or column, making it even by even.

Obviously if $m$ or $n$ is $1$ then the first player can win.

I expect the general odd by odd case to be much harder because $3\times 3$ is a second player win by case analysis and the strategy appears to have no symmetry. Also the Sprague-Grundy values of the subsets of the $3\times 3$ square do not seem to have any easy pattern.

I think if you want more information the right thing to do is to write a plugin for cgsuite (easier than it sounds) and analyze the low odd cases and their subsets to see if you can find a pattern in the Sprague-Grundy values.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .