Posts mit dem Label Kiste voller gleicher Teile werden angezeigt. Alle Posts anzeigen
Posts mit dem Label Kiste voller gleicher Teile werden angezeigt. Alle Posts anzeigen

31.1.26

Communication Box

Die Communication Box ist eine quaderförmige Kiste der Größe 3x3x4, die mit sieben identischen Steinen gefüllt werden soll. Die Schwierigkeit besteht darin, dass die Kiste nur auf einer Seite ein Öffnung hat, die auch nur fünf statt neun Elementarquadrate groß ist. Man muss alle sieben Steine nacheinander durch diese kleine Öffnung zwängen und hat im Inneren der Box nur wenig Platz, um mit den Steinen zu hantieren.

Normalerweise würde man die Steine als U-Pentominos bezeichnen, aber um 90 Grad gedreht sehen sie natürlich wie ein C aus. Und das hat mit dem Namen des Geduldspiels zu tun. In der Wissenschaft gibt es die sieben C’s der Kommunikation [1], nämlich Clear (klar), Concise (prägnant), Concrete (konkret), Correct (korrekt), Coherent (kohärent), Complete (vollständig) und Courteous (höflich). Diese sieben Cs liegen vor Ihnen und müssen in die Communication Box gepackt werden. Dabei bleibt übrigens ein Elementarwürfel frei, vielleicht für den Gegenstand der Kommunikation.

Schwierigkeit: Mittelschwer bis schwer. Einfach die Steine nacheinander in die Box packen führt nicht zum Ziel. Wir benötigen eine Strategie.

Im folgenden Bild sehen Sie die Steine außerhalb der Box zusammengesetzt zu einem 3x3x4-Quader (mit einer Leerstelle im Inneren), aber diese Konstruktion lässt sich wegen der reduzierten Öffnung nicht innerhalb der Box realisieren.

 

Design:  Volker Latussek
Hersteller und Artikelnummer:  Rombol Nr. 6370

Shopping: Lieferbar, Preis ca. 25€

Mehr Infos:

21.12.25

44 Steine der Größe 2x3x7 in eine Box 8x11x21 packen

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Vor uns liegen 44 gleiche Quader der Größe 2x3x7, und diese sollen in eine Box der Größe 8x11x21 gepackt werden. Wegen der extrem großen Anzahl von Steinen müssen wir planmäßig vorgehen, wenn wir das Puzzle lösen wollen.

Kann es überhaupt klappen? Die Gesamtanzahl von Elementarwürfeln der Steine und der Box stimmen überein, es sind jeweils 1848 Elementarwürfel. Und es gibt noch ein notwendiges Kriterium von de Bruijn, welches erfüllt sein muss: Die Seitenlängen eines kleinen Steins (2, 3 und 7) müssen Teiler der Seitenlängen der Box sein. Dies ist der Fall, so dass es klappen könnte.

Allerdings ist damit noch nicht klar, dass es klappen wird: Mit einer Box der halben Größe 4x11x21 und 22 Steinen der Größe 2x3x7 klappt es nämlich nicht, diese Aufgabe ist unlösbar, obwohl auch hier das Kriterium von de Bruijn erfüllt ist.

Aber die eigentliche Aufgabe mit 44 Steinen ist lösbar, und das Bild weiter unten zeigt die gestapelten Quader sozusagen in einer gläsernen Box. 

Schwierigkeit: Schwierig, aber auch für Menschen nicht unlösbar. Der Computer braucht nur Sekundenbruchteile. Falls Sie das folgende Bild zu Hilfe nehmen, wird es auch recht einfach.  

Ähnliches Geduldspiel: Singmaster Packing ist etwas einfacher.

Design:  David Klarner
DIY-Tipp: Selber basteln mittels 3D-Druck oder aus einer passenden Holzleiste sägen.



17.9.25

Sixmetry

Kategorie: Klassische Packwürfel

Das Puzzle von Vinco stellt uns vor eine scheinbar einfache Aufgabe: In einen 4x4x4-Würfel sollen sechs gleiche Teile gepackt werden. Jedes solche Teil ist auf die gleiche Art aus einem 1x2x3-Klotz und einem 1x2x2-Klotz zusammengeklebt. Damit besteht jedes Teil aus 10 Elementarwürfeln, in der Kiste ist Platz für 4*4*4=64 Elementarwürfel. Es werden also irgendwo vier Elementarwürfel frei bleiben.

Die Teile der Größe 1x2x3 und 1x2x2 sind aus mehreren verschiedenen Hölzern gefertigt. Beim Kauf erhält man die Kiste gepackt mit einer Beinahe-Lösung, der letzte Stein schaut oben aus der Kiste heraus. Das sieht dann so aus: 

Schwierigkeit: Sehr schwierig, Vinco vergibt 5 von 5 Punkten. Mit der richtigen Idee wird es etwas einfacher. Mitgeliefert wird ein Beipackzettel, der sowohl eine Beinahe-Lösung wie auch die vollständige Lösung enthält. Die Aufgabe, eine Beinahe-Lösung zu finden, sollte übrigens für fast jeden lösbar sein.

Außerdem erinnert der Name Sixmetry irgendwie an Symmetrie, oder? Man könnte also auf irgendeine Art Symmetrie in der Lösung hoffen.

Sixmetry war das Austauschpuzzle von Patrick Major auf IPP41. 

 

Design:  David Goodman
Hersteller und Artikelnummer:  Vinco, Nr. 589
Erscheinungsjahr: 2024

Google: Sixmetry
Shopping: Lieferbar, Preis ca. 15€

