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
    $\begingroup$ @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. $\endgroup$ – HenrikRueping Nov 22 '12 at 15:42
  • $\begingroup$ 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. $\endgroup$ – mercio Nov 22 '12 at 16:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Mike Nov 22 '12 at 17:00
  • $\begingroup$ The sequence is not in the OEIS (!!). $\endgroup$ – dot dot Nov 22 '12 at 17:12
  • $\begingroup$ @HenrikRueping Ah okay, I misunderstood that. $\endgroup$ – tomglabst Nov 22 '12 at 17:27

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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.