Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen
Das Theorem von D.A. Klarner [1] klärt endgültig, wann ein Rechteck der Größe axb vollständig mit Stäben der Größe 1xn gefüllt werden kann:
Ein Rechteck der Größe axb kann genau dann vollständig mit Stäben der Größe 1xn gefüllt werden, wenn eine der Seitenlängen a oder b durch n teilbar ist.
Zum Beweis müssen zwei Dinge gezeigt werden:
1. Es ist möglich, wenn eine der Seitenlängen durch n teilbar ist. Eine triviale Lösung findet man ohne Anstrengung: Wenn z.B. a=k*n, so kann man jeweils k Stäbe hintereinander in jede Reihe parallel zur Kante der Länge a legen. Und das macht man für jede der b Reihen (im Bild: k=2).
2. Es ist unmöglich, wenn keine der Seitenlängen durch n teilbar ist. Dieser Teil des Beweises soll nur skizziert werden. Wir verweisen auf die unlösbare Aufgabe, ein 10x10-Quadrat mit 1x4-Stäben zu füllen. Im allgemeinen Fall kann man ganz analog vorgehen, muss das Rechteck nur mit n Farben färben und sich vergewissern, dass nicht alle Farben gleich oft im axb-Rechteck vorkommen.
Damit ist die Aufgabe, ein Rechteck mit ganzzahliger Seitenlänge mit 1xn-Brettern zu füllen, recht einfach: Entweder es klappt durch einfaches, paralleles Stapeln der Bretter oder es klapp gar nicht.
Wie sieht es mit weiteren Verallgemeinerungen aus?
Wir können uns dem dreidimensionalen Fall mit 1x1xn-Stangen zuwenden. Lässt sich das Theorem von Klarner einfach verallgemeinern? Lässt sich speziell eine 5x6x6-Box mit 45 Stäben der Größe 1x1x4 füllen?
Das Theorem von Klarner löst das zweidimensionale Problem, ein Rechteck mit Stäben, also Rechtecken der Breite 1, zu füllen. Wie sieht es mit dem Füllen durch andere Rechtecke aus? Eine weitere allgemeine Aussage liefert das Theorem von De Bruijn.
Mehr Infos:
[1] Wikipedia
