Klarner’s theorem

How do I fit as many boxes and suitcases as possible into my much too small car? How are container ships loaded in the most space-saving way possible? How can I cut out as many biscuits as possible from a sheet of dough? How does the layout artist fill a newspaper page with as many advertisements as possible without gaps?

Such questions, which play a major role in everyday life and in business, are what mathematicians call packing problems. They were a speciality of the American mathematician David A. Klarner (†1999).

A puzzle in the Maths Adventure Land refers to one of its central statements. Klarner’s theorem states: A rectangle of dimension $a\times b$ , which consists of squares with side length 1, can be filled without gaps with $1\times n$ -sized strips if at least one of the side lengths $a$ or $b$ is divisible by $n$ . The rectangle in the Maths Adventure Land is divided into $10\times 10$ , or $100$ squares. The strips with which this area is to be filled consist of four squares of the same size arranged in a row one behind the other. $25$ of these strips also make $100$ squares.

However, the task of completely covering the rectangle with the strips is not solvable. If $24$ strips are placed on the surface, in no case a row of $4$ squares remains free for the 25th strip, but always a square field of $2\times 2$ small squares. Klarner’s theorem is thus confirmed, because the side length $10$ is not divisible by the strip length $4$ .

And now … the mathematics:

The divisibility of the large area of $10\times 10$ squares can be well illustrated if the diagonals are marked with four different colours. In the Maths Adventure Land, the 10 squares of the main diagonal from the bottom left to the top right are coloured red, the squares of the side diagonals connecting to the bottom right are coloured blue, orange, green and red again until the blue square in the corner. In reverse order, the secondary diagonals are coloured towards the top left, i.e. green, orange, blue and red again and so on until the green square in the corner (cf. Figure 2). In mathematical terms, if one identifies each square with a grid point $(x,y)$ in the plane grid $\mathbb Z\times\mathbb Z$ , those grid points where $x-y$ belong to the same residue class modulo $4$ are coloured with the same colour.

If you now distribute the strips of four in any order, each strip always covers one square of each of the four colours above. If you now add up all the squares of each colour, you get

$10+2\cdot 6+2\cdot 2=26$ red squares;
$9+5+1+7+3=25$ blue squares;
$2\cdot 8+2\cdot 4=24$ orange squares;
$7+3+9+5+1=25$ green squares.

So our conclusion is: If each strip of four covers all four colours, there are only as many strips on the large surface as there are squares of the colour that occurs most rarely. In the example, these are the $24$ orange squares. No matter how the strips are laid, there will always be one green, one blue and two red squares left. An overlapping of these last four fields by the last remaining strip is impossible!

The proof of Klarner’s general theorem — as formulated above — is now easy to derive from the proof of the special case presented in the Maths Adventure Land: Instead of four, $n$ colours must now be used and we colour the points $(x,y)$ of the rectangle $\{1,\ldots,a\}\times\{1,\ldots,b\}$ with the associated residue class of $x-y$ modulo $n$ . A strip of length $n$ then always covers one square (grid point) of each of the $n$ colours. If one of the lengths $a$ or $b$ (or both), say $a$ , is divisible by $n$ , we can clearly fill this in with strips of length $n$ by simply laying all the strips horizontally, thus forming $b$ “layers” of $a/n$ adjacent strips each.

It therefore follows in particular that in such a rectangle there must be an equal number of squares (grid points) of each colour (“residual class“). Now it only remains to show that a rectangle where neither $a$ nor $b$ are divisible by $n$ cannot be laid out by strips of length $n$ . We show this with the help of the colouring above. If it were possible to lay out such a rectangle with stripes of length $n$ , then, since each such stripe covers exactly one square (grid point) of each of the $n$ colours, there should be the same number of squares (grid points) of each colour in this rectangle. It is therefore sufficient to show that this is not the case. So, by first “taking away”from our rectangle of dimension $a\times b$ a rectangle of dimension $(n\lfloor a/n\rfloor)\times b$ , so that we get a new rectangle of dimension $a'\times b$ with $a'=a-n\lfloor a/n\rfloor$ , and then “subtract”a rectangle of dimension $a'\times(n\lfloor b/n\rfloor)$ from it, we get a rectangle of dimension $a'\times b'$ , where $b'=b-n\lfloor b/n\rfloor$ (here $\lfloor x\rfloor$ denotes the largest integer $\leq x$ ). This new rectangle now satisfies $0 < a',b' < n$ (since $a$ and $b$ were not divisible by $n$ ) and we show that not all colours can occur in it with equal frequency. Since each colour appears equally often in our “subtracted” rectangles, not all colours appear with the same frequency in the original rectangle either.

But this assertion is easy to see, because since $a',b' < n$ the only way that a grid point of the new rectangle $\{1,\ldots,a'\}\times\{1,\ldots,b'\}$ , say $(x,y)$ , is coloured with residue class $0$ modulo $n$ is that $x=y$ , because otherwise either $x$ or $y$ would have to be greater than $n$ . Thus there is exactly $m=\min(a',b')$ of such grid points. If all colours were to appear with the same frequency, our rectangle would have to have exactly $m\cdot n$ points. But it is easy to see that $a'\cdot b' < m\cdot n$ . Thus we obtain the desired contradiction and Klarner’s theorem is proved (in its full generality).

Literature

[1] Klarner, D.A.: Packing Boxes with congruent figures, in: American Mathematical Monthly 1, S. 100–105, 1964.

[2] Klarner, D.A. (Hrsg.): Mathematical Recreations: A Collection in Honor of Martin Gardner, Dover, 1998 (Reprint der unter dem Titel The Mathematical Gardner, Boston 1982, erschienenen Originalausgabe).

[3] Sachs, K.: Die Sätze von D. Klarner und N.G. de Bruijn als Exponate, Bachelor-Arbeit am Institut für Algebra der TU Dresden, 2010.