59th Ukrainian National Mathematical Olympiad

Consider the case when one of the numbers is not divisible by two and another one is not divisible by three. Without loss of generality, let $m$ be not divisible by $2$, and let $n$ be not divisible by $3$, and let $m$ be the width and $n$ be the height of the rectangle.

We will color in black all the rows of the rectangle $m\times n$ of the type $3k$ and $3k+2$, $k\in \mathbb{N}$ (Fig. 12). The number of black rows is odd: $2\left[\frac{1}{3}n\right]+1$, hence the odd number of black cells, since there are odd ($m$) number of cells in each row. Since every square $2\times 2$ and $3\times 3$ covers even number of black cells, it is not possible to cover the rectangle with $2\times 2$ and $3\times 3$ squares.

It suffices to consider the case when both $m$ and $n$ are divisible by $2$, or $3$. Then it is clear how to divide the rectangle into $2\times 2$ squares (in the first case) or $3\times 3$ squares (in the second case).