We claim the answer is $3\mid mn.$ For the construction, the idea is that it is possible to flip a $3\times 1$ rectangle, with the following steps: [asy][asy] size(10cm); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle); draw((5,0)--(8,0)--(8,2)--(5,2)--cycle); draw((10,0)--(13,0)--(13,2)--(10,2)--cycle); draw((15,0)--(18,0)--(18,2)--(15,2)--cycle); draw((3.5,1)--(4.5,1),Arrow); draw((8.5,1)--(9.5,1),Arrow); draw((13.5,1)--(14.5,1),Arrow); filldraw((7,0)--(8,0)--(8,2)--(6,2)--(6,1)--(7,1)--cycle,gray); draw((7,0)--(8,0)--(8,2)--(6,2)--(6,1)--(7,1)--cycle,linewidth(1.5)); filldraw((11,0)--(12,0)--(12,2)--(13,2)--(13,1)--(11,1)--cycle,gray); draw((11,0)--(13,0)--(13,1)--(12,1)--(12,2)--(11,2)--cycle,linewidth(1.5)); filldraw((15,1)--(18,1)--(18,2)--(15,2)--cycle,gray); draw((16,0)--(17,0)--(17,2)--(15,2)--(15,1)--(16,1)--cycle,linewidth(1.5)); draw((1,0)--(1,2)); draw((6,0)--(6,2)); draw((11,0)--(11,2)); draw((16,0)--(16,2)); draw((2,0)--(2,2)); draw((7,0)--(7,2)); draw((12,0)--(12,2)); draw((17,0)--(17,2)); draw((0,1)--(3,1)); draw((5,1)--(8,1)); draw((10,1)--(13,1)); draw((15,1)--(18,1)); [/asy][/asy] Then if $3\mid mn,$ it is possible to cut the rectangle into $3\times 1$ strips and flip all of them. (This doesn't run into space issues since $m,n\ge 2.$) To show this is necessary, color the cell $(x,y)$ with the remainder when $2x+y$ is divided by $3.$ Then each move flips one cell of each color, and thus the number of heads-up coins of each color must always have the same parity. Thus we show that for $3\nmid mn$ there exist two colors that appear different-parity numbers of times. To do this, first cut the rectangle into four pieces, three of which have at least one side length divisible by $3$ and the fourth has both dimensions $<3.$ An example is as shown: [asy][asy] size(7cm); draw((0,0)--(7,0)--(7,5)--(0,5)--cycle); draw((1,0)--(1,5)); draw((2,0)--(2,5)); draw((3,0)--(3,5)); draw((4,0)--(4,5)); draw((5,0)--(5,5)); draw((6,0)--(6,5)); draw((0,1)--(7,1)); draw((0,2)--(7,2)); draw((0,3)--(7,3)); draw((0,4)--(7,4)); draw((-1,2)--(8,2),linewidth(2)); draw((1,-1)--(1,6),linewidth(2)); label("0",(0,0),dir(44)*2.9); label("1",(0,1),dir(44)*2.9); label("2",(0,2),dir(44)*2.9); label("0",(0,3),dir(44)*2.9); label("1",(0,4),dir(44)*2.9); label("2",(1,0),dir(44)*2.9); label("0",(1,1),dir(44)*2.9); label("1",(1,2),dir(44)*2.9); label("2",(1,3),dir(44)*2.9); label("0",(1,4),dir(44)*2.9); label("1",(2,0),dir(44)*2.9); label("2",(2,1),dir(44)*2.9); label("0",(2,2),dir(44)*2.9); label("1",(2,3),dir(44)*2.9); label("2",(2,4),dir(44)*2.9); label("0",(3,0),dir(44)*2.9); label("1",(3,1),dir(44)*2.9); label("2",(3,2),dir(44)*2.9); label("0",(3,3),dir(44)*2.9); label("1",(3,4),dir(44)*2.9); label("2",(4,0),dir(44)*2.9); label("0",(4,1),dir(44)*2.9); label("1",(4,2),dir(44)*2.9); label("2",(4,3),dir(44)*2.9); label("0",(4,4),dir(44)*2.9); label("1",(5,0),dir(44)*2.9); label("2",(5,1),dir(44)*2.9); label("0",(5,2),dir(44)*2.9); label("1",(5,3),dir(44)*2.9); label("2",(5,4),dir(44)*2.9); label("0",(6,0),dir(44)*2.9); label("1",(6,1),dir(44)*2.9); label("2",(6,2),dir(44)*2.9); label("0",(6,3),dir(44)*2.9); label("1",(6,4),dir(44)*2.9); [/asy][/asy] Now the three rectangles with a side divisible by $3$ can be tiled by $3\times 1$ rectangles, and thus have the same number of each color. Thus it suffices to check rectangles with side lengths $<3:$ the $1\times 1$ and $2\times 1$ have one $0$ and zero $1$s, the $1\times 2$ has one $0$ and zero $2$s, and the $2\times 2$ has two $0$s and one $1.$ Thus each of these has two colors with different parities, so we are done.

I love generating functions. The answer is $3\mid mn$. Work in the polynomial ring $\mathbb F_2[x,y]$. We represent a configuration by the polynomial in the set $$S = \left\{\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij} x^iy^j : a_{ij}\in\mathbb F_2\right\} \subset\mathbb F_2[x,y],$$where for a configuration with polynomial $\textstyle{\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij} x^iy^j}$, the cell $(i+1,j+1)$ is head if $a_{ij}=0$ and tails otherwise. Thus, each move corresponds to adding a monomial times $x+y+1$ or $x+y+xy$ into the polynomial. Therefore, a configuration can be made into all heads if and only if the corresponding polynomial is in form $P(x,y)(x+y+1) + Q(x,y)(x+y+xy)$. We need to determine whether the polynomial $$P(x,y) = (1+x+x^2+\dots+x^m)(1+y+y^2+\dots+y^n)$$can be written in that form. By reducing modulo $x+y+1$, we are left to check whether $P(x,-1-x)$ is divisible by $x+(-1-x)+x(-1-x) = -(x^2+x+1)$. This is true if and only if either $1+x+\dots+x^m$ or $1+x+\dots+x^n$ is divisible by $1+x+x^2$, which occurs if and only if $3\mid mn$.

