5
$\begingroup$

I'm interested in the following game:

Given a rectangular board consisting of $n\times m$ unit squares, two players alternate coloring squares composed of uncolored unit squares. The player that is unable to color a square loses the game.

What is known:

  • If $n=m$, then the first player wins by coloring the entire board. If $n=1$, then the first player can win unless $m\equiv 0\pmod{2}$, where the second player wins. Therefore, from now on we assume $1\lt n\lt m$.

  • If $n,m$ are of equal parity (both odd or both even), then the first player can color a $n\times n$ square in the center of the board which leaves us with two equal separated boards. By symmetry, the first player proceeds to mirror the moves of the second player across those two boards, to win.

  • If $n$ is odd and $m$ is even, then the first player can color a $(n-1)\times (n-1)$ square in the center of the board which leaves us with two equal separated boards and a $1\times(n-1)$ strip next to the colored square. By symmetry, the first player proceeds to mirror the moves of the second player across those two boards and across the two halves of the strip, to win.

This leaves us with the case when $n$ is even and $m$ is odd.

But when $n\gt 2$, this is apparently a hard problem.

Does this game have a name and had anyone attempted to solve it in the past?

What strategies can be used to try to solve the remaining case?

I did not find anything relevant other than the linked answer above, hence I am asking this question. Note that the linked question is not a duplicate since the author decided to ignore the "(even, odd) case" by accepting a partial answer.

$\endgroup$
5
  • $\begingroup$ It's somewhat similar to Chomp, so the references in the Chomp wikipedia article might be a place to start: en.wikipedia.org/wiki/Chomp $\endgroup$ Sep 5 '20 at 0:10
  • $\begingroup$ Also, isn't the definition of the game symmetric in $n, m$, so isn't "$n$ odd, $m$ even" the same as "$n$ even, $m$ odd" (mirrored across the diagonal)? Or am I misreading something? $\endgroup$ Sep 5 '20 at 0:12
  • 1
    $\begingroup$ @QiaochuYuan It is stated in the first bullet point after the trivial cases are handled. $\endgroup$
    – Vepir
    Sep 5 '20 at 0:24
  • $\begingroup$ Ah, there it is, thank you. $\endgroup$ Sep 5 '20 at 0:25
  • $\begingroup$ @QiaochuYuan Other than Chomp, it appears to be the same as Cram (found it here), except we are using squares of any size instead of $1\times 2$ (or $2\times 1$) rectangles (dominoes). $\endgroup$
    – Vepir
    Sep 10 '20 at 12:39

Your Answer

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

Browse other questions tagged or ask your own question.