Maths Olympiad Prep

Library / /105 of 106

Combinatorics Difficulty 9.2 IMO level Prove it China

Define a hook to be a figure made up of six unit squares as shown in the diagram or any of the figures obtained by applying rotations and reflections to this figure.
Figure 1
Determine all m×nm \times n rectangles that can be covered with hooks so that
* the rectangle is covered without gaps and without overlaps;
* no part of a hook covers area outside the rectangle.

Solutions — 2

Solution 1

mm and nn should be the positive integers and should satisfy one of the following conditions:

(1) 3m3 \mid m and 4n4 \mid n (or vice versa);
(2) one of mm and nn is divisible by 1212 and one is not less than 77.

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 11 or 66.

(i) If it is 66, two hooks form a 3×43 \times 4 rectangle. We call it (1)\mathbf{(1)}.
Figure 2
(ii) If it is 11, 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)\mathbf{(2)}.
Figure 3

Thus, in a tessellation, all hooks are matched into pairs. Each pair forms (1)\mathbf{(1)} or (2)\mathbf{(2)}.
(1)\mathbf{(1)}
There are 1212 squares in (1)\mathbf{(1)} and (2)\mathbf{(2)}. Hence 12mn12 \mid m n.
Figure 4
(2)\mathbf{(2)}

Now we consider three cases, separately.

(1) 3m3 \mid m and 4n4 \mid n (or vice versa)
Without loss of generality, we may assume m=3m0m = 3m_0 and n=4n0n = 4n_0.
Then m0n0m_0 n_0 rectangles of the type (1)\mathbf{(1)} form an m0×n0m_0 \times n_0 rectangle. Since two hooks cover a 3×43 \times 4 rectangle, an m×nm \times n rectangle can be covered with hooks.

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

(3) 12mn12 \mid m n, but neither mm nor nn is divisible by 44. Now 2m2 \mid m, 2n2 \mid n. We may assume without loss of generality that m=6m0m = 6m_0, n=2n0n = 2n_0, neither m0m_0 nor n0n_0 is divisible by 22. We will prove that if these conditions are satisfied, an m×nm \times n rectangle cannot be covered with hooks.
Consider coloring the columns of an m×nm \times n matrix with black and white colors alternately. Then the number of the black squares equals that of the white ones. One (2)\mathbf{(2)} always covers 66 black squares. A horizontal (1)\mathbf{(1)} always covers 66 black squares. A vertical (1)\mathbf{(1)} covers either 88 black squares and 44 white ones, or 44 black squares and 88 white ones. Since the number of the black squares equals that of the white ones, the number of (1)\mathbf{(1)} is the same in the preceding two cases. Hence the total number of a vertical (1)\mathbf{(1)} is even. Using the same argument as above (coloring the rows alternately), we obtain that the total number of a horizontal (1)\mathbf{(1)} is even.
Consider classifying the squares of the m×nm \times n rectangle into 44 types marked 11, 22, 33, and 44 as shown below. The number of squares of each type is equal to mn4\frac{m n}{4}.
Figure 5
From the two diagrams,
Figure 6
Figure 7
we obtain that the number of aa and cc covered by (1)\mathbf{(1)} is the same, so is for bb and dd. Hence the number of squares of type 11 covered by (1)\mathbf{(1)} equals that of type 33.
Figure 8
(i)
Figure 9
(ii)
Figure 10
(iii)
Figure 11
(iv)
The number of squares of type 11 covered by (i) or (ii) equals that of type 33. The difference between the number of squares of type 11 and type 33 covered by (iii) or (iv) is 22. There are two cases; the number of squares of type 11 is 22 more than that of type 33, or vice versa. Since the number of squares of type 11 equals that of type 33 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)\mathbf{(2)} is even. So there is an even number of (1)\mathbf{(1)} and (2)\mathbf{(2)}. Hence 24m×n24 \mid m \times n, contrary to the assumption that neither mm nor nn is divisible by 44.

We now show that if n7n \ge 7 and nn is not divisible by 33 and 44, a tessellation exists.
If n1(mod3)n \equiv 1 \pmod{3}, then n=4+3tn = 4 + 3t (tNt \in \mathbb{N}^*). Together with (1), we have that if 12m12 \mid m, an m×3tm \times 3t rectangle and an m×4m \times 4 rectangle can be covered with hooks. So the problem can be solved.
If n2(mod3)n \equiv 2 \pmod{3}, n=8+3tn = 8 + 3t (tNt \in \mathbb{N}^*). Together with (1), we have that if 12m12 \mid m, each of m×8m \times 8 and m×3tm \times 3t rectangles can be covered with hooks. The problem is solved.

Solution 2

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

Consider a covering of an m×nm \times n rectangle satisfying the conditions. For any hook AA, there is a unique hook BB covering the "inner" square of AA with one of its "tailend" squares. In turn, the "inner" square of BB must be covered by a "tailend" square of AA. Thus, in a tessellation, all hooks are matched into pairs. There are only two possibilities to place BB so that it does not overlap with AA and no gap occurs. In one case, AA and BB form a 3×43 \times 4 rectangle; in the other, their union is an octagonal shape, with sides of length 33, 22, 11, 22, 33, 22, 11, 22 respectively.
So an m×nm \times n rectangle can be covered with hooks if and only if it can be covered with the 1212-square tiles described above. Suppose that such a tessellation exists; then mnmn is divisible by 1212. We now show that one of mm and nn is divisible by 44.
Assume on the contrary that this is not the case. Then mm and nn are both even, because mnmn is divisible by 44. Imagine that the rectangle is divided into unit squares, with the rows and columns labeled 1,,m1, \ldots, m and 1,,n1, \ldots, n. Write 11 in the square (i,j)(i, j) if exactly one of ii and jj is divisible by 44, and 22, if ii and jj are both divisible by 44. 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×43 \times 4 rectangle always covers numbers with sum 33 or 77; and the other 1212-square shape always covers numbers with sum 55 or 77. Consequently, the total number of 1212-square shapes is even. But then mnmn is divisible by 2424, and hence by 88, contrary to the assumption that mm and nn are not divisible by 44.
Notice also that neither mm nor nn can be 11, 22 or 55 (any attempt to place tiles along a side of length 11, 22 or 55 fails). We infer that if a tessellation is possible, then one of mm and nn is divisible by 33, one is divisible by 44, and m,n{1,2,5}m, n \notin \{1, 2, 5\}.
Conversely, we shall prove that if these conditions are satisfied, then a tessellation is possible (using only 3×43 \times 4 rectangles). The result is immediate if 33 divides mm and 44 divides nn (or vice versa). Let mm be divisible by 1212 and n{1,2,5}n \notin \{1, 2, 5\} (or vice versa). Without loss of generality, we may assume that neither 33 nor 44 divides nn. Then n7n \ge 7. In addition, between n4n-4 and n8n-8, at least one can be divisible by 33. Hence the rectangle can be partitioned into m×3m \times 3 and m×4m \times 4 rectangles, which are easy to cover, in fact with only 3×43 \times 4 tiles again.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.