Domino i matematyka Ten tekst przeczytasz w 6 minut

Felietony w dziale „Matematyka w grach” opisują zwykle zastosowanie matematyki do analizy zagadnień, występujących w różnych grach planszowych. Tym razem chciałbym pokazać sytuację odwrotną – jak gra domino przyczyniła się do rozwiązania dwóch zagadnień naukowych.

Na początek jednak podstawowe pytanie:

Z ilu kamieni składa się zestaw domina i dlaczego z tylu?

Pytanie może wydawać się dziwne – przecież wiadomo, że w zestawie jest 28 kamieni. To prawda – ale to dotyczy klasycznego domina szóstkowego. Jeszcze 30 lat temu inne zestawy były w Polsce praktycznie nieznane. Jednak w ostatnich kilkunastu latach sytuacja się zmieniła. Można kupić domino dziewiątkowe (czyli takie, które na połówkach kamieni ma od zera do dziewięciu oczek), dwunastkowe, a nawet piętnastkowe.

Jeżeli oznaczymy maksymalną liczbę oczek na połówce kamienia przez n (a więc w dominie szóstkowym n=6), to ze względu na obecność mydeł czyli połówek bez oczek mamy w komplecie kombinacje 2 elementów z n+1, odpowiadające dominom z różnymi liczbami oczek na obu połówkach oraz n+1 dubletów. Wzór na liczbę kamieni wygląda więc tak:

Jak łatwo sprawdzić, dla domina szóstkowego daje to 7*8/2 = 28. Oczywiście do tego samego wyniku można dojść stosując kombinacje z powtórzeniami. A jeżeli ktoś chce wiedzieć, ile jest razem oczek na wszystkich kamieniach, to określa to wzór:

W tabelce można odczytać wyniki obliczeń, przeprowadzonych na podstawie powyższych wzorów, dla różnych zestawów domina

Wariant domina	Liczba kamieni	Liczba oczek
Szóstkowe	28	168
Ósemkowe	45	360
Dziewiątkowe	55	495
Dwunastkowe	91	1092
Piętnastkowe	136	2040

Układanie łańcucha i cykle Eulera

Do tego by zauważyć, że z wszystkich 28 kamieni domina szóstkowego można zbudować łańcuch zgodny z zasadami gry (tzn. sąsiadujące ze sobą połówki kamieni mają taką samą liczbę oczek), nie potrzeba wiedzy matematycznej. Ale policzenie, na ile różnych sposobów można taki łańcuch skonstruować, to już zagadnienie bardzo trudne. Jako pierwszy jego rozwiązanie podał w napisanym w 1859 roku, a opublikowanym w 1871 artykule M. Reiss [1]. W efekcie dość zawiłych obliczeń, zajmujących 58 stron, uzyskał wynik: 7 959 229 931 520.

Dziewiętnastowieczny francuski popularyzator matematyki Edouard Lucas, zacytował powyższy rezultat w swojej książce [2] zaznaczając jednak, że metoda Reissa jest bardzo skomplikowana i trudna do zweryfikowania. W następnym wydaniu książki Lucas poinformował czytelników, że Charles-Ange Laisant zaproponował, by do rozwiązania problemu dominowego łańcucha zastosować teorię grafów, a Jolivard i Tarry przeprowadzili oparte na tej teorii obliczenia.

 

Jeżeli z zestawu 28 kamieni domina szóstkowego usuniemy dublety, to pozostałe 21 kamieni możemy przedstawić w postaci grafu pełnego K7. Każdy z 7 wierzchołków tego grafu (czyli granatowych kropek) odpowiada innej liczbie oczek (od 0 do 6). Każda łącząca kropki linia czyli krawędź grafu, oznacza jeden z 21 kamieni. Cyklem Eulera nazywamy drogę, przechodzącą przez każdą krawędź grafu dokładnie raz. A więc zamknięty łańcuch, złożony z 21 kamieni jest cyklem Eulera. Zagadnienie sprowadza się zatem do policzenia, ile jest cykli Eulera w grafie pełnym K7.

Rozwiązanie tego problemu przedstawił Gaston Tarry w artykule:

GEOMETRY OF POSITION: NUMBER OF DIFFERENT WAYS OF TRAVERSING ALL THE ALLEYS OF A RE-ENTRANT LABYRINTH IN A SINGLE WALK, PASSING ONLY ONCE THROUGH EACH ALLEY

Graficzne wyjaśnienie podanych w tekście wzorów można zobaczyć na dwóch obrazkach:

       

Z wykonanych przez Tarry’ego obliczeń wynika, że liczba cykli Eulera w grafie pełnym K7 wynosi 129 976 320. Tyle różnych pierścieni czyli zamkniętych łańcuchów można utworzyć z 21 kamieni domina. Teraz dołóżmy dublety. Każdy z 7 dubletów może być wstawiony do łańcucha w 3 miejscach, bo są w łańcuchu trzy pary sąsiadujących mydeł, trzy pary jedynek itd. Zamknięty pierścień możemy rozerwać w jednym z 28 miejsc – między każdą parą sąsiadujących ze sobą kamieni. Końcowy wynik obliczeń to zatem 129 976 320 x 3^7 x 28 = 7 959 229 931 520 czyli dokładnie tyle, ile otrzymał Reiss.

Podział płaszczyzny na domina