Note that the polynomials in Markbcc's solution can also be understood as using a finite field $F = \{0, 1, \omega, \omega^2\}$ of characteristic two as weights and utilising a method similar to that of 2021 USAMO 3.

The answer is all pairs $(m,n)$ such that $3\mid mn$. To see why the others don't work, label the cells of the grid as $(i,j)$ for $1\leq i\leq m$ and $1\leq j\leq n$ (with the bottom left corner being $(1,1)$), and write $(i-j)\pmod 3$ in each of them. A move flips one coin of each residue, but as there are $\lfloor mn/3 \rfloor$ cells with one residue and $\lceil mn/3\rceil = \lfloor mn/3\rfloor+1$ with another, we get that the number of moves must be both even and odd for all coins to show heads, which is impossible. We now show a construction for all grids $m\times n$ where $3\mid mn$. We can partition every such grid into multiple $2\times 3$, $3\times 2$, and $3\times 3$ subgrids by dividing the initial grid into rectangular strips $3\times n$ or $m\times 3$. Now, each such strip can be cut into $2\times 3$ or $3\times 2$ rectangles if the larger side is even, and such rectangles and one $3\times 3$ if it's odd. Therefore proving the statement for the grids $2\times 3$, $3\times 2$, and $3\times 3$ suffices. For brevity, call $L_{i,j}$ the set of cells $\{(i,j), (i+1, j), (i, j+1)\}$, and $R_{i+1,j+1}$ the set of cells $\{(i+1,j), (i,j+1), (i+1, j+1)\}$. For $2\times 3$, switching $L_{1,1}$ and $R_{2,3}$ works. Similarly, for $3\times 2$, switching $L_{1,1}$ and $R_{3,2}$ does the job. For $3\times 3$, we have the slightly more convoluted combination of moves $L_{1,1}+L_{1,2}+L_{2,1}+R_{2,2}+R_{3,3}$ which suffices. This completes the solution.