13.11.24

Eine Box der Größe 7x7x13 gefüllt mit 78 Steinen 1x2x4 und 13 Löchern

Wie viele 1x2x4-Klötzer lassen sich in eine Box der Größe 7x7x13 packen? Vom Volumen her könnten 79 Klötzer hineinpassen und noch 5 Elementarwürfel frei bleiben. Könnte das klappen? Nach kurzem Nachdenken können wir die Idee verwerfen: In unserer Box muss in jeder Schicht der Höhe 1 mindestens ein Elementarwürfel frei bleiben, da unabhängig von seiner Lage ein Klotz immer eine gerade Anzahl von Elementarwürfeln pro Schicht belegt.

Bei einer Höhe von 13 bleiben also mindestens 13 Elementarwürfel frei und wir können maximal (7*7*13-13) / 8 = 78 Klötzer einpacken. Ob uns das gelingt?

Die Antwort ist ja, und wir wollen hier auch eine Lösung zeigen, die schon mindestens seit 1992 bekannt ist [1]. Aber vorher noch eine Bemerkung: In vielen Fällen, wie z.B. in der 7x7x7-Box müssen mehr Elementarwürfel frei bleiben als es die größte Seitenlänge verlangt. Dass in unserer Aufgabe wirklich nur 13 Elementarwürfel frei bleiben, ist also ein erfreulicher Spezialfall, der uns die Lösung besonders schwer macht.

Hier eine der möglichen Lösungen, die 13 Lücken wurden hier mit blauen Elementarwürfeln gefüllt. 


Die folgenden Fotos zeigen den schrittweisen Aufbau. Im ersten Bild ist links die unterste Schicht abgebildet, rechts die daraufzulegende zweite Schicht.

Bei den folgenden Bildern wurden links jeweils die beiden Teile aus dem darüberstehenden Bild aufeinandergelegt und rechts wird die nächste Schicht gezeigt.




Hier folgt rechts die ganz oben aufzulegende letzte Schicht.

Es bleibt die Frage, wie man eine solche Lösung findet. Es gibt sicher sehr viele verschiedene Lösungen, trotzdem sind sie nicht einfach zu finden. Auch der Computer wird wegen der großen Anzahl von Steinen schnell überfordert, zumindest der PolySolver findet in annehmbarer Zeit keine Lösung.

DIY-Tipp: Man kann die Bauklötzer im Internet direkt bestellen. Achten Sie auf das Seitenverhältnis 1:2:4. Vielleicht werden Sie auch bei Ihren Kindern fündig. Alternativ ist auch 3D-Druck möglich.

Mehr Infos: 

[1] F.W. Barnes: How many 1×2×4 bricks can you get into an odd box?. Discrete Mathematics Vol. 133, Pages 55-78, Elsevier 1994 


Quader ungerader Seitenlängen packen mit 1x2x2-Klötzern

Beim 3x3x3-Conway-Würfel erwies es sich als schwierig, 6 Klötzer der Größe 1x2x2 in einen 3x3x3-Würfel zu packen. Die Größe der Box soll hier verallgemeinert werden: Wir wollen zunächst einen 3x3x7-Quader, danach einen 3x7x11-Quader und schließlich beliebige Quader mit ungeraden Seitenlängen mit den solchen 1x2x2-Klötzern füllen. Natürlich bleiben einige Löcher, und zwar mindestens in jeder Schicht eins, da ein Klotz pro Schicht entweder zwei oder vier Elementarwürfel belegt. 

Aufgabe 1: Packen Sie 14 Klötzer der Größe 1x2x2 in einen 3x3x7-Quader! Es bleiben genau 7 Löcher, in jeder der sieben Schichten eines.
Lösungshinweis: Packen Sie 5 der 7 Löcher ins Innere des Quaders, so dass man sie von außen nicht sieht. Diese Lösung lässt sich verallgemeinern für alle Quader der Größe 3x3x(2n+1). Man startet bei n=1 mit dem 3x3x3-Conway-Würfel und verlängert diesen einfach, indem man jeweils einen Ring von vier Klötzern einfügt. 


Die drei Klötzer im Vordergrund passen als Deckel auf das hintere Teil. Ganz vorn links oben bleibt ein Elementarwürfel frei (siehe Bild unten).

Ein einziger leerer Elementarwürfel pro Schicht reicht aber in anderen Fällen nicht aus, wie das folgende Beispiel zeigt:

Aufgabe 2: Wie viele 1x2x2-Klötzer passen in einen 3x7x11-Quader? Der Quader besteht aus 11 Schichten der Größe 3x7, deshalb müssen mindestens 11 Elementarwürfel frei bleiben. Passen (3x7x11-11)/4=55 Klötzer in unseren Quader? Das klappt nicht, aber mit 54 klappt es. Für die abgebildete Lösung verwenden wir den 3x3x7-Quader von oben und ergänzen ihn um acht Schichten der Größe 3x1x7, also einen 3x8x7-Quader. In jeder der acht hinzugefügten Schichten bleibt wieder eine einzelne Lücke.


Bleibt die Frage, wieso der Stein Nummer 55 nicht mehr hineinpasst. Wir können wieder eine schachbrettähnliche Färbung anwenden, und zwar diesmal mit vier Farben. Wir bezeichnen die vier Farben mit A, B, C und D und ordnen sie folgendermaßen an:

Schicht 1:   C  B  C  B  C  B  C  B  C  B  C  
         A  D  A  D  A  D  A  D  A  D  A  
         C  B  C  B  C  B  C  B  C  B  C  
         A  D  A  D  A  D  A  D  A  D  A   
         C  B  C  B  C  B  C  B  C  B  C  
         A  D  A  D  A  D  A  D  A  D  A  
         C  B  C  B  C  B  C  B  C  B  C  

