3
$\begingroup$

Bob and Susan play a game on an $a\times b$ board by alternating turns. In each turn, the player chooses a square comprising only uncolored cells, and color all of the cells. The first player who is unable to move loses the game. If Bob starts, for which $(a,b)$ can he win?

If $a=b$, then clearly he can win by choosing the whole board. Otherwise, say $a<b$, one choice is to color an $a\times a$ square and leave Susan with an $a\times (b-a)$ board, so this points to an induction approach. But Bob can also color any $c\times c$ square for $c<a$, which does not leave a rectangle and therefore induction cannot apply.

$\endgroup$
  • $\begingroup$ @HagenvonEitzen Yes $\endgroup$ – nan Jan 24 '16 at 20:14
3
$\begingroup$

If b>a, and (b-a) is even, then the first player can win by leaving two equal strips either side of his initial move (of a square of side a) and then using a strategy stealing argument.

If b>a, and (b-a) is odd, then a first move of a square of side a-1 can leave two equal strips either side and a strip of height 1 above the square. If a-1 is even, the first player can again use a strategy stealing argument to win, I believe.

-EDIT- If a=1, in the above scenario, then b is even and player 1 will lose (thanks to TonyK for pointing that out)

So the only other options to consider would be when b>a with b being odd and a being even.

$\endgroup$
  • $\begingroup$ Looks good so far (except that your second paragraph is wrong when $a=1$). $\endgroup$ – TonyK Jan 24 '16 at 19:36
  • 1
    $\begingroup$ @TonyK The outcome $1\times b$ does not even depend on the player's moves: Bob wins if $b$ is odd and Susan wins if $b$ is even. Hence $a=1$ is not just a gap in the proof but in fact leads to a win fo Susan $\endgroup$ – Hagen von Eitzen Jan 24 '16 at 19:40
  • $\begingroup$ @HagenvonEitzen: Yes, obviously. If the first player can't win then the second player can. $\endgroup$ – TonyK Jan 24 '16 at 19:42
1
$\begingroup$

I posted a comment to the effect that this looked like a very difficult problem to me. Then Penitent's answer seemed to cover most cases, so I deleted my comment. Now I have changed my mind again $-$ it's difficult!

According to Penitent's answer, assuming $b > a$ the only unresolved case is $b$ odd and $a$ even. Let's look at the simplest case of this: $a=2$. So we start with a $2 \times b$ grid, and we want to know whether the first or the second player wins.

This is a case for Sprague-Grundy theory. Let $v_b$ denote the Sprague-Grundy value of the $2 \times b$ starting position. There are no moves from the $2 \times 0$ position, so $v_0 = 0$. From position $2 \times b$, we have two options: we can colour a $2 \times 2$ square, leaving a $2 \times k$ block and a $2 \times (b-k-2)$ block for some $k$; or we can colour a $1 \times 1$ square, leaving a $2 \times k$ block, a $2 \times (b-k-1)$ block, and a $1 \times 1$ square. The first option leads to a Sprague-Grundy value of $v_k \oplus v_{b-k-2}$; the second option leads to a Sprague-Grundy value of $v_k \oplus v_{b-k-1} \oplus 1$ (here $\oplus$ is the exclusive-or operator).

So according to the theory, the Sprague-Grundy value of a $2 \times b$ block is the minimum excluded value (or mex) of $v_k \oplus v_{b-k-2}$ and $v_k \oplus v_{b-k-1} \oplus 1$ over all allowable values of $k$. We can calculate these values efficiently, and they look like this:

0,0,2,2,1,4,3,3,1,4,2,6,
5,0,2,7,1,4,3,3,1,4,7,7,
5,0,2,8,4,4,6,3,1,8,7,7,
5,0,2,2,1,4,6,3,1,8,7,7,...

A position is a win for the first player unless this value is $0$.

Just as an example, the value $v_5=4$ is the mex of:

$v_0 \oplus v_3 = 0 \oplus 2 = 2$
$v_1 \oplus v_2 = 0 \oplus 2 = 2$
$v_0 \oplus v_4 \oplus 1 = 0 \oplus 1 \oplus 1 = 0$
$v_1 \oplus v_3 \oplus 1 = 0 \oplus 2 \oplus 1 = 3$
$v_2 \oplus v_2 \oplus 1 = 2 \oplus 2 \oplus 1 = 1$

I have displayed the values in rows of twelve because after a short while, the sequence seems to settle down to being periodic with period $12$. I don't have a proof of this, but it's the sort of thing that Sprague-Grundy sequences do. If true, then the situation for $a=2$ is this:

The starting position $2 \times b$ is a win for the first player unless $b$ is zero, or $b \equiv 1 \bmod 12$

Such a simple result is possible only because of the simple nature of the starting position. Once we allow $a \ge 4$, then the playing area can become arbitrarily complicated, and an analysis like the above is impossible.

$\endgroup$

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.