We claim that the solution is all pairs $(m,n)$ for which $3|mn$ The construction for $3|mn$ is the same as posts above. Consider the following coloring of the board: Description of the coloring (in case the image does not work): We will color the board in 3 colors along the diagonals going upwards from left to right. Notice that in this coloring we have that, no matter which three squares we pick, we will always pick three squares with a different color. Now, if $3 \nmid mn$ then one of the colors will be of a different quantity than the other two (it will be $1$ more or $1$ less than the other colors), hence the quantity of one color will be of different parity than the other two. Claim: If the quantity of some color is uneven, then flipping all tails to heads on that color will take an uneven number of moves. Assume we have m squares colored with color A and m is uneven. To turn one single coin from tails to heads it takes an uneven amount of moves performed on that coin so summing up m uneven numbers we get an uneven number, hence the claim is true Claim: If the quantity of some color is even, then flipping all tails to heads on that color will take an even number of moves. The proof is very similar to the proof given above. Because we got that the number of moves must be both even and odd (because we have both parities for the quantities of colors), we got a contradiction. Hence, it must be that $3|mn$

The answer is $3\mid m$ or $3\mid n$ (i.e. $3\mid mn$). For a construction, observe that we can flip any $3 \times 2$ rectangle; then take a $3 \times 2$ rectangle and flip the L-shape in the bottom left, the L-shape one cell to the right of it, and the rotated L-shape in the bottom left to leave only the bottom row of the $3 \times 2$ flipped (look at oron's in post #2). To get the top row, just flip the whole $3 \times 2$. Thus we can flip any $3 \times 1$ rectangle, and by reflecting everything $45^{\circ}$, we can also flip any $1 \times 3$ rectangle. Therefore if $3 \mid mn$ we can repeatedly flip $1 \times 3$ rectangles along the rows or columns to flip the whole grid. Also, since $m, n > 1$, we'll always have room to choose a $3 \times 2$ or $2 \times 3$ rectangle to do this. Now index the rows $(1, \dots, m)$ from left to right and index the columns $(1, \dots, n)$ from top to bottom. In each cell $(i, j)$, write the value of $(i + j) \pmod3$. Then each move flips exactly one $0$, one $1$, and one $2$. So, to flip all $mn$ cells, the amount of $0$'s, $1$'s, and $2$'s must be equal $\pmod 2$. It's easy to see (say, by chopping off $3 \times k$ grids of rows and columns to leave a $2 \times 2$ or smaller) that the amount of cells labeled with each residue cannot differ by 2 or more, so they must be equal. This implies $3 \mid mn$.

The construction is omitted cuz its silly. We first show necessity. We want to find sols to \[ P(x, y)(1 + x + y) + Q(x, y)(x + y + xy) = (1 + x + \dots + x^m)(1 + y + \dots + y^n) \]over $\mathbb{F}_2$. Note that $x^2 + x + 1$ is irreducible over $\mathbb{F}_2$ so extend our field extension to get $\mathbb{F}_2[\zeta]$ where $\zeta$ is the third root of unity. Now, substitute $x = \zeta, y = \zeta^2$. Then $1 + x + y = x + y + xy = 0$, so the LHS is $0$. Then either $\zeta$ is a root of $(1 + x + \dots + x^m)$ or $\zeta^2$ is a root of $(1 + y + \dots + y^n)$ so $3$ divides one of $m$ and $n$.

We claim the answer is $3\mid mn$. Consider the sets of diagonals formed by taking $i-j\pmod 3$. Let there be $a,b,c$ in each of these sets of columns. We have that $a \equiv b\equiv c\pmod 2$. However, for the whole grid to be covered, this means $a = b= c$ since the size of the set of diagonals differ by at most $1$. Note that $3\mid mn$ implies $3\mid m$ or $3\mid n$. By taking the following L-shapes, we can flip any $1 \times 3$ meaning we can flip the whole grid. $(i,j),(i+1,j),(i,j+1)$, $(i+1,j+1), (i,j+1), (i+1,j)$, $(i+1,j+1), (i+1,j), (i+2,j)$ flips only $(i,j), (i+1,j), (i+2,j)$ so we are done.

hardest c1?? I claim the answer is $3 \mid mn$ with $mn \neq 3$. Construction: We prove that we can achieve all heads for all $3$ by $x$ rectangles for $x > 1$. Then we can finish by just combining such rectangles, and applying moves on them separately. We do this by proving we can achieve $3$ by $2$ and $3$ by $3$ rectangles. Then we can finish by just combining such rectangles, and applying moves on them separately. To make a $3$ by $2$ do the move on the squared labeled 1 in the first move and 2 in the second move. 22 12 11 To make a $3$ by $3$ do the following moves written the same way as before to get the left column completely heads and everything else tails, then do the $3$ by $2$ to get the full thing. (1) () () (123) (13) () (2) (23) () Proof of necessity: Color the rectangle by the following easily generalizable coloring ....... 231231231231... 312312312312... 123123123123... Then each operation changes the parity of the total number of heads of each color by one, thus they all have the same parity of number of heads, if $3 \nmid mn$ this will not be possible in the final scenario since they will have all heads but the colors occur with different parities.

GEN FUNC ORZZZZZZZZ The answer is $3\mid mn$. I infact give an algebric proof of both directions Consider the ring $\mathbb F_2[x,y]$. Represent the configuration of the board by $$S = \left\{\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij} x^iy^j : a_{ij}\in\mathbb F_2\right\} \subset\mathbb F_2[x,y],$$where for a configuration with polynomial $\textstyle{\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij} x^iy^j}$, the cell $(i+1,j+1)$ is head iff $a_{ij}=0$ We now get that each move corresponds to adding a monomial times $x+y+1$ or $x+y+xy$ into the polynomial(modulo 2 FTW!). Therefore, a configuration can be made into all heads if and only if the corresponding polynomial is in form $P(x,y)(x+y+1) + Q(x,y)(x+y+xy)$. Now we want to determine wheter $$R(x,y) = (1+x+x^2+\dots+x^m)(1+y+y^2+\dots+y^n)$$can be written in that form. If we reduce modulo $x+y+1$, we must check that $P(x,-1-x)$ is divisible by $x+(-1-x)+x(-1-x) = -(x^2+x+1)$. This is true iff either $x^m+\dots+x^2+x+1$ or $x^n+\dots+x+1$ is divisible by $x^2+x+1$, which can be checked to occur if and only if $3\mid mn$, as desired Remark: My original solution was the combinatorial one(in terms of construction) but then I got the algebric one while trying to prove the only if direction but I only got the only if of the algebric version by substituting $(x,y)=(\omega,\omega^2)$ but then later I was told by a friend the modulo $x+y+1$ trick which was crazy awseome

