Game with coloring squares in rectangular board 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.

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.