Klarner set

How do I fit as many boxes and suitcases as possible into my much too small car? How can container ships be loaded in the most space-saving way possible? How can I cut out as many cookies as possible from a sheet of dough? How does a layout artist fill a newspaper page with as many ads 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 specialty of the American mathematician David A. Klarner (†1999).

A puzzle in MATHEMATICS ADVENTURE LAND refers to one of his 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 MATHEMATICS ADVENTURE LAND is divided into 10\times 10, that is 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.

Figure 1: Exhibit in the MATHEMATICS ADVENTURE LAND

And now … the mathematics of it:

The divisibility of the large area of 10\times 10 squares can be illustrated well if the diagonals are marked with four different colors. In the MATHEMATICS ADVENTURE LAND the 10 squares of the main diagonals from the lower left to the upper right are colored red, the squares of the secondary diagonals connecting to the lower right are colored blue, orange, green and red again up to the blue square in the corner. In reverse order, the secondary diagonals to the top left are colored green, orange, blue and red again, and so on until the green square in the corner (see Figure 2). Mathematically expressed: If one identifies each square with a lattice point (x,y) in the plane lattice \mathbb Z\times\mathbb Z, those lattice points where x-y belong to the same residue class modulo 4 are colored with the same color.

If we now distribute the strips of four in any order, each strip always covers one square of each of the above four colors. If we now add up all the squares of each color, we 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.
Figure 2

So our conclusion is: If each strip of four covers all four colors, there are only as many strips on the large area as there are squares of the color that occurs most rarely. In the example, these are the 24 orange squares. No matter how the stripes are placed, there will always be one green, one blue and two red squares left. An overlap of these last four squares 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 MATHEMATICS ADVENTURE LAND: Instead of four, n colors must now be used, and we color 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 (lattice point) of each of the n colors. If one of the lengths a or b (or both), say a, is divisible by n, we can clearly fill this in with stripes of length n by simply laying all the stripes horizontally, thus forming b “layers” of stripes each a/n adjacent.

So it follows in particular that in such a rectangle there must be equal numbers of squares (lattice points) of each color (“residue class”). Now it only remains to show that a rectangle, where neither a nor b are divisible by n, cannot be laid out by stripes of length n. We show this with the help of the coloring above. If it were possible to lay out such a rectangle with stripes of length n, then in this rectangle, since each such stripe covers exactly one square (lattice point) of each of the n colors, there should be the same number of squares (lattice points) of each color. So it is sufficient to show that this is not the case. So by “taking away” from our rectangle of dimension a\times b first 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 colors can occur in it with equal frequency. Since in our “subtracted” rectangles each color occurs equally often, then also in the original rectangle not all colors occur with the same frequency.

This assertion is easy to see, however, because since a',b'<n, the only way that a lattice point of the new rectangle {1,\ldots,a'}\times{1,\ldots,b'}, say (x,y), is colored 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. Now, if all colors would 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.