Schicht 2:   D  A  D  A  D  A  D  A  D  A  D
         B  C  B  C  B  C  B  C  B  C  B
         D  A  D  A  D  A  D  A  D  A  D
         B  C  B  C  B  C  B  C  B  C  B
         D  A  D  A  D  A  D  A  D  A  D
         B  C  B  C  B  C  B  C  B  C  B
         D  A  D  A  D  A  D  A  D  A  D

Schicht 3:  wie Schicht 1

Unabhängig von seiner Lage belegt jeder Klotz vier Elementarwürfel verschiedener Farbe. Aber es gibt nicht gleichviele Elementarwürfel in den verschiedenen Farben: Wir finden 56 mal A, 58 mal B, 63 mal C und nur 54 mal D. Damit können wir maximal 54 Klötzer in die Box packen. Dass dies tatsächlich klappt, zeigt das Foto oben.

Dieser Beweis geht auf F.W. Barnes [1] zurück und lässt sich auf beliebige Boxen mit ungerader Seitenlänge übertragen:

In einen Quader mit ungeraden Seitenlängen a ≤ b ≤ c lassen sich ¼(abc+a-b-c) Klötzer der Größe 1x2x2 packen, dabei bleiben genau b+c-a Elementarwürfel frei. 

Mit der Färbung oben kann man zeigen, dass mindestens b+c-a Elementarwürfel frei bleiben, zusätzlich muss man eine Füllung mit der entsprechenden Anzahl von Klötzern angeben. Hier kann man nacheinander immer größere Quader betrachten, indem man die Seitenlängen jeweils um 2 vergrößert und eine Randschicht um den vorhergehenden Quader baut. Details in [1].

DIY-Tipp: Man kann die Bauklötzer im Internet direkt bestellen. Achten Sie auf das Seitenverhältnis 1:2:2. Vielleicht werden Sie auch bei Ihren Kindern fündig. Alternativ ist auch 3D-Druck möglich. Beispielweise gab es beim 3x3x3-Conway-Würfel einen passenden Stein.

Mehr Infos: 

[1] F.W. Barnes: How many 1×2×4 bricks can you get into an odd box?. Discrete Mathematics Vol. 133, Pages 55-78, Elsevier 1994.

19.10.24

54 S Puzzle

Dies ist eine Abwandlung des 54 T Puzzles, statt T-Tetrominos werden hier aber S-Tetrominos verwendet. Die Aufgabe besteht also darin, 54 S-Tetrominos in eine 6x6x6-Kiste zu packen. Da dieses Geduldspiel gerade nicht im Handel ist, hier eine 3D-gedruckte Variante. Details zum Selberdrucken gibt es unten.



Schwierigkeit: Das Geduldspiel ist knifflig, sogar kniffliger als das 54 T Puzzle. Es kommt beim Packen zwar nicht auf die Reihenfolge der Steine an, aber trotzdem sollte man planvoll vorgehen. Man könnte es schichtenweise versuchen und zunächst eine 1x6x6-Schicht zusammenfügen, um dann sechs solche Schichten übereinander zu legen. Das ist aber leider unmöglich, ebenso lassen sich keine Teilquader der Größe 2x6x6 oder 3x6x6 zusammenbauen. 

Der Würfel der Größe 6x6x6 ist eine sogenannte prime Box, lässt sich also nicht vollständig in kleinere füllbare Quader zerlegen. Unten finden Sie die Liste der primen Boxen, die sich mit den maximal 54 S-Tetrominos füllen lassen. Dies sind zusätzliche Aufgaben, die uns leider nicht helfen. Beim 54 T puzzle waren wir in einer komfortableren Situation. 

Hier die zusätzlichen Aufgaben:

Aufgabe 1: Setzen Sie die folgenden Quader zusammen (siehe die Liste [1] von Michael Reid)!
  • aus 8 S-Stücken einen 2x4x4-Quader, 
  • aus 10 S-Stücken einen 2x4x5-Quader, 
  • aus 30 S-Stücken einen 2x6x10-Quader.
Aufgabe 2: Zeigen Sie, dass sich aus 9 T-Stücken kein 3x3x4-Quader zusammensetzen lässt. 

Shopping: Nicht lieferbar.

3D-Druck: Das S-Tetromino finden Sie (zusammen mit anderen Tetrominos) an mehreren Stellen im Web, z.B. bei Thingiverse oder Printables. Oder schnell selbst in der gewünschten Größe modellieren mit PuzzleCAD.

Mehr Infos:
[1] Michael Reid: cflmath.com/Polyomino


9.10.24

Eine 5x6x6-Box füllen mit Stäben der Größe 1x1x4

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Gegeben ist eine 5x6x6-Box und dazu 45 Stäbe der Größe 1x1x4 und dazu noch ein Quader der Größe 1x2x2. Dazu gibt es drei Aufgabenstellungen, die leider nicht alle lösbar sind:

  • Füllen Sie die Box mit den 45 Stäben.
  • Füllen Sie die Box mit 44 Stäben und dem Quader.
  • Versuchen Sie dabei, den Quader im Inneren zu platzieren, so dass er von außen (ohne Box) nicht sichtbar ist.

Die unlösbare erste Aufgabe stammt von Nicolas de Bruijn, (vermutlich) aus den 1960er Jahren.

