International Mathematical Olympiad

$m$ and $n$ should be the positive integers and should satisfy one of the following conditions:

(1) $3\mid m$ and $4\mid n$ (or vice versa); (2) one of $m$ and $n$ is divisible by $12$ and one is not less than $7$.

A figure is obtained by applying rotations and reflections to another figure. We regard the two figures as equivalent. Label the six unit squares of the hook as shown below. The shaded square must belong to another hook, and it is adjacent to only one square of this other hook. Then the only possibility of the shaded square is $1$ or $6$.

(i) If it is $6$, two hooks form a $3\times 4$ rectangle. We call it $(1)$. (ii) If it is $1$, there are two cases. It is easy to see that the shaded square cannot be covered in the first diagram as shown below. Hence the latter is true. We call it $(2)$.

Thus, in a tessellation, all hooks are matched into pairs. Each pair forms $(1)$ or $(2)$. $(1)$ There are $12$ squares in $(1)$ and $(2)$. Hence $12\mid mn$. $(2)$

Now we consider three cases, separately.

(1) $3\mid m$ and $4\mid n$ (or vice versa) Without loss of generality, we may assume $m=3m_0$ and $n=4n_0$. Then $m_0{n}_0$ rectangles of the type $(1)$ form an $m_0\times n_0$ rectangle. Since two hooks cover a $3\times 4$ rectangle, an $m\times n$ rectangle can be covered with hooks.

(2) $12\mid m$ or $12\mid n$. Without loss of generality, we may assume $12\mid m$. If $3\mid n$ or $4\mid n$, the question reduces to (1). Assume that $n$ is not divisible by $3$ nor by $4$. If a tessellation exists, then there is at least one of $(1)$ and $(2)$ in it, so $n\ge 3$. Hence $n\ge 5$ because $3\times n$ and $4\times n$. Since the square at the corners can belong to either $(1)$ or $(2)$, it follows from $n\ge 5$ that the squares at the adjacent corners cannot belong to the same type $(1)$ or $(2)$. Hence $n\ge 6$. Since $n$ is not divisible by $3$ and $4$, $n\ge 7$.

(3) $12\mid mn$, but neither $m$ nor $n$ is divisible by $4$. Now $2\mid m$, $2\mid n$. We may assume without loss of generality that $m=6m_0$, $n=2n_0$, neither $m_0$ nor $n_0$ is divisible by $2$. We will prove that if these conditions are satisfied, an $m\times n$ rectangle cannot be covered with hooks. Consider coloring the columns of an $m\times n$ matrix with black and white colors alternately. Then the number of the black squares equals that of the white ones. One $(2)$ always covers $6$ black squares. A horizontal $(1)$ always covers $6$ black squares. A vertical $(1)$ covers either $8$ black squares and $4$ white ones, or $4$ black squares and $8$ white ones. Since the number of the black squares equals that of the white ones, the number of $(1)$ is the same in the preceding two cases. Hence the total number of a vertical $(1)$ is even. Using the same argument as above (coloring the rows alternately), we obtain that the total number of a horizontal $(1)$ is even. Consider classifying the squares of the $m\times n$ rectangle into $4$ types marked $1$, $2$, $3$, and $4$ as shown below. The number of squares of each type is equal to $\frac{mn}{4}$. From the two diagrams, we obtain that the number of $a$ and $c$ covered by $(1)$ is the same, so is for $b$ and $d$. Hence the number of squares of type $1$ covered by $(1)$ equals that of type $3$. (i) (ii) (iii) (iv) The number of squares of type $1$ covered by (i) or (ii) equals that of type $3$. The difference between the number of squares of type $1$ and type $3$ covered by (iii) or (iv) is $2$. There are two cases; the number of squares of type $1$ is $2$ more than that of type $3$, or vice versa. Since the number of squares of type $1$ equals that of type $3$ in the rectangle, the frequency of the two cases is the same. Hence the total number of (iii) and (iv) is even. Similarly, the total number of (i) and (ii) is even. Then the number of $(2)$ is even. So there is an even number of $(1)$ and $(2)$. Hence $24\mid m\times n$, contrary to the assumption that neither $m$ nor $n$ is divisible by $4$.

