Dzielenie na kamienie, czyli o rozszyfrowywaniu układu

Słowo „domino” ma w matematyce rekreacyjnej dwa znaczenia. Pierwsze oznacza prostokąt 2×1 utworzony z dwóch jednakowych kwadratów. Drugie jest określeniem zestawu złożonego z p= (k+1) (k+2)/2 takich prostokątów (kamieni) z umieszczonymi na tworzących je kwadratach cyframi, obejmującymi zakres od 0 do k. Zestaw tworzą wszystkie różne pary – od 0–0 do k-k. Dla k=1 kamienie są trzy (0–0, 0–1, 1–1), dla k=2 – sześć (0–0, 0–1, 0–2, 1–1, 1–2, 2–2) itd. Na rys. 1 oznaczone są większe zestawy – od k=3 do k=6. Ostatni, czyli cały rys. 1, obejmuje komplet 28 kamieni do tradycyjnej gry w domino; różnica jest tylko formalna – cyfry na kamieniach oznaczane są oczkami, jak na kostce do gry.

Gdy w XIX wieku kołatanie kamieniami domina przybrało w Europie rozmiary epidemii, zainteresowali się nim matematycy, w czego następstwie pojawiły się dominowe łamigłówki. Były to niemal wyłącznie zadania polegające na budowaniu układów o określonych własnościach, np. figur magicznych (jednakowe sumy w określonych rzędach), działań arytmetycznych albo tzw. kwadryli lub kwartyli (układy, w których połówki kamieni z jednakową cyfrą tworzą czwórki 2×2 – w kwadrylach lub 1×4 – w kwartylach). Takie łamigłówki stanowią jednak w gruncie rzeczy problemy z wieloma rozwiązaniami. Ich przeciwieństwem są konkretne zadania z jednym rozwiązaniem, które można by nazwać rekonstrukcyjnymi. Chodzi w nich o pełne odtworzenie jakiegoś układu, ujawnionego tylko częściowo. Do najciekawszych łamigłówek rekonstrukcyjnych należy deduktomino, które mimo że formalnie proste, wiąże się z trudnymi zagadnieniami matematycznymi.

Zadanie łatwo utworzyć samemu. Wystarczy z kompletu kamieni (dla danego k) ułożyć prostokąt o wymiarach (k+1)×(k+2), a następnie oznaczyć na kartce rozmieszczenie cyfr w tym układzie bez rysowania granic między kamieniami i zadanie gotowe. Nietrudno się domyślić, że zabawa polega na podzieleniu cyfrowej mozaiki na kamienie, a więc na pary cyfr. Podstawowym kluczem do rozwiązania jest oczywiście kompletność układu, czyli fakt, że występują w nim wszystkie różne pary, każda dokładnie raz.

Na rys. 2 znajduje się deduktomino 5×6 utworzone z umieszczonych z lewej strony 15 kamieni kompletu czwórkowego (k=4). Rozwiązywanie zaczyna się zwykle od znalezienia pewniaków, czyli par cyfr sąsiadujących ze sobą tylko w jednym miejscu. Wygodnie jest szukać takich par systematycznie, korzystając z tabelki znajdującej się na rys. 2 z prawej strony. Przecięcia wierszy i kolumn odpowiadają w niej wszystkim kamieniom, czyli wszystkim różnym sąsiedztwom par cyfr. W prostokącie (k+1)×(k+2) wszystkich sąsiedztw jest 2k²+4k+1, czyli 49 dla k=4. Oznaczając każde sąsiedztwo kreską w odpowiedniej rubryce, uzyskamy informację o liczbie sąsiadujących par każdego rodzaju. Z wypełnionej tabeli na rys. 1 wynika, że tylko raz występują pary 1–1 i 4–4. Oznaczenie tych kamieni na diagramie zaczyna więc pierwszy etap rozwiązywania, którego efekt znajduje się na rys. 3a. Nietrudno zauważyć, że ujawnianie w pierwszym etapie kolejnych kamieni zaczęło się od pary 0–0 – jej połączenie było konieczne, bo w przeciwnym wypadku w układzie pojawiłoby się dwukrotnie 0–2. Wydzielenie kilku dalszych kamieni wynika wyłącznie z geometrii układu, po czym należy rozgraniczyć sąsiadujące zera oraz 1 i 2, bo kamienie z tymi parami są już ujawnione. Jeśli teraz drugi etap zacząć od zakreślenia jedynej możliwej pozycji 1–4, to dalej wszystko będzie szło jak po sznurku, aż do finału (rys. 3b).

