IMO 2004 · Problem 3

Define a ”hook” to be a figure made up of six unit squares as shown below in the picture, or any of the figures obtained by applying rotations and reflections to this figure.

┌───┬───┬───┐
│   │   │   │
├───┼───┼───┤
│   │   │   │
├───┤   └───┘
│   │
└───┘

Determine all \(m\times n\) rectangles that can be covered without gaps and without overlaps with hooks such that

  • the rectangle is covered without gaps and without overlaps
  • no part of a hook covers area outside the rectagle.

Official text of the problem. Official problem paper (PDF)

Answer

Exactly the rectangles satisfying \[ \boxed{ m,n\in\mathbb Z_{>0},\qquad m,n\notin\{1,2,5\},\qquad 12\mid mn,\qquad 4\mid m\ \text{or}\ 4\mid n. } \]

Solution

We first establish the necessary conditions.

All tiles in a tiling have their grid directions parallel to the rectangle’s sides. Indeed, tiles sharing an edge segment have the same grid directions, and their adjacency graph is connected: a path between tile interiors can be chosen to avoid all vertices. Moreover, a horizontal line avoiding vertices cuts the hooks into intervals of integer length. Starting from the rectangle’s left side, their endpoints therefore have integer coordinates. The analogous vertical argument shows that the entire tiling lies on one unit-square grid, and that \(m,n\) are integers.

Hooks must occur in pairs. Fix a hook \(A\), positioned as follows; dots denote squares outside it:

AAA
A.A
A..

Its central missing square has three neighbours in \(A\). Consequently, the hook \(B\) covering that square must have an endpoint there, with its next square immediately below.

A hook has two different endpoints. For either endpoint, the remaining part can turn left or right, giving four possibilities. One overlaps \(A\) immediately. The other three are:

   R          S        Impossible

AAAB       .AAA        AAA.
ABAB       .ABA        ABA.
ABBB       BAB.        AB.B
           BBB.        .BBB

In the last configuration, the missing square in the third row and third column is surrounded on all four sides. No hook can cover it.

Thus only \(R\) and \(S\) are possible. In both, \(A\) also covers the central missing square of \(B\). Hence this pairing is mutual and partitions all hooks into pairs.

Each pair is therefore either a \(3\times4\) rectangle \(R\), or the stepped figure \(S\)

.XXX
.XXX
XXX.
XXX.

up to rotations and reflections. Both have area \(12\), so \[ 12\mid mn. \tag{1} \]

Neither side can be \(1,2,\) or \(5\). Every hook has a \(3\times3\) bounding square, so both sides are at least \(3\).

Consider the paired tiles meeting the top row of the rectangle. Their numbers of squares in the first two rows are respectively:

  • \(3,3\) or \(4,4\) for \(R\);
  • \(3,3\) for a horizontally stepped \(S\);
  • \(2,4\) for a vertically stepped \(S\).

The first-row contributions already sum to the rectangle’s width. Thus a vertically stepped \(S\) would make the second-row contributions exceed that width. None can occur.

For every remaining tile meeting the top row, its third-row interval has the same length as its first-row interval. For \(R\), its position is unchanged; for \(S\), it shifts one square left or right. These third-row intervals again have total length equal to the rectangle’s width, so they partition that row.

Their order cannot change: each interval has length at least \(3\), while each displacement has magnitude at most \(1\). A partition into intervals with the same ordered lengths has uniquely determined endpoints. Hence every displacement is zero, excluding \(S\) from the top boundary.

Therefore the rectangle’s width is a sum of \(3\)’s and \(4\)’s. Applying the same argument after rotation gives the same conclusion for its height. In particular, \[ m,n\notin\{1,2,5\}. \tag{2} \]

One side must be divisible by \(4\). We prove this using an elementary matrix argument, including the required cancellation principle.

Assign an invertible matrix \(X\) to a unit step right and \(Y\) to a unit step down; assign \(X^{-1},Y^{-1}\) to the opposite steps. The matrix of a walk is the ordered product of its step matrices.

If every tile’s boundary has product \(I\), then the outer boundary also has product \(I\). To see this, suppose a closed edge walk has nonidentity product, and choose a simple such walk enclosing the fewest tiles. This is possible because a walk with repeated vertices splits into smaller closed walks, whose products, up to conjugation, give its product. Replace an edge of the chosen walk by the complementary boundary path around the tile immediately inside that edge. The product is unchanged. After cancelling backtracks and splitting at repeated vertices, the resulting loops enclose components of the old region with that tile removed. Each encloses fewer tiles, so each has product \(I\), a contradiction.

Now put \[ \zeta=e^{\pi i/4},\qquad X=\begin{pmatrix}\zeta&0\\0&\zeta^{-1}\end{pmatrix}, \qquad Y=\frac1{\sqrt2} \begin{pmatrix}1&1\\-1&1\end{pmatrix}. \] Direct multiplication gives \[ X^4=Y^4=-I,\qquad Y^2XY^{-2}=X^{-1},\qquad X^2YX^{-2}=Y^{-1}. \tag{3} \]

The boundary product of a \(3\times4\) rectangle is \[ X^3Y^4X^{-3}Y^{-4}=I, \] because \(Y^4=-I\).

For a stepped tile, take the orientation

XXX.
XXX.
.XXX
.XXX

Its boundary product, starting at its upper-left corner, is \[ X^3Y^2XY^2X^{-3}Y^{-2}X^{-1}Y^{-2}. \] By (3), \[ Y^2XY^2=-X^{-1}, \qquad Y^{-2}X^{-1}Y^{-2}=-X, \] so this product equals \[ X^3(-X^{-1})X^{-3}(-X)=I. \] The identities (3) remain valid when \(X,Y\) are interchanged or either is replaced by its inverse. Thus the same conclusion holds for every rotation and reflection of both paired tiles.

The cancellation principle now gives \[ X^mY^nX^{-m}Y^{-n}=I, \] or equivalently \(X^mY^n=Y^nX^m\).

But \[ X^m= \begin{pmatrix}\zeta^m&0\\0&\zeta^{-m}\end{pmatrix}, \qquad Y^n= \begin{pmatrix} \cos(n\pi/4)&\sin(n\pi/4)\\ -\sin(n\pi/4)&\cos(n\pi/4) \end{pmatrix}. \] Comparing their upper-right entries in the two products yields \[ (\zeta^m-\zeta^{-m})\sin(n\pi/4)=0. \] For integers \(m,n\), the first factor vanishes exactly when \(4\mid m\), and the second exactly when \(4\mid n\). Therefore \[ 4\mid m\quad\text{or}\quad4\mid n. \tag{4} \]

It remains to prove sufficiency.

Assume the stated conditions, and interchange the dimensions if necessary so that \(4\mid m\). Two hooks tile a \(4\times3\) rectangle, as shown by configuration \(R\).

If \(3\mid n\), divide the rectangle directly into \(4\times3\) blocks.

Otherwise, \(12\mid mn\) implies \(3\mid m\), hence \(12\mid m\). Every positive integer other than \(1,2,5\) is a nonnegative integer combination of \(3\) and \(4\): this holds for \(3,4,6,7,8\), and all larger cases follow by repeatedly adding \(3\). Write \[ n=3a+4b,\qquad a,b\ge0. \] Split the rectangle into \(a\) strips of size \(m\times3\) and \(b\) strips of size \(m\times4\). Since \(12\mid m\), every strip can be divided into \(3\times4\) rectangles, each covered by two hooks.

Thus all the stated rectangles, and only those rectangles, can be tiled.

The solution was checked against Evan Chen's published IMO solution notes.