XXIX Rioplatense Mathematical Olympiad

We will prove that the only boards that can be covered with the given pieces are the following: Those with both sides even. Those with both sides divisible by 3. * Those with at least one side divisible by 6.

If both $m$ and $n$ are even, then the $m\times n$ board can be divided into $2\times 2$ squares, which can be covered using type A pieces. On the other hand, using one piece of each type, a $3\times 3$ square can be formed. Therefore, if both $m$ and $n$ are divisible by 3, since the $m\times n$ board can be divided into $3\times 3$ squares, it can be covered using the given pieces.

Now let's see that for every $n\ge 2$, a $6\times n$ board can be covered using the given pieces (and thus, by stacking multiple of these, any $6k\times n$ board can be covered, as we claim). We can form a $6\times 2$ rectangle by vertically stacking three type A pieces. We can also form a $6\times 3$ rectangle by stacking two $3\times 3$ squares, which we have already seen how to form. Now, if $n\ge 2$ is even, we can form the $6\times n$ rectangle using multiple $6\times 2$ rectangles; and if $n$ is odd, we can first place a $6\times 3$ rectangle followed by enough $6\times 2$ rectangles. The figure shows an example for $n=7$.



We will now prove that there are no other solutions. Let's consider a board of size $m\times n$ that can be covered. If both sides are even, we have already seen how to do it. So, without loss of generality, let's assume that $m$ is odd. We color the cells of the board alternately by rows: the cells in the first row are black, the cells in the second row are white, the cells in the third row are black, and so on until the $m$-th row, which is black (because $m$ is odd). We observe that in the thus colored board, there are $n$ more black cells than white cells. Now let's notice that each type A piece always covers 2 white cells and 2 black cells, while a type B piece can cover either 4 white cells and 1 black cell, or vice versa. Thus, in each piece, the difference between the number of white cells covered and the number of black cells covered is divisible by 3. Consequently, if the board can be covered, the total difference between white and black cells must also be divisible by 3. This difference is $n$.

So far, we have shown that if one side is odd, the other side must be divisible by 3. If $n$ were odd, the same argument would allow us to prove that $m$ is divisible by 3, and we would be in a case that has already been considered. Therefore, we only need to consider the case of even $n$, but then $n$ would be divisible by 6, which is again a case we have already analyzed. This proves that there are no other solutions apart from the three mentioned at the beginning.