Obwohl es von der reinen Anzahl der 180 Elementarwürfel (für die 5x6x6-Box und auch für 45 Stäbe der Größe 1x1x4) klappen könnte, findet man so schnell keine Lösung. Nach dem Klarner-Theorem und dem dazugehörigen Motto "Einfach oder gar nicht" vermutet man, dass es vielleicht keine Lösung gibt. Um das zu beweisen, muss man die Elementarwürfel der quaderförmigen Box passend einfärben und kann dann genau wie im zweidimensionalen Fall argumentieren.

Frage: Wie genau könnte man die Elementarwürfel (diesmal in drei statt nur zwei) Dimensionen einfärben?

Dagegen klappt es wieder, 44 der geplanten 45 Stäbe in die Box zu packen. Dann bleiben vier leere Elementarwürfel, manchmal auch als 1x2x2-Quader.

Aber, und jetzt wird es merkwürdig: Der 1x2x2-Quader ist immer von außen sichtbar. (Stimmt das? Statt dies nachzuprüfen, widmen wir uns gleich der folgenden, etwas allgemeineren Frage.)

Wie ist das, wenn die vier einzelnen Elementarwürfel nicht unbedingt zusammenhängen müssen? Kann dann einer der Elementarwürfel im Inneren  der Box liegen?

Bei manchen Geduldspielen gibt es die Geschichte, dass in solch einem freien Elementarquader ein Holzwurm leben möchte, und dieser möchte in einer abgeschlossenen Wohnung leben. Das heißt, die Wohnung soll keine Verbindung nach außen haben. 

Können wir diese Fragestellung mit dem PolySolver lösen? Wir können einen Elementarwürfel mit der Option "Place" fest verankern und sehen, ob sich die verbleibenden 44 Stäbe und drei Elementarwürfel in der Box unterbringen lassen. Wie viele Positionen für den verankerten Würfel müssen wir testen? (Es müssen nur sechs Positionen betrachtet werden. Der PolySolver findet dafür keine Lösung.)

Damit haben wir wieder ein Problem für einem unglücklichen Holzwurm gefunden.

Und dann ist da noch der Missbrauch eines unlösbare Geduldspiels, um ungeliebte Gäste möglichst lange zu beschäftigen, wie schon in diesem Post ganz unten zu lesen ist. Dieses Geduldspiel eignet sich hervorragend.

Design:  Nicolas de Bruijn u.a.

DIY-Tipp: Dies ist ein schönes Geduldspiel zum Selberbauen auch für Anfänger. Aus einer Holzleiste mit quadratischem Querschnitt können Sie die passenden Stäbe der Größe 1x1x4 absägen. Oder mittels CAD-Software (wie z.B. OpenSCAD)  den Stab modellieren und dann 3D-drucken.

21.9.24

Einen 7x7x7-Würfel füllen mit 41 Klötzern der Größe 1x2x4 und 15 Elemenrarwürfeln

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Eigentlich könnte man hoffen, dass 42 Klötzer der Größe 1x2x4 in einen 7x7x7-Würfel passen und dann noch sieben Elementarwürfel frei bleiben. Das klappt aber leider nicht, wie schon im Jahr 1976 gezeigt wurde [1]. Aber mit 41 statt 42 klappt es:

Aufgabe: Packen Sie 41 Klötzer der Größe 1x2x4 und 15 Elementarwürfel in einen 7x7x7-Würfel! Wenn Sie es noch etwas schwieriger haben wollen: Es klappt auch mit 4 Stück 1x1x3 plus drei Elementarwürfeln statt der 15 Einzelwürfel.


Auch wenn wir wissen, dass es sich um eine lösbare Aufgabe handelt, kommt man durch Herumprobieren nicht zum Ziel. Gibt es vielleicht einfachere Teilaufgaben? Im Schnitt dürfen in einer Schicht von 7x7 Würfeln reichlich zwei Elementarwürfel frei bleiben. Bei geradzahliger Höhe geht es aber besser: Wir können es relativ einfach schaffen, dass nur ein Elementarwürfel pro Schicht frei bleibt, und zwar genau der mittlere Elementarwürfel. Hier das Bild für 7x7x2:

Verringern wir also die Höhe um zwei, müssen wir einen 5x7x7-Quader mit 29 Steinen der Größe 1x2x4 füllen. Vielleicht scheint dies für den Menschen auf den ersten Blick nicht einfacher zu sein, aber der Computer zeigt mit dem PolySolver einen dramatischen Unterschied.

PolySolver-Info: Für die 7x7x7-Aufgabe findet der PolySolver innerhalb 10 Minuten rund 60.000 Lösungen (und würde noch mehr finden), die erste Lösung findet er nach sechseinhalb Minuten. Bei der "etwas kleineren" 5x7x7-Aufgabe findet der PolySolver blitzartig die erste Lösung und sofort weitere.

Um es für uns Menschen noch einfacher zu machen: Klappt derselbe Trick noch einmal, d.h. können wir einen 7x7x3-Quader mit 17 Steinen der Größe 1x2x24 füllen? Leider nein! Damit sind 2x7x7 und 5x7x7 die einzigen Schichthöhen, die wir unter den gegebenen Nebenbedingungen mit 1x2x4-Steinen füllen können.

Anders als beim Theorem von De Bruijn, dass uns nur sagt, wann eine Box sich vollständig mit Steinen gleicher Größe füllen lässt (oder auch nicht), ist die Situation bei den speziellen Steinen der Größe 1x2x4 noch besser: F.W. Barnes beschreibt in [2] genau, wie viele solche Steine in eine beliebige Box mit ganzzahliger Seitenlänge passen und wie viele Elementarwürfel übrigbleiben müssen. Wir werden darauf noch zurückkommen.