We now show that if $n\ge 7$ and $n$ is not divisible by $3$ and $4$, a tessellation exists. If $n\equiv 1(\mathrm{mod}3)$, then $n=4+3t$ ($t\in {\mathbb{N}}^{\ast }$). Together with (1), we have that if $12\mid m$, an $m\times 3t$ rectangle and an $m\times 4$ rectangle can be covered with hooks. So the problem can be solved. If $n\equiv 2(\mathrm{mod}3)$, $n=8+3t$ ($t\in {\mathbb{N}}^{\ast }$). Together with (1), we have that if $12\mid m$, each of $m\times 8$ and $m\times 3t$ rectangles can be covered with hooks. The problem is solved.

---

Alternative solution.

$m$ and $n$ should be the positive integers and should satisfy one of the following conditions: (1) $3\mid m$ and $4\mid n$ (or vice versa); (2) $12\mid m$, $n\notin \{1,2,5\}$ (or vice versa).

Consider a covering of an $m\times n$ rectangle satisfying the conditions. For any hook $A$, there is a unique hook $B$ covering the "inner" square of $A$ with one of its "tailend" squares. In turn, the "inner" square of $B$ must be covered by a "tailend" square of $A$. Thus, in a tessellation, all hooks are matched into pairs. There are only two possibilities to place $B$ so that it does not overlap with $A$ and no gap occurs. In one case, $A$ and $B$ form a $3\times 4$ rectangle; in the other, their union is an octagonal shape, with sides of length $3$, $2$, $1$, $2$, $3$, $2$, $1$, $2$ respectively. So an $m\times n$ rectangle can be covered with hooks if and only if it can be covered with the $12$-square tiles described above. Suppose that such a tessellation exists; then $mn$ is divisible by $12$. We now show that one of $m$ and $n$ is divisible by $4$. Assume on the contrary that this is not the case. Then $m$ and $n$ are both even, because $mn$ is divisible by $4$. Imagine that the rectangle is divided into unit squares, with the rows and columns labeled $1,\dots ,m$ and $1,\dots ,n$. Write $1$ in the square $(i,j)$ if exactly one of $i$ and $j$ is divisible by $4$, and $2$, if $i$ and $j$ are both divisible by $4$. Since the number of squares in each row and column is even, the sum of all numbers written is also even. Now, it is easy to check that a $3\times 4$ rectangle always covers numbers with sum $3$ or $7$; and the other $12$-square shape always covers numbers with sum $5$ or $7$. Consequently, the total number of $12$-square shapes is even. But then $mn$ is divisible by $24$, and hence by $8$, contrary to the assumption that $m$ and $n$ are not divisible by $4$. Notice also that neither $m$ nor $n$ can be $1$, $2$ or $5$ (any attempt to place tiles along a side of length $1$, $2$ or $5$ fails). We infer that if a tessellation is possible, then one of $m$ and $n$ is divisible by $3$, one is divisible by $4$, and $m,n\notin \{1,2,5\}$. Conversely, we shall prove that if these conditions are satisfied, then a tessellation is possible (using only $3\times 4$ rectangles). The result is immediate if $3$ divides $m$ and $4$ divides $n$ (or vice versa). Let $m$ be divisible by $12$ and $n\notin \{1,2,5\}$ (or vice versa). Without loss of generality, we may assume that neither $3$ nor $4$ divides $n$. Then $n\ge 7$. In addition, between $n-4$ and $n-8$, at least one can be divisible by $3$. Hence the rectangle can be partitioned into $m\times 3$ and $m\times 4$ rectangles, which are easy to cover, in fact with only $3\times 4$ tiles again.