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.
|
Keine Kommentare:
Kommentar veröffentlichen