Wörtlich übersetzt heißt Rektifizierung "Verrechreckigung": Die Aufgabe besteht darin, ein Rechteck mit lauter identischen Steinen zu füllen, und als Steine sollen Polyominos benutzt werden. Wir müssen unsere Aufgabenstellung allerdings noch etwas genauer formulieren:
Gegeben sei ein bestimmtes Polyomino. (Wir werden uns weiter unten die Pentominos genauer ansehen.) Rechtecke welcher Größe lassen sich mit der passenden Anzahl von Exemplaren dieses Polyominos vollständig füllen? Falls es überhaupt ein solches Rechteck gibt, heißt das Polyomino rektifizierbar. In diesem Fall wollen wir uns natürlich für "alle" Rechtecke interessieren, die sich damit füllen lassen. Und auch diese Fragestellung müssen wir noch genauer spezifizieren. Bekannt wurde diese Fragestellung durch Martin Gardner [1], im englischen Original ab 1965.
Für ein gegebenes Polyomino kann die Fragestellung nach der Rektifizierbarkeit leicht zu beantworten sein, für andere ist es schwierig. Beispielsweise ist es einfach zu sehen, dass man Rechteck genau dann mit I-Pentominos füllen kann, wenn eine Seitenlänge ein Vielfaches von fünf ist: Diese Bedingung ist notwendig, weil die Gesamtfläche durch fünf teilbar sein muss und fünf eine Primzahl ist. Andererseits ist diese Bedingung auch hinreichend, weil sich das Rechteck mit gleich orientierten I-Pentominos füllen lässt, die alle auf der durch fünf teilbaren Seite „liegen“. Wir interessieren uns dann oft für das kleinste Rechteck (oder die kleinsten Rechtecke, falls es mehrere mit verschiedenen Seitenverhältnissen gibt), welches gefüllt werden kann. Beim I-Pentomino ist dies trivialerweise das 1x5-Rechteck und wir benötigen nur einen Stein. In vielen Fällen reichen zwei (beim L- und P-Pentomino, jeweils für das 2x5-Rechteck) oder maximal vier Steine (beim T-Tetromino für das 4x4-Quadrat).
Hier ein Negativ-Beispiel: Mit mehreren X-Pentominos lässt sich niemals ein Rechteck füllen, da die Elementarquadrate in den Ecken des großen Rechtecks niemals durch ein X-Pentomino überdeckt werden können. Das X-Pentomino ist damit nicht rektifizierbar.
Doch zurück zu den rektifizierbaren Polyominos. Wenn wir für ein solches Polyomino ein füllbares Rechteck gefunden haben, dann können wir mehrere solche Rechtecke zu einem größeren zusammenfügen wie oben für das I-Pentomino erklärt. Umgekehrt kann man derartige größere Rechtecke in kleinere zerschneiden. Interessant ist der Fall der kleinsten solchen Rechtecke, die sich nicht weiter zerschneiden lassen. Solche Rechtecke heißen prime Rechtecke. Dieser Begriff lehnt sich an den Begriff der Primzahl an, die ebenfalls nicht weiter in ein Produkt kleinerer natürlicher Zahlen zerlegt werden können.
Betrachten wir also die etwas komplizierteren Fälle von rektifizierbaren Polyominos mit etwas komplizierteren primen Rechtecken. Wenn wir eine solche nichttriviale Rektifizierung gefunden haben, dann lässt sich daraus sofort ein Puzzle erzeugen, bei dem die entsprechend vielen identischen Bausteine in den vorgegebenen rechteckigen Rahmen eingeordnet werden sollen.
Für die einzelnen Tetrominos und Pentominos sieht die Situation folgendermaßen aus:
Rektifizierung der Tetrominos
Auf einfache Weise rektifizierbar (mit 1, 2 oder 4 Steinen) sind die folgenden Tetrominos: I, L O und T.
Nicht rektifizierbar ist das Z: Sie versuchen, die linke obere Ecke zu überdecken. Dazu gibt es (bis auf Spiegelung an der Hauptdiagonale) nur eine Möglichkeit. Danach kümmern Sie sich um den oberen Rand (von links nach rechts) und den linken Rand (von oben nach unten). Jeweils gibt es nur eine Möglichkeit, den nächsten Stein anzufügen. Die Eckfelder rechts oben und links unten können Sie so niemals überdecken. Damit ist das Z-Tetromino nicht rektifizierbar.
Rektifizierung der Pentominos
Auf einfache Weise rektifizierbar (mit 1, 2 oder 4 Steinen) sind die Pentominos I, L und P. Dagegen sind die folgenden Pentominos nicht rektifizierbar: F, N, T, U, V, W, X und Z. Die Begründungen sind ähnlich wie beim Z-Tetromino.
Es bleibt das Y-Pentomino. Es wurde schon bei den allgemeinen Packproblemen mit dem Y-Pentomino verraten, dass sich ein 5x10-Quadrat aus 10 Y-Pentominos legen lässt. Dies ist nicht das einzige prime Rechteck. Hier ist die vollständige Liste der primen Rechtecke, zusammengestellt von Michael Reid [2]. Sie ist zeilenweise geordnet nach der Länge der kürzeren Seite:
- 5 × 10
- 9 × 20, 9 × 30, 9 × 45, 9 × 55
- 10 × 14, 10 × 16, 10 × 23, 10 × 27
- 11 × 20, 11 × 30, 11 × 35, 11 × 45
- 12 × 50, 12 × 55, 12 × 60, 12 × 65, 12 × 70, 12 × 75, 12 × 80, 12 × 85, 12 × 90, 12 × 95
- 13 × 20, 13 × 30, 13 × 35, 13 × 45
- 14 × 15
- 15 × 15, 15 × 16, 15 × 17, 15 × 19, 15 × 21, 15 × 22, 15 × 23
- 17 × 20, 17 × 25
- 18 × 25, 18 × 35
- 22 × 25
Das klingt nach einer großen Menge von Geduldspielen. Speziell beschäftigen wollen wir uns mit den Größen 15x15 und 25x25. Auch nicht-prime Rechtecke (wie 25x25) können interessant sein, deshalb soll auch auf die Aufstellung "aller" möglichen Rechtecke zusammen mit vielen weiteren Aufgaben von Torsten Sillke [3] hingewiesen werden.
Übrigens gibt es zum zweidimensionalen Rektifizierungsproblem auch eine dreidimensionale Variante: Ein Würfel oder allgemeiner, ein Quader soll mit identischen Bausteinen gefüllt werden. Die Bausteine werden hier aus Elementarwürfeln zusammengesetzt. Dafür wird es noch einen eigenen Post geben.
Auch mit größeren Polyominos bleibt die Rektifizierung spannend. Es gibt immer einige Steine, für die man relativ große Rechtecke für die Rektifizierung benötigt. Eine schöne Zusammenstellung der aufregenden Fälle findet man bei Andrew Clarke [4].
