Namioty, magnesy, wodorosty, czyli o dominacji domin
Powszechnie przyjęło się, jakoby jedynym wyróżnionym rodzajem prostokąta, uchodzącym od wieków za swego rodzaju doskonałość, była figura równoboczna, czyli kwadrat. Zapewne tylko nieliczni wskazaliby na drugi wyodrębniony rodzaj zwany złotym prostokątem, którego długości boków – dłuższego (a) i krótszego (b) – wynikają ze złotego podziału odcinka (a+b), a więc (a+b)/a = a/b = ϕ ≈ 1,618. Ale na tym nie koniec, bowiem jest jeszcze trzeci rodzaj, wyróżniony najpierw w matematyce rekreacyjnej, a potem przez matematyków, zajmujących się geometrią dyskretną, a ściślej – parkietażami. Chodzi o prostokąt zwany dominem albo dimerem, a więc taki, którego jeden bok jest dwukrotnie dłuższy niż drugi; czasem taki prostokąt definiuje się jako złożony z dwóch kwadratów – podobnie jak kamień do gry w domino tworzą dwie kwadratowe połówki.
Droga domino-prostokąta do samodzielności zaczęła się od zadania zamieszczonego w wydanej w 1946 roku książce amerykańskiego filozofa Maxa Blacka Critical thinking. Dziś zadanie to uchodzi za klasyczne. Polega na ustaleniu, czy po wycięciu z szachownicy (8×8) dwu narożnych pól z końców tej samej przekątnej pokrycie pozostałych 62 kratek dominami (każdy zakrywa dwie) będzie możliwe (rys. 1). Skorzystanie z szachownicy stanowi jakby podpowiedź, bo nietrudno zauważyć, że usunięto pola tego samego koloru, czyli pozostały 32 ciemne i 30 jasnych (lub odwrotnie), a skoro każde domino zakrywa dwa pola różnego koloru, to liczby pól jasnych i ciemnych powinny być równe.
Jeżeli z szachownicy usunąć dwa pola różnego koloru, to pokrycie 62 pozostałych dominami będzie zawsze możliwe. Natomiast po usunięciu czterech pól – dwóch jasnych i dwóch ciemnych – już niekoniecznie. Nie uda się to na przykład wtedy, gdy ubędzie para pól takiego samego koloru obok pola narożnego, bo tym samym odcięty zostanie róg szachownicy.
Popularność zadania Blacka zainspirowała matematyków do zwrócenia uwagi na dominowe parkietaże, co spowodowało „wybicie się na niepodległość” domina jako typu prostokąta. Za pierwszoplanowe uznano określenie warunków, jakie powinien spełniać wielokąt złożony z jednostkowych kwadratów (połówki domina), aby możliwe było pokrycie go dominami. Chodziło oczywiście o warunki konieczne i dostateczne, a nie tylko konieczne, jak kryterium szachownicowe (równe liczby ciemnych i jasnych pól). Zagadnieniem zajęło się wielu matematyków, także tych z górnej półki. Na przykład William Thurston (laureat Medalu Fieldsa) sformułował w 1990 roku, korzystając z teorii grafów, kryterium pokrywalności. W pełnej formie jest ono zbyt obszerne, aby je tu opisać, ale warto wspomnieć o stanowiącym jego podstawę twierdzeniu Thurstona: jeśli jakiś zwarty (bez otworów) wielokąt ma więcej niż jedno pokrycie dominami, to wszystkie te pokrycia są wzajemnie przekształcalne – przez obroty o 90° par domin tworzących kwadrat 2×2. Na rys. 2 znajduje się przykład takich przekształceń wszystkich czterech możliwych pokryć kwadratu 3×3 bez narożnego pola. Prosty sposób wykazania niepokrywalności podał wcześniej Philip Hall (laureat m.in. Medalu Sylvestra przyznawanego przez brytyjskie Royal Society). Na rys. 3 sześć ciemnych pól z czerwoną kropką potrzebuje sześciu jasnych do utworzenia domin. Tymczasem sąsiadujących z nimi jasnych pól jest tylko pięć (z niebieską kropką; pomarańczowe pole to otwór w wielokącie), zatem „zdominowanie” całej figury – mimo że liczby jasnych i ciemnych kratek są takie same – nie jest możliwe. Znalezienie w wielokącie takiego obszaru, w którym nie uda się sparować jasnych i ciemnych pól, oznacza więc, że wielokąt ten jest niepokrywalny dominami.
Przeważająca większość publikacji o dominowych parkietażach dotyczy prostokątów. W roku 1961 trzej matematycy – Michael Fisher, Harold Temperley i Pieter Kasteleyn – wyprowadzili osobliwy wzór na liczbę P(2m,2n) sposobów pokrycia dominami prostokąta o długościach boków, wyrażających się liczbami parzystymi (2m, 2n). „Ojciec algorytmiki” Donald Knuth i James Propp przekształcili ten wzór do postaci, obejmującej wszystkie prostokąty m×n:
Wzór jest nie tylko osobliwy, ale i ekstremalny. Jego główną część stanowi iloczyn (mnożenie oznaczają duże litery Π, małe to 180°) m×n sum kwadratów wartości funkcji trygonometrycznych (to pierwsza osobliwość), które nie zawsze są liczbami wymiernymi, a mimo to (to druga osobliwość) wynik jest zawsze liczbą całkowitą dodatnią. Ekstremalność polega na tym, że korzystanie z tego wzoru bez wsparcia komputera lub wysokiej klasy kalkulatora jest praktycznie niemożliwe. Aby na przykład obliczyć, na ile sposobów można pokryć dominami szachownicę 8×8, trzeba utworzyć i pomnożyć przez siebie 64 sumy i na koniec wyciągnąć z iloczynu pierwiastek czwartego stopnia. Wynik, 12 988 816, jest kwadratem, a poza tym – co także wydaje się osobliwe – wszystkie liczby pokryć dominami kwadratów o boku, którego długość jest liczbą parzystą (2n×2n), również są albo drugimi potęgami, albo ich dwukrotnościami, czyli wartości P(2n,2n) wynoszą dla n=1, 2, 3,…: 2×12, 62, 2×582, 36042, 2×359 5722, 230 348 6002…. W niektórych przypadkach P(m,n) można także obliczać dla konkretnych wartości m, korzystając z wzorów rekurencyjnych. Na przykład P(2,n)=P(2,n–1)+P(2,n-2) (ciąg Fibonacciego); P(3,n)=4P(3,n–2)+P(2,n–4); P(4,n)=P(4,n–1)+5P(4,n–2)+P(4,n–3)–P(4,n–4).
Zapewne formalna prostota dominowych parkietaży sprawiła, że prac naukowych poświęconych wnikliwej analizie różnych aspektów tego zagadnienia pojawiło się dotąd grubo ponad 100 i ciągle ich przybywa. Niektórzy matematycy, jak wspomniany James Propp z University of Massachusetts Lowell, są autorami kilku. Część tych prac jest bliska matematyce rekreacyjnej, a zawarte w nich analizy prowadzą do ciekawych wniosków. O kilku warto wspomnieć.
Do podanego wyżej twierdzenia Thomsona nawiązuje wniosek następujący: w każdym prostokątnym dominowym parkietażu musi znaleźć się utworzony z dwóch domin kwadrat 2×2 – co najmniej jeden. Próba uniknięcia go, czyli „jodełkowego” układania domin, zawsze prowadzi do pojawienia się jednego takiego kwadratu w ściśle określonym miejscu (z dokładnością do obrotów i odbić lustrzanych), na przykład dla prostokąta 5×6 w takim, jak niebieski kwadrat na rys. 4a. Inny wniosek dotyczy tzw. parkietaży bez szwu. Szwem jest linia prosta biegnąca brzegami domin, łącząca brzegi prostokąta – np. czerwona na rys. 4a. Okazuje się, że parkietaż bez szwu możliwy jest tylko w przypadku prostokątów m×n, których m≥5 i n≥5 (przynajmniej jedna z tych wartości musi być oczywiście parzysta), ale z jednym wyjątkiem – nie sposób pozbawić szwu prostokąta 6×6; przykład najmniejszego bez szwu (5×6) – na rys. 4b. Inny wniosek, dość prosty do udowodnienia, brzmi: liczba różnych parkietaży prostokąta m×n jest nieparzysta wtedy i tylko wtedy, gdy m+1 i n+1 są względnie pierwsze, czyli nie mają wspólnego dzielnika większego niż 1.
Omawiane dotąd liczby pokryć dominami prostokątów dotyczą różnych pokryć, ale nie całkowicie różnych, tzn. dwa, z których jedno powstaje w wyniku obrotu lub odbicia lustrzanego drugiego, uważane są za różne. Niestety, z określeniem liczby całkowicie różnych parkietaży P’(m,n) matematycy na razie sobie nie poradzili – poza najprostszym przypadkiem P’(2,n), czyli prostokątami o boku równym 2, liczby całkowicie różnych pokryć, których dla kolejnych n tworzą ciąg P’: 1, 1, 2, 4, 5, 9, 12, 21, 30, 51, 76, …, będący modyfikacją ciągu Fibonacciego F: 1, 2, 3, 5, 8, 13, 21, 34, 55, 91, 146, …. Modyfikację tę nietrudno rozszyfrować, jeśli zauważyć, że np. czwarty wyraz ciągu P’ równy jest połowie sumy czwartego i trzeciego wyrazu ciągu F, a piąty wyraz P’ to połowa sumy piątego i drugiego wyrazu F.
Obecność dominowego prostokąta w parkietażach jest bliska matematyce rekreacyjnej. Nic więc dziwnego, że niektórzy z zajmujących się tym tematem matematyków, jak choćby wspomniani Donald Knuth i James Propp, znani są także z zamiłowania do gimnastyki szarych komórek i związanych z tym popularnych publikacji. Stąd tylko krok do bardziej spektakularnej obecności domin w intelektualnej rozrywce, a więc do łamigłówek. Wszystkie polegają na rekonstrukcji układu domin na diagramie. Różnią się tylko „przesłankami”, czyli informacjami stanowiącymi klucz do rozwiązania, a korzystanie z tego klucza wymaga niekiedy bardzo giętkiego umysłu.
W roku 1989 na łamach holenderskiego pisma Eureka ukazało się pierwsze zadanie z dominami, którego wygląd i tytuł ( „Zbierz wszystkie kulki”) nie sugerowały niczego dominowego. Domina pojawiają się bowiem dopiero w rozwiązaniu (rys. 5a), a tytułowe kulki są na ich połówkach – na każdym dominie jedna ciemna i jedna jasna. Aby cofnąć się i z rozwiązania utworzyć zadanie, wystarczy usunąć zarysy wszystkich domin i wszystkie białe kulki, a przy brzegach diagramu umieścić kilka liczb (rys. 5b). Każda liczba oznacza, ile białych kulek powinno znaleźć się w danym wierszu lub kolumnie. Odtwarzając pozycje białych, czyli praktycznie granice domin, należy pamiętać o jednym warunku: dwie białe kulki nigdzie nie mogą trafić do sąsiednich kratek – nawet stykających się tylko rogami. Aby uatrakcyjnić łamigłówkę, wkrótce ją „urealniono”, zmieniając formę i nazwę. Diagram stał się polem kempingowym, czarne kulki – drzewami, a białe – przymocowanymi do drzew namiotami. W tej postaci zadanie pod nazwą „tentje-boompje” (Drzewko-namiociki) stało się w latach 90. jakby holenderską łamigłówką firmową, zyskując sporą popularność jako „drzewa i namioty” w wielu krajach i będąc swego rodzaju zwiastunem epidemii sudoku. Przykład na rys. 6 jest dość trudny.
Podobny, ale logicznie bardziej skomplikowany i ciekawszy pomysł debiutował na 10. Łamigłówkowych Mistrzostwach Świata w Brnie (2001) – domina stały się magnesami, czyli na połówkach każdego pojawił się plus i minus. Zadanie może wyglądać na przykład tak, jak na rys. 7. Tym razem, jak widać, gęsto od domin jest już na początku, a rozwiązywanie polega na likwidowaniu tego tłoku. Niektóre domina trzeba bowiem usunąć, czyli zaczernić (przekreślić), a pozostałe zmienić w magnesy, a więc oznaczyć na ich połówkach plusy (+) i minusy (–). Jak to zrobić, wskazują liczby obok diagramu. Każda oznacza, ile plusów lub minusów powinno pojawić się w danym wierszu lub kolumnie. Brak liczby jest tylko brakiem informacji, więc nie oznacza, że w danym rzędzie jakichś znaków nie ma. Poza tym istotny jest magnetyczny warunek: dwa jednoimienne bieguny, czyli dwie połówki domin z plusem lub dwie z minusem nie mogą stykać się bokami. Dla jasności przyda się mały przykład z rozwiązaniem (rys. 8), zwłaszcza że zadanie na rys. 7 jest dość twardym orzechem.
Od blisko dekady łamigłówkowym przebojem w Japonii jest dominowe zadanie o nazwie norinori. Nori to popularne w japońskim menu jadalne wodorosty, służące m.in. do zawijania sushi, sprzedawane w postaci sprasowanych prostokątnych arkuszy zbliżonych kształtem do domin (podwojone „nori” to japoński sposób na liczbę mnogą). Reguły „wodorostów” są urokliwie proste. Na rozparcelowanym diagramie (rys. 9) należy oznaczyć domina tak, by w każdej działce znalazły się dokładnie dwie połówki każdego, a domina nigdzie nie stykały się bokami; rogami mogą. Tak więc niektóre domina w całości obsłużą tylko jedną działkę, a inne „rozdwoją się”, trafiając połówkami w różne, ale sąsiednie działki. Prosty przykład znajduje się na rys. 9 z lewej strony, a niełatwe zadanie obok.
Z trzema innymi rodzajami zadań dominowych z japońskim rodowodem można się zmierzyć, rozwiązując poniższe łamigłówki konkursowe.
Zadania
1. Na niektórych pustych polach szachownicy 10×10 (rys. 10) trzeba oznaczyć domina tak, aby, stykając się rogami, podzieliły planszę na pięć oddzielnych obszarów (wielokątów). W każdym obszarze powinny znaleźć się tylko jednakowe figury. Zabronione jest stykanie się domin bokami. Zasadę dzielenia planszy ilustruje mały przykład obok zadania. W rozwiązaniu wystarczy podać wielkości rozdzielonych obszarów, czyli liczby tworzących je pól (w przykładzie wieże-4, gońce-6, skoczki-7).
2. Na rozparcelowanym diagramie (rys. 11) należy oznaczyć domina podobnie jak w norinori. Różnica jest tylko taka, że liczbę połówek domin, które powinny trafić do danej działki, określa znajdująca się w działce liczba. Jeśli liczby brak, to znaczy, że podawanie jej nie jest konieczne. Domina nie mogą stykać się bokami; rogami mogą. Mogą także obejmować pola z liczbą. W rozwiązaniu wystarczy podać, ile pól na przekątnych diagramu zajmują domina.
3. Na połówkach domin znajdują się litery A, B, C, ale możliwe są tylko trzy rodzaje domin – każde z parą różnych liter, czyli A-B, A-C i B-C. Na diagramie (rys. 12) ujawniono niektóre litery; wszystkie brakujące należy wpisać w odpowiednie pola, oznaczając równocześnie domina. Ponadto utworzony układ domin powinien spełniać następujące warunki:
• dwa takie same domina nie mogą stykać się bokami; rogami mogą;
• jeśli połówki dwóch różnych domin stykają się bokami, to na tych połówkach musi być taka sama litera;
• wszystkie domina muszą tworzyć spójny obszar, a więc jeden wielokąt (niekoniecznie zwarty, czyli może być z otworami).
W rozwiązaniu wystarczy podać, ile pól na przekątnych diagramu zajmują domina.
Rozwiązania prosimy nadsyłać do 30 kwietnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 04/20. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Thomasa Morrisa Tajemnica eksplodujących zębów oraz inne ciekawostki z historii medycyny 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 lutowego
1. Oprócz n=3, 9 i 11 jeszcze n=33 i 99 mają tę własność, że odwrotka każdej liczby podzielnej przez n także jest podzielna przez n.
2. Suma liczby i jej odwrotki nie może składać się tylko z cyfr nieparzystych, z których każda będzie inna. Aby ostatnia cyfra sumy była nieparzysta pierwsza cyfra (a) i ostatnia cyfra (b) liczby muszą różnić się parzystością. Ponieważ suma a+b występuje w pierwszej i ostatniej kolumnie dodawania, więc pierwsza lub druga cyfra sumy albo będzie taka sama (nieparzysta) jak ostatnia albo będzie o jeden większa, czyli parzysta.
3. Liczby całkowite, które można przedstawić w postaci odejmowania dwu 5-cyfrowych liczb naturalnych, z których jedna jest odwrotką drugiej – są 323 (17×19) lub 342 (18×19), jeśli uwzględnić liczby kończące się zerami, których odwrotki są krótsze (zaczynają się zerami).
4. Odjemnik równy jest 41 399 (99 314–41 399=57 915).
Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Jak wynaleźć wszystko. Cała wiedza ludzkości w jednej książce Ryana Northa, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Patryk Dumański z Warszawy, Sebastian Janczy z Pruszcza Gdańskiego, Tomasz Kowalczyk z Krakowa, Marta Polak z Wrocławia, Marcin Świerczyna z Grabownicy