Rozszyfrowanie deduktomina nie zawsze jest takie proste. Kłopoty mogą wystąpić już na początku, gdy zabraknie pewniaków. Tak jest w przypadku drugiego zadania dla k=4 przedstawionego na rys. 4. Z tabelki sąsiedztw obok diagramu wynika, że żadna para nie sąsiaduje tylko raz, ale kilka par (0–4, 2–2, 3–3, 4–4) pojawia się dokładnie dwukrotnie. Warto przyjrzeć się rozmieszczeniu każdej z tych par, bo być może którąś z nich uda się rozdzielić albo jakaś granica będzie wynikała z ich wzajemnego położenia. Taki przypadek dotyczy tworzących czwórkowy tercet par 4–4 przy prawym górnym rogu – efektem jest granica A. Dalsze rozwiązywanie stanowi test spostrzegawczości i logicznego myślenia – polega na kolejnym oznaczaniu krótkich granic z wykorzystaniem wniosków wynikających z wzajemnego położenia niektórych kamieni: gdyby nie było granicy B, to pojawiłyby się dwa kamienie 1–3 (taki sam wniosek dotyczy granicy C); brak granicy D owocuje drugim 0–2, a brak E lub F rodzi drugi dublet 1–1 u góry diagramu; z kolei nad oznaczoną granicą F musi leżeć poziomo lub pionowo kamień 1–2, co uzasadnia rozdzielenie jedynki i dwójki granicą G. W drugim etapie (rys. 5a) można już oznaczyć kamienie 2–2 i 1–1, a następnie narysować trzy granice H (wyodrębnienie w górnej części diagramu dwóch obszarów, które powinny być parzyste, czyli zawierać parzystą liczbę cyfr), a także granicę I (rozdzielenie dwójek, bo kamień 2–2 jest już ujawniony), a potem J (gdyby jej zabrakło, pojawiłyby się dwa kamienie 2–3). Po wydzieleniu w środku kamienia 4–3 – ze względu na konieczną parzystość dwóch obszarów u dołu diagramu – oraz rozdzieleniu par trójki i czwórki przy dolnych rogach dalszy podział jest niemal automatyczny (rys. 5b).

Z finałem wiąże się jednak pewien mankament: zadanie ma więcej niż jedno rozwiązanie, ponieważ obszar przy prawym górnym rogu można podzielić na kamienie 1–2, 2–4 i 4– 4 na trzy sposoby. W związku z tym wypada skorygować podaną wyżej informację o łatwym układaniu deduktomina. Jeśli zadanie ma mieć jedno rozwiązanie, nie jest to takie proste, bowiem ułożony na chybił-trafił prostokąt ma na ogół przynajmniej kilka rozwiązań. Trzeba go więc poprawić, a to nie zawsze jest takie łatwe, jak w przypadku układu z rys. 4, gdzie wystarczy zamienić miejscami dwójkę przy prawym brzegu i znajdującą się pod nią jedynkę, aby układ okazał się jednoznaczny.

