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 , das aus Quadraten mit der Seitenlänge 1 besteht, lässt sich genau dann lückenlos mit
-großen Streifen ausfüllen, wenn mindestens eine der Seitenlängen
oder
durch
teilbar ist. Das Rechteck im ERLEBNISLAND MATHEMATIK ist in
, also
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.
dieser Streifen ergeben ebenfalls
Quadrate.
Die Aufgabe, das Rechteck mit den Streifen vollständig abzudecken, ist jedoch nicht lösbar. Wenn Streifen auf die Fläche gelegt sind, bleibt in keinem Fall eine Reihe aus
Quadraten für den 25. Streifen frei, sondern immer ein quadratisches Feld aus
kleinen Quadraten. Der Satz von Klarner ist damit bestätigt, denn die Seitenlänge
ist nicht durch die Streifenlänge
teilbar.
Und nun … die Mathematik dazu:
Die Teilbarkeit der großen Fläche von 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. Abildung 2). Mathematisch ausgedrückt: Wenn man jedes Quadrat mit einem Gitterpunkt
im ebenen Gitter
identifiziert, werden diejenigen Gitterpunkte, bei denen
zur selben Restklasse modulo
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
rote Quadrate;
blaue Quadrate;
orange Quadrate;
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 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 Farben verwendet werden und wir färben die Punkte
des Rechteckes
mit der zugehörigen Restklasse von
modulo
. Ein Streifen der Länge
deckt dann stets je ein Quadrat (Gitterpunkt) von jeder der
Farben ab. Ist eine der Längen
oder
(oder beide), sagen wir
, durch
teilbar, so können wir dies klar durch Streifen der Länge
ausfüllen, indem wir einfach alle Streifen horizontal legen und somit
„Schichten“ aus jeweils
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 noch
durch
teilbar sind, nicht durch Streifen der Länge
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
auszulegen, dann müsste es in diesem Rechteck, da jeder solche Streifen genau ein Quadrat (Gitterpunkt) von jeder der
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
also erst ein Rechteck der Dimension
„wegnehmen“, sodass wir ein neues Rechteck der Dimension
mit
erhalten, und anschließend ein Rechteck der Dimension
von diesem „subtrahieren“, erhalten wir ein Rechteck der Dimension
, wobei
(hierbei bezeichnet
die größte ganze Zahl
). Dieses neue Rechteck erfüllt nun
(da
und
nicht durch
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 ist die einzige Möglichkeit, dass ein Gitterpunkt des neuen Rechtecks
, sagen wir
, mit der Restklasse
modulo
eingefärbt wird, dass
, denn anderenfalls müsste entweder
oder
größer als
sein. Damit gibt es genau
solcher Gitterpunkte. Würden nun alle Farben mit der gleichen Häufigkeit auftauchen, müsste unser Rechteck also genau
Punkte haben. Es ist aber leicht einzusehen, dass
. 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.