The answer is all $m, n$ such that $3 \mid m$ or $3 \mid n$. Bound: We color the chessboard cells red, blue, or green such that every row and column reads red, blue, green, repeating in that order. Any operation performed on the chessboard will then operate on an equal number of red, blue, and green cells. Claim: The number of red, blue, and green cells must all be the same parity. Proof: Assume for the sake of contradiction that there were an even number of red cells and odd number of blue cells. It follows that to flip all the coins in the blue cells, it requires an odd number of operations (as every cell should be affected an odd number of times.) But applying the same argument to the red cells, there should be an even number of operations, contradiction. $\blacksquare$ Suppose there are $r$ red cells, $b$ blue cells, and $g$ green cells in the coloring. Observe that $|r-b|$ is unaffected if we remove any three columns or three rows; so the only possible values $|r-b|$ can take are those for a $1 \times 1$, $1 \times 2$, or $2 \times 2$ grid. For each of these grids, $|r-b| \leq 1$. This implies that $r=g=b$, so the number of cells is a multiple of three. Construction: Clearly a $3 \times 2$ square can be constructed, and a $3 \times 3$ square can be constructed as follows: place the cells in a coordinate system such that $(1, 1)$ represents the bottom-left square, and consider performing operations on the square with bottom-left corner $(1, 1)$, flipping that corner; the square with top-right corner $(2, 2)$, flipping that corner; the square with bottom-left corner $(1, 2)$, flipping that corner; the square with top-right corner $(2, 2)$, flipping that corner; and the square with bottom-left corner $(2, 1)$, flipping that corner. Any $3 \times n$ grid can be divided into $3 \times 2$ and $3 \times 3$ grids, so the result follows.