Polimino do kwadratu, czyli układanki sformatowane

Polimino to ogólne określenie wielokąta złożonego z jednakowych małych kwadratów (kratek). W zależności od tego, ile kratek tworzy wielokąt, w nazwie zmienia się cząstka „poli-”. Na rys. 1 figurują wszystkie różne polimina z „poli-” obejmującym zakres od 1 do 5: jedno monomino, jedno domino, dwa trimina, pięć tetromin oraz 12 pentomin z ich jednoliterowymi nazwami. Dalej jest 35 heksomin, 108 heptomin, 369 oktomin, a od nonomin zaczynają się rodziny przekraczające tysiąc „osobników”. Tyle jest przy założeniu, że są to tzw. polimina swobodne, czyli obroty i odbicia lustrzane ich nie zmieniają. Bez tego założenia, uważanego za standardowe, liczba polimin jest znacznie większa. Polimino i każde konkretne „-mino”, to także nazwa kompletu określonych polimin.

Kilka zagadnień geometrycznych i kombinatorycznych związanych z poliminem gościło już w tej rubryce. Tym razem będzie o kwadratach układanych z poliminowych figur (figury te jako elementy układanki zwane są także kamieniami) lub na polimina dzielonych.

Temat jest bliski matematyce rekreacyjnej także ze względu na to, że pokratkowany kwadrat jest standardową figurą w przeważającej większości diagramowych zadań logicznych, a wśród nich dużą grupę stanowią te, w których diagram jest podzielony na początku lub dzielony w trakcie rozwiązywania na polimina. Spektakularnym przykładem takiego zadania, także ze względu na „-mino” w nazwie, jest łamigłówka fillomino, polegająca na dzieleniu diagramu na polimina. Kluczem do rozwiązania są w niej dwie informacje:

– liczba w kratce oznacza wielkość (liczbę kratek) polimina obejmującego tę kratkę,

– polimina tej samej wielkości nie mogą stykać się bokami (rogami mogą).

Praktycznie rozwiązywanie polega na równoczesnym oznaczaniu granic i wypełnianiu pól liczbami tak, aby każda grupa sąsiadujących pól z jednakową liczbą (tworzących jeden wielokąt) składała się dokładnie z tylu pól, jaka jest wartość liczby w każdym jej polu.

Trzy łatwe fillomina najmniejszych rozmiarów znajdują się na rys. 2. Te 2×2 i 3×3 są właściwie trywialne, ale rozwiązywanie 4×4 już tak proste nie jest.

Fillomino debiutowało w Japonii w roku 1994, choć właściwie było „plagiatem” holenderskiej łamigłówki z lat 80. znanej pod różnymi nazwami, najczęściej jako vakken vullen (wypełnianie przegródek), która różni się od fillomina brakiem drugiego warunku, ponieważ wszystkie polimina są różnej wielkości. Przykładowa łamigłówka (rys. 3) jest najmniejszą nietrywialną.

Ile może być różnych rozwiązań obu rodzajów zadań – holenderskiego pierwowzoru i japońskiego bliźniaka – dla diagramów różnego formatu? To pytanie jest bliskie następującemu: na ile różnych sposobów (z dokładnością do obrotów i odbić lustrzanych) można podzielić na polimina kwadrat n×n? Rozwiązanie tego problemu obliczeniowego jest na razie znane tylko dla formatów takich, jak na rys. 2 i 3, czyli n≤4. Dla n=2 podziałów jest 5, przy uwzględnieniu również braku podziału (rys. 4), ale już dla n=3 sięga 216, a dla n=4 liczba podziałów wynosi 212 987. Dalej komputery na razie się poddały; szacunkowy wynik dla n=5 to około 25 mld. Dla dwu przykładowych rodzajów zadań podane liczby podziałów są oczywiście znacznie mniejsze (stąd „bliskie” w zdaniu powyżej) ze względu na dodatkowe warunki: brak sąsiadowania (a) – lub w ogóle brak polimin takiej samej wielkości – (b). W przypadku (a) zamiast czterowyrazowego początku ciągu 1, 5, 216, 212 987, … jest 1, 2, 77, 15 192, … , zaś w przypadku (b) – 1, 2, 35, 6563, … .

Przypadek (b) stanowi – w analogii do niektórych sportów – jedną z konkurencji w dyscyplinie „układanie kwadratów z polimina”. Konkurencję tę można określić symbolem W_rK_d, czyli Wielkości różne, Kształty dowolne. Natomiast przypadek (a) to konkurencja W_dK_d (warunek dotyczący braku sąsiedztwa pomijamy). Ponieważ możliwy jest jeszcze indeks dolny j (jednakowe), więc w sumie teoretycznych konkurencji mamy dziewięć. Wszystkie uwzględnione są na schemacie z przykładami dla kwadratu 4×4 (rys. 5).

