Das folgende Theorem von Nicholas G. de Bruijn [1] kann man als dreidimensionale Verallgemeinerung des Theorems von Klarner für den zweidimensionalen Fall betrachten. Allerdings gilt es nur für sogenannte harmonische Klötzer, das sind solche mit Seitenlängen a, ab und abc für natürliche Zahlen a, b und c. Bei solchen harmonischen Klötzern ist die nächstlängere Seitenlänge also immer ein ganzzahliges Vielfaches der nächstkürzeren Seite. Beispiele sind Stäbe mit den Seitenlängen 1, 1 und 4 oder Klötzer mit den Seitenlängen 1, 2 und 4.
Das Theorem von de Bruijn klärt nun, wann genau eine Box vollständig mit solchen harmonischen Bricks gefüllt werden können:
Eine Box kann genau dann mit harmonischen Klötzern der Größe a x ab x abc gefüllt werden, wenn sie die Größe ap x abq x abcr für irgendwelche ganzzahlige p, q, r hat, d.h. die Box in jeder Richtung ein Vielfaches des Klotzes ist.
Damit lässt sich die Box auch auf ganz einfache Weise füllen, ohne Klötzer irgendwie drehen zu müssen. Die Aussage des Theorems ist also genau wie beim Theorem von Klarner: Wir können die Box entweder auf eine ganz einfache Weise mit harmonischen Klötzern füllen oder es geht gar nicht. Im ersten Fall, also wenn es klappt, kann man die Box manchmal auch auf eine komplizierte Art füllen. Aber immer, wenn es kompliziert möglich ist, dann ist es auch einfach möglich.
Das folgende Foto zeigt 24 harmonische Klötzer der Größe 1x2x4 gestapelt zu 4x6x8, links einfach, rechts komplizierter.
Aber Achtung, damit ist das Problem des Kistenpackens noch nicht vollständig gelöst, denn es gibt ja noch die nicht-harmonischen Klötzer (z.B. 1x2x3), für die das Theorem nichts aussagt. Es bleiben also noch eine Menge Aufgaben. Ein Beispiel ist das Singmaster Packing mit nicht-harmonischen Steinen der Größe 1x3x4
Das Theorem von de Bruijn lässt sich übrigens auch in höheren Dimensionen formulieren und gilt dort analog. Mangels Relevanz für Geduldspiele soll das hier aber nicht weiter betrachtet werden.
Mehr Infos:
[1] Wikipedia
Keine Kommentare:
Kommentar veröffentlichen