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.

  • 1
    @tomglabst: The game would be over if each remaining square is adjacent to some cross. Then no player can make any cross. Thus in your example the game would end after the first move. Specifically "P1 crosses any remaining square". There are no squares left that any player could cross.2012-11-22
  • 0
    I think I've seen a variant of the $m=1$ game where there's a modulus $M$ such that the grundy number of the game only depends on $n$ modulo $M$. So it's a possibility that such an $M$ exists here too.2012-11-22
  • 1
    @AndréNicolas The OP has noted values of $m$, where the first player has no winning strategy, and 6 is not among them. I see no edits made either.2012-11-22
  • 0
    The sequence is not in the OEIS (!!).2012-11-22
  • 0
    @HenrikRueping Ah okay, I misunderstood that.2012-11-22
  • 0
    If the first player does not have a winning strategy for 1xn, then they **do** have a winning strategy for 1x(n+2) (consider what happens if you place a cross in the right-most square of a n+2 grid). You will also have a winning strategy for a 1x(n-2) grid (imagine that the other player started by placing a cross in the right-most square of a 1xn grid).2012-11-22
  • 0
    So the 2 by $n$ case might be the next interesting thing to look at...2012-11-23
  • 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...