IMO 2004 SL C7

Origin: EST | Category: Combinatorics

Problem

Determine all m \times n rectangles that can be covered with hooks made up of 6 unit squares, as in the figure: Rotations and reflections of hooks are allowed. The rectangle must be covered without gaps and overlaps. No part of a hook may cover area outside the rectangle.

Solution

Suppose that an m\timesn rectangle can be covered by “hooks”. For any hook H there is a unique hook K that covers its “ inside” square. Then also H covers the inside square of K, so the set of hooks can be partitioned into pairs of type {H, K}, each of which forms one of the following two figures consisting of 12 squares: A1 B1 A2 B2 Thus the m \times n rectangle is covered by these tiles. It immediately follows that 12 | mn. Suppose one of m, n is divisible by 4. Let w.l.o.g. 4 | m. If 3 | n, one can easily cover the rectangle by 3\times4 rectangles and therefore by hooks. Also, if 12 | m and n ̸\in{1, 2, 5}, then there exist k, l \inN0 such that n = 3k+4l, and thus the rectangle m \times n can be partitioned into 3 \times 12 and 4 \times 12 rectangles all of which can be covered by hooks. If 12 | m and n = 1, 2, or 5, then it is easy to see that covering by hooks is not possible. Now suppose that 4 ∤m and 4 ∤n. Then m, n are even and the number of tiles is odd. Assume that the total number of tiles of types A1 and B1 is odd (otherwise the total number of tiles of types A2 and B2 is odd, which is analogous). If we color in black all columns whose indices are divisible by 4, we see that each tile of type A1 or B1 covers three black squares, which yields an odd number in total. Hence the total number of black squares covered by the tiles of types A2 and B2 must be odd. This is impossible, since each such tile covers two or four black squares.