Unlösbar: Ein gezacktes Rechteck mit Pentominos überdecken

Kategorie: Pentominos in rechteckige und andere Rahmen packen

Der hier abgebildete Ausschnitt aus einem verdrehten Quadratgitter soll gezacktes Rechteck heißen. 

Es besteht aus 60 Elementarquadraten und man könnte sich deshalb vornehmen, es mit den zwölf Pentominos zu füllen. Doch das scheint nicht zu klappen. Kann man vielleicht sogar beweisen, dass eine Lösung unmöglich ist? Bei ähnlich gelagerten unlösbaren Aufgaben (für Quadrate der Größen 6x6, 8x8 oder 10x10) half eine schachbrettartige Färbung (mit zwei oder mehr Farben) weiter. Doch dieser Trick hilft hier nicht, wir müssen nach einer anderen Lösung suchen.

Bei vielen Überdeckungsaufgaben ist es eine gute Idee, am Rand zu beginnen. Und wenn Sie versuchen, zunächst die ganz außen liegenden Elementarquadrate des gezackten Rechtecks zu füllen, dann klapp schon dass nicht. Können Sie das beweisen? Die Details gibt es in  dem untenstehenden Lösungshinweis.

PolySolver-Hinweis: Statt Nachdenken können wir mittels Computer auch alle Möglichkeiten durchprobieren lassen. Software wie der PolySolver sagt dann: Keine Lösung gefunden. Auch das zählt als Unmöglichkeitsbeweis.

Lösungshinweis: Insgesamt müssen 22 solche außen liegende Elementarquadrate bedeckt werden. Jetzt schauen wir, wie viele davon jedes einzelne Pentomino maximal überdecken kann. Diese Anzahlen sind: F-3, I-1, L-1, N-2, P-2, T-1, U-1, V-1, W-3, X-3, Y-2 und Z-1. Insgesamt sind dies nur 21 statt der nötigen 22 Randfelder. Damit ist die Aufgabe unlösbar.

 

Historisches:  Pentominos wurden durch S. Golomb in den 1950er Jahren populär, die Aufgabe ist auch schon lange bekannt. Der Beweis oben stammt von R.M. Robinson.