Skrót K_j, czyli jednakowy kształt, oznacza zarówno figury przystające, jak i podobne, zaś różna wielkość (W_r) wyklucza obecność dwóch figur takiej samej wielkości. Zatem połączenie W_rK_j powinno dać kwadrat ułożony z dwóch figur podobnych, jednak nie jest to możliwe, dlatego odpowiedniej konkurencji dla kwadratu 4×4 (i dla każdego innego) brak. Najbliższy ideału jest kwadrat bez rogu (rys. 6).

Nietrudno zauważyć, że konkurencja W_dK_d obejmuje wszystkie pozostałe, podobnie jak styl dowolny w pływaniu obejmuje wszystkie inne, choć w praktyce niemal zawsze oznacza kraul, jako najszybszy. Matematyków najbardziej interesują dwie „specjalistyczne” konkurencje z W_j: W_jK_r, czyli układanie kwadratów z różnych polimin, należących do tej samej rodziny oraz W_jK_j, a więc tworzenie kwadratów z jednakowych polimin. Zajmiemy się tą pierwszą konkurencją.

Jeśli pominąć polimina kwadratowe (1×1, 2×2), bo w tym przypadku kwadrat po prostu jest, a nie jest układany, to konkurencja W_jK_r teoretycznie zaczyna się od tetromina, jednak ten obiecujący start okazuje się falstartem. Choć cztery tetromina to 16 kratek, a więc powierzchnia kwadratu 4×4, to jednak z żadnego kwartetu różnych tetromin kwadratu ułożyć się nie da. Aby powstał kwadrat, przynajmniej jedna figura musi się powtórzyć, a wszystkich kwadratów z powtórkami jest 22. Dwa z nich to przykłady konkurencji W_jK_d i W_jK_j na rys. 5; 20 pozostałych jest na rys. 7 – każdy z pięciu kwadratów w pierwszym rzędzie tworzą cztery jednakowe figury, w drugim – dwie pary jednakowych, w trzecim i czwartym występuje jedna powtórka.

Głównym sprawcą tetrominowego falstartu jest figura w kształcie przysadzistego „T” – jedyna z szachownicowym wzorem złożonym z jednego pola jasnego i trzech ciemnych (lub odwrotnie), więc jeśli pojawia się w kwadracie, to zawsze dwukrotnie, jako „negatyw” i „pozytyw” – aby zachowana była równa liczba jasnych i ciemnych pól szachownicy 4×4. A skoro powtórka T-tetromino jest nieunikniona, więc pozostaje tylko jeden zestaw czterech różnych tetromin do ułożenia z nich kwadratu 4×4 – a to, niestety, nie jest możliwe.

Falstart tetromina nadrabia z nawiązką pentomino. Najmniejszy i jedyny, jeśli chodzi o wielkość, pentominowy kwadrat ma wymiary 5×5. Większy (10×10) być nie może, bo obejmowałby 100 kratek, czyli 20 różnych pentomin, podczas gdy jest ich tylko 12. Ze wzoru na kombinacje bez powtórzeń wynika, że 5 kamieni można wybrać z kompletu 12 pentomin na 792 sposoby. 49 z nich umożliwia utworzenie kwadratu 5×5. Różnych kwadratów (z dokładnością do obrotów i odbić) jest jednak 107, bo część zestawów jest bardziej owocna, a zwłaszcza zestaw złożony z kamieni I, L, P, W, Y – daje on aż osiem kwadratów (rys. 8). Ciekawe, że tylko jeden z nich, potraktowany jak mapa złożona z pięciu obszarów, wymaga użycia nie trzech, jak pozostałe, lecz czterech barw do takiego pokolorowania, aby każde dwa graniczące bokami obszary różniły się barwą. Ciekawe jest też to, że z kompletu można wybrać 10 takich kamieni, z których uda się ułożyć dwa kwadraty 5×5. Takiego wyboru dotyczy jedno z zadań konkursowych.

Od heksomina zaczyna się możliwość układania kwadratów różnej wielkości. Dla heksomina są to kwadraty 6×6 i 12×12. 18×18 obejmuje już większą liczbę kamieni (54) niż jest w komplecie (35). Liczby różnych kwadratów możliwych do ułożenia z tego i większych polimin nie są znane, a główny problem sprowadza się do utworzenia największego – przynajmniej jednego. Podzielenie kwadratu 12×12 na 24 różne heksomina to zadanie benedyktyńskie, ale przy niewielkiej wprawie i sporej wytrwałości możliwe do wykonania na piechotę – efekt na rys. 9. W przypadku większych polimin i kwadratów trudno obyć się bez komputerowego wsparcia. Włoscy programiści dotarli do kwadratu 210×210 złożonego z 4410 różnych dekomin (wszystkich 10-kratkowych figur jest 4655), ale największy spośród największych, jaki może zmieścić się na tej stronie z zachowaniem odpowiedniej rozdzielczości, ma 100 razy mniej kratek – obejmuje 63 heptomina (rys. 10 – jego kolorystyka, podobnie jak tego z rys. 9 oraz ostatniego z rys. 8, może być przykładem twierdzenia o czterech barwach).

