Game with coloring squares in rectangular board

Question

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.

Answer 1

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.

Answer 2

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.