Jak widać na powyższym rysunku, prostokąt 3×2 można podzielić na kamienie domina czyli prostokąty 2×1 na trzy sposoby. Wprawdzie w grze w domino znaczenia to nie ma ale okazuje się, że liczba podziałów jest ważna w chemii, a konkretnie w badaniach dotyczących dimerów, czyli najprostszych oligomerów, złożonych z dwóch cząsteczek. Zagadnienie to nazwane zostało „domino tiling” czyli podział na domina.

Liczbę podziałów prostokąta 3×2 policzyć łatwo ale w przypadku figur nieregularnych, a nawet większych prostokątów, sprawa jest znacznie trudniejsza. Na ile sposobów można np. podzielić na domina pokazaną na obrazku figurę:

Przypuszczam, że niewiele osób jest w stanie to policzyć, więc podaję wynik: na 2024 sposoby. Jak to policzyłem, a raczej: jak to policzył komputer? Otóż liczba możliwych podziałów jest pierwiastkiem kwadratowym z wartości bezwzględnej wyznacznika, zawierającego informacje o sąsiedztwach kwadracików z powyższego obrazka. Konkretnie: jeżeli dwa kwadraciki sąsiadują ze sobą w poziomie, to odpowiada tej parze wartość 1, jeżeli sąsiadują w pionie – jednostka urojona i, a gdy nie sąsiadują – zero [3]. Oczywiście nie będę tutaj podawał opisującej obrazek macierzy 36×36, tylko pokażę to na prostszym przykładzie prostokąta 3×2. Jeżeli ponumerujemy należące do tego prostokąta kwadraciki w sposób pokazany na kolejnym obrazku:

to wyznacznik będzie wyglądał tak:

Mimo, że wyznacznik zawiera liczby urojone, jego wartość jest liczbą całkowitą. Konkretnie jest to liczba 9, z której pierwiastkiem kwadratowym jest 3 czyli tyle, ile wyjść powinno.

Jeżeli dzielona na domina figura jest prostokątem mxn, to liczba możliwych podziałów jest określona wzorem [3]:

w którym symbol ∏ oznacza mnożenie wyrazów w nawiasie (tu pionowe kreski symbolizują wartość bezwzględną) dla kolejnych wartości l od 1 do m i k od 1 do n. Wzór wygląda bardzo dziwnie, bo jest w nim użyta funkcja cosinus, choć żadnych kątów (poza prostymi) nie widać. Ale najdziwniejsze jest to, że choć czynnikami w tym iloczynie są liczby zespolone z niewymiernymi częściami rzeczywistymi i urojonymi, to wynik jest zawsze liczbą całkowitą.

Jak ktoś nie lubi liczb zespolonych, to może zastosować jeden z dwóch poniższych wzorów, w których cosinusy są w drugiej potędze:

Jeżeli chcemy policzyć liczbę podziałów dla prostokąta 3×2, to w środkowym wzorze j może przyjmować wartości 1 lub 2, a k tylko 1, mamy więc w rezultacie iloczyn dwóch sum:

(4cos²(π/4) + 4cos²(π/3)) (4cos²(π/2) + 4cos²(π/4)) = (2 + 1) (0 + 1) = 3

Oczywiście pierwszy i trzeci wzór dają ten sam wynik (jak ktoś nie wierzy, może sprawdzić).

A co w sytuacji, gdy oba boki prostokąta mają nieparzystą długość? Wtedy w każdym z trzech powyższych wzorów pojawi się przynajmniej jeden wyraz o wartości 0 (bo cosinus π/2 jest równy 0) i w związku z tym iloczyn będzie równy 0.

Jeżeli dzielona na domina figura jest prostokątem o szerokości 2, to można zauważyć pewną własność rekurencyjną:

Ostatni kamień z prawej strony prostokąta nx2 może zostać umieszczony pionowo i wtedy po jego lewej stronie mamy prostokąt o długości n-1. Druga możliwość zakończenia prostokąta to umieszczenie ma jego prawym końcu dwóch poziomych kamieni. Wtedy po lewej stronie mamy prostokąt o długości n-2. Liczbę możliwych podziałów prostokąta nx2 można więc opisać wzorem rekurencyjnym:

L(n) = L(n-1) + L(n-2)

A zatem liczba możliwości podziału prostokąta nx2 określona jest przez ciąg Fibonacciego. Wzory rekurencyjne zostały sformułowane dla kilku innych układów, takich jak np. prostokąty o szerokości 3 lub 4 oraz przecinających się prostokątów o szerokości 2. A na koniec ciekawy kształt czyli tzw. diament Azteków [4]:

Pokazany na rysunku diament Azteków ma rząd 3 (diament rzędu 1 to po prostu kwadrat 2×2). Liczba możliwości podziału diamentu Azteków rzędu n określona jest wzorem:

2^{n (n+1)/2}

 

Bibliografia:

1. M. Reiss, Evaluation du nombre de combinaisons desquelles les 28 d´es ´ d’un jeu du domino sont susceptibles d’apr`es la r`egle de ce jeu, Ann. Mat. Pura Appl. (2), 5 (1871–3) 63–120.
2. Edouard Lucas „Recreatios Mathematiques”, Librairie Albert Banchard, 1892
3. P. W. Kasteleyn. „The statistics of dimers on a lattice : I. The number of dimer arrangements on a quadratic lattice.” Physica 27 (December 1961) 1209-1225
4. Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp. „Alternating-sign matrices and domino tilings.” I. J. Algebraic Combin., 1(2):111–132, 1992.