Klasyczne deduktomino jest większym prostokątem – 7×8, ułożonym z pełnego kompletu do gry w domino, czyli z 28 kamieni (k=6). Określenie „klasyczne” jest uzasadnione, ponieważ łamigłówka debiutowała pod koniec XIX wieku w prasie niemieckiej jako dominosa, a nawet została opatentowana w roku 1894. Autorem pomysłu i patentu był niejaki Oskar Adler, dyrektor jednego z berlińskich banków. Nie zmienia to faktu, że deduktomino wypłynęło na szersze, światowe wody znacznie później – pośrednio dzięki Lechowi Pijanowskiemu, który przesłał kilka zadań do Martina Gardnera, zaś ten opublikował je na łamach Scientific American w grudniu 1969 roku.

Na rys. 6 znajdują się dwa przykłady klasycznego deduktomina. Pierwsze jest proste – zawiera kilka pewniaków (m.in. dubletów), które łatwo znaleźć; można też bez trudu oznaczyć sporo granic, więc nawet nie trzeba korzystać z tabelki sąsiedztw. Natomiast drugi przykład to twardy orzech. Z umieszczonej obok niego tabelki wynika, że pewniaków brak, ale siedem kamieni (0–0, 0–2, 1–1, 3–4, 5–5, 5–6, 6–6) pretenduje do zajęcia tylko dwóch pozycji. Od nich warto więc zacząć zmagania, bo położenie niektórych może zaowocować oznaczeniem paru granic.

Ogólnie rzecz biorąc, rozwiązywanie deduktomina jest ustalaniem sposobu pokrycia dużego prostokąta m×n małymi prostokątami 1×2. Pytanie o liczbę wszystkich tych sposobów jest zagadnieniem ściśle matematycznym, a praktycznie wchodzi w zakres mechaniki statystycznej, gdzie nosi nazwę problemu dimerów kratowych (dla krat kwadratowych). Wzór na tę liczbę jest skomplikowany i – co może się wydać dziwne – zawiera funkcję trygonometryczną (cosinus) i liczbę p. Całe zagadnienie jest zresztą zbyt skomplikowane, aby je tu przedstawiać, ale można wspomnieć o kilku związanych z nim prostych przypadkach.

Łatwo sprawdzić, że liczba sposobów pokrycia dominem prostokątów 2×n (dla n=1, 2, 3, …) tworzy ciąg Fibonacciego: 1, 2, 3, 5, 8, 13, 21, 34, …; dla n=5 wszystkie sposoby są przedstawione na rys. 7. Jeśli prostokąty mają wymiary 3×n, to pokrycia są możliwe tylko dla n parzystych, więc nieparzyste wyrazy odpowiedniego ciągu są zerami: 0, 3, 0, 11, 0, 41, 0, 153 …; pokrycia dla n=4 – na rys. 8. Prostokąty 4×n dzielą się na domina na liczbę sposobów wyrażoną ciągiem: 1, 5, 11, 36, 95, 281, 781, 2245 … Kontynuując tę wyliczankę, dotrzemy do m=7, czyli długości krótszego boku deduktomina, a pięć pierwszych wyrazów ciągu liczb sposobów pokrycia dominem prostokątów 7×n możemy spisać z podanych wyżej ciągów; do deduktominowego ósmego wyrazu (7×8) ciąg wygląda tak: 0, 21, 0, 781, 0, 31 529, 0, 1 292 697 …

Niektóre pary pokryć, jak np. na rys. 7 i 8, są względem siebie symetryczne, czyli jedno z nich można zmienić w drugie, obracając lub odbijając w lustrze. W powyższych ciągach takie pokrycia uważamy za różne. Gdyby przyjąć, że są jednakowe, liczby w ciągach by oczywiście zmalały, ale ustalenie ich dokładnych wartości w szerszym zakresie jest problemem bardzo trudnym obliczeniowo, więc znamy tylko ciąg całkowicie różnych sposobów pokrycia dominem prostokąta 2×n: 1, 1, 2, 4, 5, 9, 12, 21 … Z szacunkowych obliczeń wynika jednak, że rozwiązanie każdego deduktomina, czyli podział prostokąta 7×8 na prostokąty 1×2, jest przynajmniej jednym z blisko pół miliona całkowicie różnych możliwych podziałów.