Mehr Infos: 

[1] M. Mather: Solution to Problem E2524, Amer. Math. Monthly 83 (1976) S. 741-742.
[2] F.W. Barnes: How many 1×2×4 bricks can you get into an odd box?. Discrete Mathematics Vol. 133, Pages 55-78, Elsevier 1994 


Übersicht: Gleiche Klötzer in rechtwinklige Boxen packen


Hier finden Sie alle systematischen Übersichten.

Viele gleiche Klötzer sollen in eine rechtwinklige Box passender Größe gepackt werden. Klötzer packen können wir in zwei oder drei Dimensionen: Die Klötzer sind entweder Rechtecke (2D) oder Quader (3D), die Boxen ebenfalls Rechtecke oder Quader. Es sollen jeweils eine bestimmte Anzahl gleicher Klötzer eingepackt werden, die Seitenlängen der Klötzer sind ganzzahlig. Bei den meisten Aufgaben sollen die Boxen vollständig gefüllt werden. Manchmal bleiben auch einige Elementarwürfel frei oder sollen mit zusätzlichen kleinen Steinen gefüllt werden. Es gibt auch unlösbare Aufgaben, bei denen sich die Klötzchen einfach nicht einpacken lassen wollen und man diese Unmöglichkeit auch beweisen kann.

Rechtecke packen

Viele gleiche Rechtecke in eine Box passender Größe zu packen, sieht einfach aus, ist manchmal aber sehr vertrackt oder gar unmöglich. Ein wenig Theorie hilft manchmal.

Aufgaben

Manche Aufgaben sind relativ einfach, andere so schwierig, dass der Computer helfen muss.
  • 21 I-Trominos auf Schachbrett
  • Erscheint im Dezember: Schwierig für Mensch und Computer: 147 Rechtecke der Größe 95x137 in ein Rechteck der Größe 1230x1600 packen

Unlösbare Aufgaben

Findet selbst der Computer keine Lösung, kann man versuchen, die Unlösbarkeit zu beweisen. Hilfreich sind oft Färbungen mit einem Schachbrett- oder einem anderen Muster.

Quader packen

Auf den ersten Blick sieht die dreidimensionale Version des Packproblems nicht viel anders aus als die zweidimensionale. Aber es gibt aus kombinatorischer Sicht mehr Möglichkeiten und andere theoretische Resultate.

Lösbare Aufgaben

Manche Aufgaben sind relativ einfach, andere so schwierig, dass der Computer helfen muss. Bei umfangreicheren Aufgaben kommt auch der Computer schnell an seine Grenzen

Unlösbare Aufgaben

Findet man keine Lösung, kann man versuchen, die Unlösbarkeit zu beweisen. Hilfreich sind wieder Färbungen oder das Theorem von de Bruijn.

18.9.24

Singmaster Packing

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Aufgabe: Packen Sie 25 Klötzer der Größe 1x3x4 in einen 5x5x12-Quader!

Dieses Geduldspiel von David Singmaster gibt es als Original in einer Version mit den Steinen aus sehr schönen Hölzern in einer hölzernen Box. Die hier abgebildete Variante als 3D-Druck findet sich in den Modellen zu diesem Blog unter den ganz unten angegebenen Links.


Das Geduldspiel besitzt 22 verschiedene Lösungen, die sich nicht wesentlich unterscheiden. PolySolver findet 140 Lösungen. Das ist weniger als das Achtfache, weil einige Lösungen eine größere Symmetrie besitzen.

Das Geduldspiel entstand auf der Suche nach dem einfachsten nichttrivialen Packproblem zum Einpacken gleicher quaderförmiger Teile in eine quaderförmige Box. Das Theorem von de Bruijn sagt uns, dass die Box nicht ein Vielfaches eines Steins sein soll, weil dann die Steine ohne Nachdenken einfach hineingestapelt werden können. Die Seitenlängen der Klötzer sind durch 2 (sogar durch 4) und 3 teilbar, deshalb hat die Box zweimal die dazu teilerfremde Seitenlänge 5. Die dritte Seite muss nach dem Theorem von de Bruijn sowohl durch 4 als auch durch drei teilbar sein. Damit ist 12 die kleinste solche Seitenlänge. 

Wenn man es mit kleineren Klötzern der Größe 1x2x3 versucht, wäre 5x5x6 die kleinste nichttriviale Box. Diese lässt sich aber ganz einfach schichtenweise einpacken, da bereits eine Box 1x5x6 mit fünf Steinen zu füllen ist.

Design:  David Singmaster
Hersteller: verschiedene
Erscheinungsjahr: 1970er Jahre

Google: Singmaster Packing
Shopping: Aus edlen Hölzern selten gebraucht lieferbar, Preis ca. 70€

3D-Druck:  Sie finden das STL-File in der Sammlung zum Blog auf Thingiverse sowie bei Printables.

Das Kriterium von N. de Bruijn für beliebige Klötzer

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Das Packproblem für harmonische Klötzer (das sind solche mit Seitenlängen a, ab und abc) in eine quaderförmige Box wird durch das Theorem von de Bruijn vollständig gelöst. Aber wie ist das mit allgemein Klötzern mit ganzzahliger Seitenlänge?

Der allgemeine Fall ist nicht vollständig gelöst, aber es gibt das folgende Kriterium von de Bruijn, welches erfüllt sein muss, damit es überhaupt möglich sein könnte, eine Box vollständig zu füllen.

