Berkeley Math Circle Monthly Contest 3

Solution:

The answer is all pairs $(m, n)$ such that the ratio
$$R=\frac{m+1}{n+1}$$
is an integer power of two, that is, the pairs $\left(a-1,2^{k} a-1\right)$ and $\left(2^{k} a-1, a-1\right)$ for $a \geq 2$ and $k \geq 0$. We will show that

a. If $R$ is a power of two, then it will not remain so after one move;

b. If $R$ is not a power of two, then some move will make it one.

To prove (a), simply note that at each move, one of the dimensions is decreased at most by half, so either $m+1$ or $n+1$ is diminished by a factor strictly between 1 and 2. Thus the new value of $R$ is sandwiched between two powers of two: $R / 2$ and $R$ in the first case, $R$ and $2 R$ in the second.

As for (b), assume $m \geq n$ (the other case is symmetric) so $2^{k}<R<2^{k+1}$ for some $k \geq 0$. We have
$$2^{k}(n+1)<m+1<2^{k+1}(n+1) \text{.}$$
These inequalities imply that one can move to a bar that is $\left[2^{k}(n+1)-1\right] \times(n+1)$, with $R$-value $2^{k}$.

If $R$ is initially a power of two, Ben wins by making it that way at each move; otherwise Art wins by the same strategy (in either case ending at the $1 \times 1$ square, where $R=1$ ).