Odrębną konkurencją jest układanie kwadratów z pełnego kompletu n-omina uzupełnionego kamieniem odpowiedniej innej wielkości, ale najmniejszej możliwej. Ściśle rzecz biorąc, powinien to być kamień x-omina, gdzie x<n. Takie uzupełnienie jest jednak możliwe tylko w przypadku pentomina, którego 12 kamieni zawiera 60 kratek. Wystarczy więc dodać do niego jedno tetromino, aby liczba kratek utworzyła kwadrat (64). Czy dysponując 13 kamieniami – kompletem pentomina i dowolnym z 5 kamieni tetromina – zawsze uda się utworzyć kwadrat? Odpowiedź twierdząca jest możliwa tylko dla kwadratowego tetromina 2×2 – tak sądzono początkowo za sprawą popularnej od ponad 100 lat łamigłówki Henry’ego Dudeneya (zdjęcie), pojawiającej się czasem jako gotowa układanka w sklepach z zabawkami w postaci szachownicowej. Dopiero po skorzystaniu z komputerów okazało się, że takim „suplementem” może być dowolne tetromino i to na wiele sposobów, różniących się umiejscowieniem tetromina w kwadracie. Znaleziono nawet kilka serii pięciu tzw. kwadratów kompaktowych. Każdy kwadrat w danej serii składa się z dwóch części – dużej, stałej, jeśli chodzi o zestaw i rozmieszczenie 10 pentomin, oraz małej, częściowo zmiennej. Część małą tworzą dwa pozostałe pentomina i jedno wymienne tetromino, dowolne z pięciu – rozmieszczane w różny sposób. Stąd pięć kwadratów w serii, której duża część stała oraz pięć zmiennych małych mogą wyglądać na przykład tak, jak na rys. 11.

ZADANIA

1. Do kratek diagramu podzielonego na polimina (rys. 12) należy wpisać cyfry. W każdym poliminie, obejmującym n kratek, powinno znaleźć się n kolejnych cyfr – od 1 do n. Dwie takie same cyfry nie mogą być umieszczone w sąsiednich kratkach – stykających się bokiem lub tylko rogiem. Jedna cyfra znajduje się już na swoim miejscu (w przykładzie nad diagramem ujawnione są dwie cyfry). Jako rozwiązanie końcowe wystarczy podać siedem cyfr na przekątnej – od lewego dolnego rogu do prawego górnego.

2. Z 10 kamieni pentomina (rys. 13) należy ułożyć dwa kwadraty 5×5. Kamienie można obracać i odwracać. Zacząć zapewne najlepiej od pentomin najbardziej „kłopotliwych”, czyli X lub F. W rozwiązaniu wystarczy podać dwie piątki pentomin, tworzących każdy kwadrat.

3. Kwadrat 6×6 podzielono na osiem polimin różnej wielkości – od monomina do oktomina. Do każdej kratki każdego polimina wpisano liczbę równą liczbie tworzących go kratek (np. w każdej kratce heksomina znalazła się szóstka). Następnie przy brzegu diagramu zapisano sumy liczb w trzech wierszach i dwóch kolumnach, a podział diagramu i wszystkie znajdujące się w nim liczby usunięto (rys. 14). Na podstawie pozostawionych przy brzegu sum należy odtworzyć podział diagramu. Jako rozwiązanie końcowe wystarczy podać sześć cyfr w polach na przekątnej diagramu, łączącej lewy dolny róg z prawym górnym.

Rozwiązania prosimy nadsyłać do 31 grudnia br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 12/21. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką P.J.E. Peeblesa Stulecie kosmologii. Jak zrozumieliśmy Wszechświat ufundowaną przez wydawnictwo Prószyński Media. Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:

Zapoznałam/em się z regulaminem konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji konkursu.

Regulamin konkursu jest dostępny na stronie www.swiatnauki.pl

***

Rozwiązania zadań numeru październikowego

1. Liczba statków – 19 (rys. 15).

2. Pozycje jednomasztowców – f4, h2, j2, j5 (rys. 16).

3. Pozycje jednomasztowców – a4, c5, j4, j10 (rys. 17).

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Michio Kaku Boskie równanie. W poszukiwaniu teorii wszystkiego, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Bartłomiej Goldman z Nadarzyna, Paweł Hołownia z Ożarowa Mazowieckiego, Janusz Mucha ze Skawiny, Andrzej Nużyński z Kolonii Warszawskiej, Marta Skowrońska z Warszawy.