Damit eine Box mit den Seitenlängen A, B und C sich vollständig mit Klötzern der Seitenlängen a, b und c füllen lässt, muss folgendes gelten:

  • eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von a, 
  • eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von b und 
  • eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von c.
Dabei kann durchaus beispielsweise C Vielfaches sowohl von a und b sein und weder A noch B Vielfache von a oder b. So kann man fünf Klötzer der Größe 1x2x3 in eine Box der Größe 1x5x6 packen:
Hier haben die Seitenlängen 2 und 3 des Klotzes als gemeinsames Vielfaches die Seitenlänge 6 der Box.

Andererseits ist reicht das Kriterium nicht aus, um die Lösbarkeit auch sicherzustellen. Ein einfaches Gegenbeispiel dafür ist ein 1x2x3-Klotz, den man nicht in eine 1x1x6-Box packen kann, obwohl das Kriterium erfüllt ist.  

Mehr Infos: 

[1] Wikipedia

11.9.24

Unlösbar: Einen 6x6x6-Würfel füllen mit 27 Klötzern der Größe 1x2x4

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Dies ist ein schönes Geduldspiel, um Kindern oder anderen Anfängern zu zeigen, dass ein Geduldspiel leicht lösbar aussehen kann, es aber nicht ist. Man kann lange herumprobieren, wird aber keine Lösung finden. 

27 Klötzer der Größe 1x2x4 sollen in einen 6x6x6-Würfel gepackt werden. Vom Volumen her könnte es gerade klappen, Box und Steine haben jeweils ein Volumen von 6x6x6 = 27x1x2x4 = 216 Elementarwürfeln. Aber spätestens beim letzten Klotz werden wir scheitern.

Nimmt man statt des letzten 1x2x4-Steins einen 2x2x2-Würfel, wird es recht einfach.

Lösbare Alternative im Bild: 26 Klötzer der Größe 1x2x4 und ein 2x2x2-Würfel passen in einen 6x6x6-Würfel.

Schwierigkeit: Einfach, gut geeignet für Kinder, sobald sie das Volumen der Quader ausrechnen können.

Frage: Kann der 2x2x2-Würfel auch genau in der Mitte der 6x6x6-Box liegen? Wenn nein, warum nicht?

Warum findet man eigentlich keine Lösung für die Ausgangsaufgabe mit 27 gleichen Klötzern der Größe 1x2x4? Es gibt mehrere Erklärungen, zwei werden in den Lösungshinweisen vorgeschlagen.

 

 

Im Vergleich zu der Aufgabe, einen 6x6x6-Würfel füllen mit 54 Stäben der Größe 1x1x4, fällt folgender Zusammenhang auf, wenn wir jeden 1x2x4-Klotz in zwei 1x2x4-Stäbe zerteilen: Aus jeder Lösung unseres Problems hätten wir automatische eine Lösung für die 1x1x4-Stäbe. Und andersherum: Wenn wir wissen, dass es keine Lösung für die 1x1x4-Stäbe gibt, kann es also auch keine für unsere 1x2x4-Klötzer geben.

DIY-Tipp: Holzbausteine der Größe 1x2x4 gibt es im Spielzeughandel.

Unlösbar: Einen 6x6x6-Würfel füllen mit 54 Stäben der Größe 1x1x4

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Bei der T-Teufelei ist es uns schon gelungen, den 6x6x6-Würfel mit 54 T-Tetrominos zu füllen, dann klappt es vielleicht auch mit 54 I-Tetrominos, also Klötzern der Größe 1x1x4.  

Obwohl sich I-Tetrominos besser lückenlos packen lassen als T-Tetrominos, gelingt es auch nach mehreren Versuchen nicht, die Box voll zu packen. Was tun?

 

Welche einfacheren Aufgaben sind lösbar?
  • 52 I-Tetrominos sind möglich, weil 26 Klötzer der Größe 1x2x4 möglich sind.
  • Sind 53 von 54 I-Tetrominos möglich? Nein. Man sieht dies mit einer 3x3x3-Schachbrettfärbung des Würfels.
  • 52 I-Tetrominos und ein 2x2x2-Würfel sind möglich. Der 2x2x2-Würfel kann nur an den Ecken oder in  der Mitte einer Seitenfläche des 6x6x6-Würfels liegen, ist also immer von außen sichtbar.
  • 52 I-Tetrominos und zwei 1x2x2-Quader (O-Tetrominos) lassen sich so im 6x6x6-Würfel unterbringen, dass sie nicht von außen sichtbar sind. Fällt Ihnen ohne die entsprechenden Steine eine Möglichkeit ein?


Harmonische Klötzer packen: Das Theorem von N. de Bruijn

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

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



23.6.24

125er Cube Z / Shipper's Dilemma Z

Der 125er Cube Z ist die Fortsetzung des 125er Cube Y, und die 25 identischen Steine haben ja auch eine gewisse optische Ähnlichkeit mit dem Buchstaben Z. Hier handelt es sich um sogenannte N-Pentominos, da ebenfalls eine Ähnlichkeit zum Buchstaben N besteht und bereits anderes Pentomino den Namen Z-Pentomino trägt.  

25 N-Pentominos passen lückenlos in einen 5x5x5-Würfel. Konzeptionell ist dieses Geduldspiel ähnlich zum 125er Cube Y, bei dem aber Y-Pentominos verwendet wurden.


Steine und Box lassen sich einfach mittels 3D-Druck modellieren und drucken, für die Fotos wurde das unten angegebene Modell von Matt Gard (smokeandlights) genutzt.

