IMO 1J, Mock Exam 2

The answer is all $(m, n)$ satisfying $3 \mid mn$.

Construction: Without loss of generality assume $3 \mid m$. When $2 \mid n$, we can flip all coins using the method shown in the left figure:

When $2 \nmid n$, first use the above method to flip all coins in the left $m \times (n-1)$ portion to heads-up, leaving the rightmost column tails-up. Next, let $L(i, j)$ denote the $L$-shaped operation that flips the coins at positions $(i, j)$, $(i+1, j)$, and $(i, j+1)$, and let $R(i, j)$ denote the operation that flips the coins at positions $(i, j)$, $(i, j-1)$, and $(i-1, j)$. Then note that the three consecutive operations $R(i, n)$, $R(i+1, n)$, $L(i, n-1)$ will flip the coins at the three positions from $(i-1, n)$ to $(i+1, n)$ while keeping all other coins unchanged, so we can use this method to also flip the rightmost column to heads-up.

Bound: Assign values to the grid as shown in the figure on the right, and let $T(i)$ be the total number of heads-up coins in the cells assigned the value $i$. Note that initially $T(0) = T(1) = T(2) = 0$, and in each move, the parities of $T(1) - T(0)$ and $T(2) - T(1)$ never change. This means we always have $T(0) \equiv T(1) \equiv T(2) \pmod{2}$. In other words, in order to be able to flip all coins to heads-up, the numbers of cells assigned the values 0, 1, and 2 must have the same parity. However, direct computation shows that:

- When $mn \equiv 1 \pmod{3}$, we have $T(0) - 1 = T(1) = T(2) = \frac{mn-1}{3}$;
- When $mn \equiv 2 \pmod{3}$, we have $T(0) - 1 = T(1) - T(2) = \frac{mn-2}{3}$.

Therefore $3 \mid mn$ is a necessary condition for being able to flip all coins to heads-up.