20
$\begingroup$

Suppose two players play the following game on a $m$ by $n$ rectangle. Alternatingly they have to make a cross in some empty $1\times 1$ square. They are not allowed to make a cross next to another cross (Diagonally is OK, not just right next to each other). The player who places the last cross wins.

Now the question is for which $m,n$ does the starting player have a winning strategy?

At first I thought this might be just a nice exercise. So I had a look at 1 by $n$ rectangles first. A computer programme computed that the first player does not have a winning strategy for $n=4,8,14,20,24,28,34,38,42,54,58,62,72,76,88,92,96,106,110$ (for $n\le 110$).

I do not see any pattern in these numbers. So the answer might not be so easy.

The starting player can always win for odd $n$. He just places a cross in the middle and mirrors all the moves of the second player.

  • 0
    Even by even is always a win for the second player (he can always play the move central symmetric to the last one). And similar to this odd by odd is always a win for the first player (play the central position, and mantain central symmetry).2012-11-23

1 Answers 1

11

The $n \times 1$ version is Dawson's Chess. The OP's sequence is A215721 in the OEIS, after adding 1 to each term. I wrote a program too, and found that the proportion of losing initial positions seems to tend to a constant -- there are 1473 losing positions in the first 10000, and 14709 losing positions in the first 100000. I found an explanation at "Sprague-Grundy values for Dawson's Chess" (A002187 in the OEIS):

Has period 34 with the only exceptions at n=0, 14, 16, 17, 31, 34 and 51.

5/34 is 0.14705...