Schwierigkeit: Extrem schwierig, da es keinerlei erkennbare Regelmäßigkeit bei der Anordnung der N-Pentominos gibt. Es gibt auch nur vier verschiedene Lösungen verglichen mit 1264 Lösungen beim Y-Pentomino.

In der größten Not kann der PolySolver helfen, er findet alle Lösungen in weniger als vier Minuten.

Zusätzliche Aufgaben: Welche anderen Quader lassen sich mit maximal 25 N-Pentominos füllen? Das haben wir bereits im Blogpost Kisten packen mit N-Pentominos zusammengestellt.

Alternativer Namen: Great Z Cube

Design:  klassisch
Hersteller: Creative Crafthouse und andere

Google: Shipper's Dilemma Z
Shopping: Aus dem Ausland lieferbar, Preis ca. 20€

D-Druck: Die STL-Datei von Matt Gard (smokeandlights) für den 3D-Druck unter der Lizenz CC-BY-NC gibt es bei Thingiverse.

 

22.5.24

Six-T-Puzzle

Es gab schon mehrere Geduldspiele, bei denen vier T's eingepackt werden sollen (Z.B. das T-Pausen-Puzzle oder das schlanke T-Puzzle), diesmal sind es sogar 6 T's. Sie bestehen jeweils aus fünf Elementarwürfeln (es handelt sich also um T-Pentominos) und sollen in eine Box der Größe 3x3x4 gepackt werden. Dabei bleiben einige Elementarwürfel frei.

Das wäre ganz einfach, wenn es nicht noch eine zusätzliche Schwierigkeit gäbe: Die einzige Öffnung der Box befindet sich an der Schmalseite und hat gerade die Größe eines T.

Schwierigkeit: Durch die kleine Öffnung der Box wird das Geduldspiel interessant, aber die Lage ist nicht hoffnungslos. Angenehm mittelschwer.

 

Design:  Volker Latussek
Hersteller:  Rombol
Erscheinungsjahr: 2017

Google: Six-T-Puzzle
Shopping: Lieferbar, Preis ca. 25€

13.1.24

Unmöglich: 15 Quader der Größe 1x2x4 in eine 5x5x5-Kiste packen

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Einfaches Nachzählen der Elementarwürfel ergibt, dass die 5x5x5-Kiste über 125 Elementarwürfel verfügt, und die Klötzer davon 15x8=120 benötigen. Es werden also fünf Elementarwürfel frei bleiben. Dann sollten sich die 15 Quader doch in die Kiste packen lassen!

Leider stimmt das nicht, die 15 Quader lassen sich nicht in eine 5x5x5-Kiste packen. Zumindest der letzte Stein lässt sich nicht mehr einpacken. Dies ist damit nicht die größere Version des 3x3x3-Conway-Würfels, denn es gibt gar keine Lösung, speziell nicht mit den 5 freien Feldern auf einer Raumdiagonale.

DIY-Tipp: Für Heimwerker ist hier nicht viel zu tun, man kann die Bauklötzer im Internet direkt bestellen. Vielleicht werden Sie auch bei Ihren Kindern fündig. Für das Foto wurde nur noch eine 5x5x5-Kiste mit dem 3D-Drucker gedruckt.

Wie können wir sicher sein, dass es keine Lösung gibt? Wir haben verschiedenen Möglichkeiten:

1. Wir können den Computer zu Hilfe nehmen und mit dem PolySolver auf die Suche nach Lösungen gehen: Er findet keine. 

2. (Update 10/2024) Wer nach einer für Menschen verständlicheren Begründung sucht, kann wieder ähnlich wie beim 3x3x3-Conway-Würfel argumentieren. Wir benötigen aber einen zusätzlichen Trick. Der folgende Beweis stammt von Martin Gardner [1]: Wenn es klappen würde, blieben genau fünf Elementarwürfel frei. Da jeder 1x2x4-Stein unabhängig von seiner Lage eine gerade Anzahl von Elementarquadraten pro Schicht belegt, müsste in jeder der fünf Schichten der Box genau ein Elementarwürfel frei bleiben, und das gilt für die waagerechten Schichten genauso wie für die aufrecht stehenden Schichten in jeder Richtung. Jetzt betrachten wir die von außen sichtbaren Elementarquadrate auf der Oberfläche unseres 5x5x5-Würfels. Insgesamt besteht die Oberfläche aus 6*25=150 Elementarquadraten. Auf jeder Seitenfläche gehört eines davon zu einem freigebliebenen Elementarwürfel, bleiben 144 Elementarquadrate. Nun liegt jeder der 15 Quader mit genau einer der kleinen Seitenflächen der Größe 1x2 an einer Außenseite des 5x5x5-Würfels, diese belegen weitere 30 Elementarquadrate. Damit bleiben noch 144-30=114Elementarquadrate, die durch die größeren Seiten (1x4 oder 2x4) gefüllt werden müssen. Da 114 aber nicht durch 4 teilbar ist, ist das nicht möglich und wir haben einen Widerspruch gefunden. Also lassen sich nicht fünfzehn Steine der Größe 1x2x4 und fünf Elementarwürfel in eine 5x5x5-Kiste packen.

Wenn Sie noch auf der Suche nach einem Erfolgserlebnis sind: Wir können 14 statt 15 Quader der Größe 1x2x4 in die Kiste packen und dazu noch drei Stäbe der Größe 1x1x4. Dann bleibt nur ein Elementarwürfel frei! Und diese Aufgabe ist gar nicht so schwer.

Google: Holzbausteine Quader

Mehr Infos:
[1] Martin Gardner: Time Travel and other mathematical bewilderings, W.H. Freeman, New York, 1988