Zadania

1. Pierwsza „handlowa” wersja dominosy, opatentowana w 1894 roku i po raz pierwszy opisana dokładnie w broszurze wydanej w roku 1912, zawierała więcej kamieni niż tradycyjne domino. Autor pomysłu, Oskar Adler, nadał jej w ten sposób cechy produktu w pewnym stopniu oryginalnego, bo patent z wykorzystaniem powszechnie znanego domina nie zostałby zatwierdzony. Dominosa bazowała na dominie siódemkowym, liczącym 36 kamieni, od 0–0 do 7–7. Pierwsze publikowane łamigłówki były więc prostokątami 8×9 – nierzadko dość twardymi orzechami, czego potwierdzeniem jest jedno z zadań sprzed 120 lat (rys. 9). W rozwiązaniu wystarczy podać, ile kamieni leży w układzie poziomo (dłuższy bok kamienia jest równoległy do dłuższego boku diagramu).

2. Czy w deduktominie oprócz braku granic między kamieniami można usunąć także niektóre cyfry, a mimo to rozwiązanie będzie jednoznaczne? Okazuje się, że tak, a zadania z takim dodatkowym ubytkiem pojawiły się na 21 Łamigłówkowych Mistrzostwach Świata w roku 2012 w Kraljevicy (Chorwacja). Jedno z nich znajduje się na rys. 10. W rozwiązaniu wystarczy podać, ile kamieni leży pionowo (dłuższy bok kamienia równoległy jest do krótszego boku diagramu).

3. Swego rodzaju „odwrotnością” deduktomina jest łamigłówka zwana figurominem, w której rozmieszczenie kamieni jest znane, natomiast brakuje cyfr. Zadanie (rys. 11) polega na wpisaniu cyfr na połówkach kamieni, jeśli wiadomo, że:

– w figurze zachowana jest podstawowa zasada gry w domino, czyli na stykających się bokami połówkach kamieni są takie same cyfry;

– w każdym rzędzie połówek kamieni, na który wskazuje czarna strzałka, są wyłącznie cyfry umieszczone obok tej strzałki.

W rozwiązaniu wystarczy podać osiem kolejnych cyfr w rzędzie wskazanym czerwoną strzałką.

Rozwiązania prosimy nadsyłać do 31 sierpnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 08/18. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Elizabeth Tasker Fabryka planet. Egzoplanety i poszukiwanie drugiej Ziemi 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ń z numeru czerwcowego

1. Zbieranie kamieni układu na rys. 12 można zacząć od kamienia A
(4 ścieżki, np. AŁLDEFHGIKMBCJ),
B (2, np. BMŁACEJIGHFDLK),
C (1 – CEJIGHFDLŁABMK),
G (4, np. GHFEDLKIJCBAŁM),
I (1 – IJECBAŁLDFHGKM),
J (1 – JECBAŁLDFHGIKM),
K (2, np. KLDEFHGIJCBMŁA) lub M (2, np. MŁABCEJIGHFDLK). Wszystkich rozwiązań (różnych ścieżek zbierania) jest więc 17.

2. Rozwiązanie graficzne na rys. 13. Zapis: 11-10-9/29-28/3-4/31-30-6-5/1-2-26-27/20-19-7-8/17-18-24-25/21-13-12/22-23/16-15-14.

3. Przykładowe rozwiązanie graficzne na rys. 14. Zapis: 1-2-3/17-18-19/23-16-24/15-14/22-4-5/9-10-11-6/21-13-12-20/8-7.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Reguła przetrwania Vitusa B. Dröschera, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Grzegorz Górzny z Wrocławia, Mateusz Harla z Krakowa, Julia Karska ze Zgorzelca, Andrzej Parafian ze Zgorzały, Daria Skrzypek z Poznania.

***

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.