Satz von Klarner

Wie passen möglichst viele Kisten und Koffer in mein viel zu kleines Auto? Wie werden Containerschiffe möglichst platzsparend beladen? Wie kann ich aus einer Teigplatte möglichst viele Kekse ausstechen? Wie füllt der Layouter eine Zeitungsseite lückenlos mit möglichst vielen Anzeigen?

Derartige Fragen, die im Alltag und in der Wirtschaft eine große Rolle spielen, bezeichnen Mathematiker als Packungsprobleme. Sie waren eine Spezialität des amerikanischen Mathematikers David A. Klarner (†1999).

Ein Puzzle im ERLEBNISLAND MATHEMATIK bezieht sich auf eine seiner zentralen Aussagen. Der Satz von Klarner besagt: Ein Rechteck der Dimension $a\times b$ , das aus Quadraten mit der Seitenlänge 1 besteht, lässt sich genau dann lückenlos mit $1\times n$ -großen Streifen ausfüllen, wenn mindestens eine der Seitenlängen $a$ oder $b$ durch $n$ teilbar ist. Das Rechteck im ERLEBNISLAND MATHEMATIK ist in $10\times 10$ , also $100$ Quadrate unterteilt. Die Streifen, mit denen diese Fläche ausgefüllt werden soll, bestehen aus vier Quadraten gleicher Größe, die in einer Reihe hintereinander angeordnet sind. $25$ dieser Streifen ergeben ebenfalls $100$ Quadrate.

Die Aufgabe, das Rechteck mit den Streifen vollständig abzudecken, ist jedoch nicht lösbar. Wenn $24$ Streifen auf die Fläche gelegt sind, bleibt in keinem Fall eine Reihe aus $4$ Quadraten für den 25. Streifen frei, sondern immer ein quadratisches Feld aus $2\times 2$ kleinen Quadraten. Der Satz von Klarner ist damit bestätigt, denn die Seitenlänge $10$ ist nicht durch die Streifenlänge $4$ teilbar.

Und nun … die Mathematik dazu:

Die Teilbarkeit der großen Fläche von $10\times 10$ Quadraten lässt sich gut veranschaulichen, wenn die Diagonalen mit vier unterschiedlichen Farben gekennzeichnet werden. Im ERLEBNISLAND MATHEMATIK sind die 10 Felder der Hauptdiagonalen von links unten nach rechts oben rot, die Felder der nach rechts unten sich anschließenden Nebendiagonalen blau, orange, grün und wieder rot gefärbt bis zum blauen Quadrat in der Ecke. In umgekehrter Reihenfolge werden die Nebendiagonalen nach links oben eingefärbt, also grün, orange, blau und wieder rot usw. bis zum grünen Quadrat in der Ecke (vgl. Abbildung 2). Mathematisch ausgedrückt: Wenn man jedes Quadrat mit einem Gitterpunkt $(x,y)$ im ebenen Gitter $\mathbb Z\times\mathbb Z$ identifiziert, werden diejenigen Gitterpunkte, bei denen $x-y$ zur selben Restklasse modulo $4$ gehören, mit derselben Farbe eingefärbt.

Verteilt man nun die Viererstreifen in beliebiger Anordnung, so bedeckt jeder Streifen immer je ein Quadrat von jeder der obigen vier Farben. Zählt man nun alle Quadrate jeder Farbe zusammen, so ergeben sich

$10+2\cdot 6+2\cdot 2=26$ rote Quadrate;
$9+5+1+7+3=25$ blaue Quadrate;
$2\cdot 8+2\cdot 4=24$ orange Quadrate;
$7+3+9+5+1=25$ grüne Quadrate.

Unser Fazit ist also: Wenn jeder Viererstreifen alle vier Farben abdeckt, haben nur so viele Streifen auf der großen Fläche Platz, wie Quadrate von der Farbe vorhanden sind, die am seltensten vorkommt. Im Beispiel sind das die $24$ orangen Quadrate. Ganz gleich, wie die Streifen gelegt werden, bleiben immer ein grünes, ein blaues und zwei rote Quadrate übrig. Eine Überdeckung dieser letzten vier Felder durch den letzten verbleibenden Streifen ist unmöglich!