30.4.23

31 T-Tetrominos in einen 5x5x5-Würfel packen

Haben Sie 31 T-Tetrominos für ein weiteres Packproblem? Falls Sie die T-Teufelei bzw. das 54 T Puzzle besitzen, können Sie sich die 31 T-Tetrominos dort ausleihen. 

Die Aufgabe besteht darin, die 31 Tetrominos in eine 5x5x5-Kiste zu packen. Dabei wird genau ein Elementarwürfel in der Kiste frei bleiben (31*4+1=5*5*5).

Schwierigkeit: Einfach, es gibt Millionen von Lösungen.

Aber wir können die Aufgabe ein wenig verkomplizieren: Wo genau kann sich der frei bleibende Elementarwürfel befinden? Wenn Sie versuchen, eine Ecke der Kiste frei zu halten, dann wird das nicht gelingen. Hilfreich ist eine schachbrettartige Färbung der Elementarwürfel in der 5x5x5-Kiste. Dann beobachten wir, dass der leerbleibende Elementarwürfel niemals die gleiche Farbe wie ein Eckwürfel hat.

Frage 1: Können Sie diese letzte Aussage beweisen? Einen Hinweis finden Sie bei dieser Aufgabe mit T-Tetrominos.

Frage 2: Kann jeder der Elementarwürfel in der anderen Farbe leer bleiben? Die Antwort ist ja. Speziell kann sich das Leerfeld also auch unsichtbar im Inneren des 5x5x5-Würfels befinden.

Auf diese Weise können Sie sich das Leerfeld vorgeben und erhalten viele verschiedene Aufgaben.

Idee:  Torsten Sillke
Erscheinungsjahr: 1993

Mehr Infos:

16.10.22

Bastille

Am 14. Juli 1879 erfolgte der Sturm auf die Bastille, dabei wurden alle sieben dort befindlichen Gefangenen befreit. Daraus kann man das Holzpuzzle „Bastille“ machen: Einen Holzwürfel mit gleichgroßen quadratischen Öffnungen an den Seitenflächen als Bastille, darin sieben identische Holzsteine als Gefangene. Ein sehr schönes und schwieriges Puzzle. 

Die Holzsteine sind jeweils ein Viertel einer Kreisscheibe mit Radius 1 und Höhe 1. Die innere Seitenlänge des Würfels ist etwas größer als 2. Stellen wir uns für einen Moment die Steine als Würfel mit Seitenlänge 1 vor, dann ist Folgendes klar: Es passen genau acht solche Würfel in die Kiste. Wenn wir nur sieben hineinpacken, bleibt ein Elementarwürfel frei und wir können die sieben Würfel herumschieben, wobei sie Positionen der Würfel allerdings immer wieder dieselben sind. Jetzt ersetzen wir die würfelförmigen Steine durch die tatsächlichen Spielsteine. Diese sind kleiner, da nun jeweils eine Kante abgerundet ist. Aber scheinbar lassen sich auch die abgerundeten Steine nur so bewegen wie die Elementarwürfel.

Schwierigkeit: Sehr schwer. Identische Steine, eine symmetrische Kiste und das Puzzle erscheint unlösbar. Es ist eines von mehreren Puzzles von Volker Latussek, bei denen mehrere identische Bausteine in eine Würfelförmige Kiste mit reduzierter Öffnung gepackt werden sollen, z.B. Casino, oder den Tower of London.

 

Design:  Volker Latussek
Hersteller:  Rombol, Pelikan u.a.
Erscheinungsjahr: ca. 2017

Google: Latussek Bastille
Shopping: Lieferbar, Preis ca. 25€ (Rombol)

7.3.21

Casino

Sechs identische Casino-Chips sollen in einer würfelförmigen Kiste untergebracht werden. Kiste und Chips sind aus Holz, und die Kiste ist nicht völlig geöffnet: auf zwei gegenüberliegenden Seiten ist die Öffnung zu einem kleinen Teil abgedeckt. 

Die Chips sind (anders als im richtigen Casino) ziemlich dick und tragen auf einer Seite den Schriftzug „Casino“. In der abgebildeten Version von Rombol hat die Kiste ein Innenmaß von (reichlich) 6cm x 6cm x 6cm und die Chips sind jeweils 2 cm dick und haben einen Durchmesser von 4cm. Versucht man einfach so, die Chips in die Kiste zu packen, klappt das zwar für fünf Chips, aber der sechste Chip will nicht mehr hineinpassen.

Das Puzzle gewann auf der Internationalen Puzzle Party IPP38 in San Diego im Jahr 2018 den Preis Puzzle oft the year. Es ist eines von mehreren Puzzles von Volker Latussek, bei denen mehrere identische Bausteine in eine Würfelförmige Kiste mit reduzierter Öffnung gepackt werden sollen. 

Wenn wir uns das Puzzle näher ansehen wollen, dann ergeben sich relativ schnell Lösungshinweise. Zuerst überprüfen wir aber, dass die Kiste wirklich würfelförmig ist und alle Chips gleich groß und gleich dick sind. Damit gibt es keine versteckten Informationen, die nützlich sein könnten.

 

 

Design:  Volker Latussek
Hersteller:  Rombol, Pelikan u.a.
Erscheinungsjahr: 2018

Google: Latussek Casino
Shopping: Lieferbar, Preis ca. 20€ (Rombol)

Bitten Biscuits / Die angebissene Symmetrie

Was macht man mit drei Keksen, in die bereits jemand hineingebissen hat? In der Welt der Geduldspiele isst man sie nicht auf, sondern versuc...