Der Beweis des allgemeinen Satzes von Klarner — wie oben formuliert — ist nun einfach aus dem Beweis des im ERLEBNISLAND MATHEMATIK dargestellten Spezialfalls abzuleiten: Statt vier müssen nun $n$ Farben verwendet werden und wir färben die Punkte $(x,y)$ des Rechteckes $\{1,\ldots,a\}\times\{1,\ldots,b\}$ mit der zugehörigen Restklasse von $x-y$ modulo $n$ . Ein Streifen der Länge $n$ deckt dann stets je ein Quadrat (Gitterpunkt) von jeder der $n$ Farben ab. Ist eine der Längen $a$ oder $b$ (oder beide), sagen wir $a$ , durch $n$ teilbar, so können wir dies klar durch Streifen der Länge $n$ ausfüllen, indem wir einfach alle Streifen horizontal legen und somit $b$ „Schichten“ aus jeweils $a/n$ nebeneinander liegenden Streifen bilden.

Es folgt also insbesondere, dass in einem solchen Rechteck gleichviele Quadrate (Gitterpunkte) von jeder Farbe („Restklasse“) liegen müssen. Nun bleibt nur noch zu zeigen, dass sich ein Rechteck, bei dem weder $a$ noch $b$ durch $n$ teilbar sind, nicht durch Streifen der Länge $n$ auslegen lässt. Wir zeigen dies mithilfe der obigen Färbung. Wäre es nämlich möglich ein solches Rechteck mit Streifen der Länge $n$ auszulegen, dann müsste es in diesem Rechteck, da jeder solche Streifen genau ein Quadrat (Gitterpunkt) von jeder der $n$ Farben abdeckt, von jeder Farbe gleichviele Quadrate (Gitterpunkte) geben. Es genügt also zu zeigen, dass dies nicht der Fall ist. Indem wir von unserem Rechteck der Dimension $a\times b$ also erst ein Rechteck der Dimension $(n\lfloor a/n\rfloor)\times b$ „wegnehmen“, sodass wir ein neues Rechteck der Dimension $a'\times b$ mit $a'=a-n\lfloor a/n\rfloor$ erhalten, und anschließend ein Rechteck der Dimension $a'\times(n\lfloor b/n\rfloor)$ von diesem „subtrahieren“, erhalten wir ein Rechteck der Dimension $a'\times b'$ , wobei $b'=b-n\lfloor b/n\rfloor$ (hierbei bezeichnet $\lfloor x\rfloor$ die größte ganze Zahl $\leq x$ ). Dieses neue Rechteck erfüllt nun $0<a',b'<n$ (da $a$ und $b$ nicht durch $n$ teilbar waren) und wir zeigen, dass in ihm nicht alle Farben mit gleicher Häufigkeit auftreten können. Da in unseren „subtrahierten“ Rechtecken jede Farbe gleich oft auftritt, treten dann auch im ursprünglichen Rechteck nicht alle Farben mit der gleichen Häufigkeit auf.

Diese Behauptung ist aber leicht einzusehen, denn da $a',b'<n$ ist die einzige Möglichkeit, dass ein Gitterpunkt des neuen Rechtecks $\{1,\ldots,a'\}\times\{1,\ldots,b'\}$ , sagen wir $(x,y)$ , mit der Restklasse $0$ modulo $n$ eingefärbt wird, dass $x=y$ , denn anderenfalls müsste entweder $x$ oder $y$ größer als $n$ sein. Damit gibt es genau $m=\min(a',b')$ solcher Gitterpunkte. Würden nun alle Farben mit der gleichen Häufigkeit auftauchen, müsste unser Rechteck also genau $m\cdot n$ Punkte haben. Es ist aber leicht einzusehen, dass $a'\cdot b'<m\cdot n$ . Damit erhalten wir den gewünschten Widerspruch und der Satz von Klarner ist (in seiner vollen Allgemeinheit) bewiesen.

Literatur

[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.