Kamienne łańcuchy, czyli kombinatoryka z oczkami

Tradycyjny, powszechnie znany sposób gry w domino jest formalnie bardzo prosty. Gra uchodzi za niemal dziecinnie łatwą, skoro polega na tworzeniu łańcucha z 28 prostokątnych kamieni, dokładanych do siebie po jednym tak, aby na stykających się połówkach były identyczne cyfry (liczby oczek). Może zatem dziwić, że w takiej grze organizuje się mistrzostwa świata i to z udziałem zawodowców. Ostatnie przed pandemią odbyły się w 2019 roku w meksykańskim kurorcie Cabo San Lucas; uczestniczyło w nich ponad 300 graczy z kilkunastu krajów, w większości z Nowego Świata; Stary reprezentowały tylko Rosja, Hiszpania i… Abchazja.

Równie prosta jest struktura kompletu domina. Na połówkach każdego z 28 kamieni znajduje się inna kombinacja pary cyfr ze zbioru {0, 1, 2, 3, 4, 5, 6}, czyli od 0-0 do 6-6 – jak wiadomo cyfry te oznaczone są punktami (oczkami), podobnie jak na kostce do gry. Stąd nazwa kompletu – szóstkowy. Teoretycznie możliwe są mniejsze komplety, pojawiające się wirtualnie w łamigłówkach: piątkowy – 21 kamieni, od 0-0 do 5-5, czwórkowy – 15 kamieni, od 0-0 do 4-4 itd.; praktycznie bywają też większe (np. dziewiątkowy – 55 kamieni obejmujących wszystkie cyfry). W zestawieniu z prostotą struktury zaskoczeniem może być obfitość i złożoność wielu dominowych zagadnień kombinatorycznych. Niektóre z nich były już poruszane w tej rubryce. Pora na kolejny, najbliższy praktycznej grze, bowiem dotyczący układanych z kamieni łańcuchów.

Gdy w XIX wieku kołatanie kamieniami stało się w Europie popularną rozrywką, wnikliwi gracze zwrócili uwagę na niektóre jej aspekty matematyczne. Przejawem tego był na przykład trik, polegający na przewidzeniu, jakie cyfry znajdą się na końcach łańcucha ułożonego z prawie wszystkich kamieni zgodnie z dominową zasadą (te same cyfry na stykających się połówkach). „Prawie wszystkich”, ponieważ sztukmistrz zawczasu cichaczem zabierał z kompletu jeden kamień, zatem umieszczone na nim cyfry musiały pojawić się na końcach łańcucha złożonego z 27 pozostałych. Wynika to oczywiście z faktu, że każda cyfra występuje na połówkach kamieni parzystą liczbę razy (osiem). Ta właściwość decyduje o tym, że możliwe jest ułożenie z 28 kamieni pierścienia (cyklu), a praktycznie ramki (rys. 1). Stanowiło to inspirację do pojawienia się jednego z pierwszych związanych z grą problemów matematycznych: ile takich różnych pierścieni, a w konsekwencji różnych dominowych łańcuchów można utworzyć?

Pytanie postawił w roku 1809 francuski uczony Louis Poinsot, ale z obliczeniami uporał się dopiero pół wieku później niemiecki matematyk Michel Reiss. Uczynił to jednak w sposób tak obszerny i skomplikowany, że rezultat przyjęto z niedowierzaniem. Poprawność wyniku potwierdził dopiero kilka lat później francuski matematyk-amator Gaston Tarry, stosując znacznie prostszy i elegantszy sposób oparty na teorii grafów, utożsamianych wówczas z labiryntami. Metodę Tarry’ego warto przedstawić nieco krócej, czyli na przykładzie kompletu czwórkowego.

Cyklowi utworzonemu z piętnastu kamieni czwórkowego kompletu odpowiada tzw. pełny graf eulerowski z pętlami (rys. 2). „Pełny” oznacza, że każde dwa punkty są ze sobą połączone linią (krawędzią); „eulerowski” – bo z każdego punktu (wierzchołka) wychodzi parzysta liczba krawędzi; „pętla” jest krawędzią łączącą dany wierzchołek z nim samym. Cyfry przy wierzchołkach odpowiadają cyfrom na połówkach kamieni, zatem każda krawędź odpowiada kamieniowi z takimi cyframi na jego połówkach, jakie są na końcach tej krawędzi, a pętle oznaczają dublety, czyli kamienie z jednakową cyfrą na obu połówkach.

Teraz łatwo zauważyć, że różnych cykli, czyli ramek utworzonych zgodnie z dominową zasadą z kompletu czwórkowego jest tyle, na ile różnych sposobów można obejść graf z rys. 2, przechodząc każdą z 15 krawędzi dokładnie raz, a przez każdy wierzchołek trzykrotnie. Istotniejsze i trudniejsze jest jednak liczenie cykli w grafie bez pętli, odpowiadającym 10 kamieniom bez dubletów; z pięcioma dubletami łatwo sobie później poradzić.

Do policzenia cykli w 5-wierzchołkowym grafie eulerowskim bez pętli, zwanym K₅, Tarry zastosował metodę rekurencyjną. Zaczął od twierdzenia: gdy mamy graf eulerowski z k wierzchołkami, a w każdym wierzchołku zbiega się 2n krawędzi, to liczba cykli w tym grafie równa jest sumie cykli w (2n–1)!! (silnia podwójna – w tym przypadku iloczyn liczb nieparzystych od 1 do 2n–1) odpowiednich grafach eulerowskich z k–1 wierzchołkami. Te „odpowiednie” grafy powstają w wyniku usunięcia jednego z wierzchołków i połączenia dochodzących do niego krawędzi parami na wszystkie różne (2n–1)!! sposoby. Każdy z tych sposobów owocuje nowym grafem. Cały proces dla grafu K₅ przedstawia rys. 3.

Po połączeniu krawędzi a-b i c-d pojawiają się drugie krawędzie AB i CD, czyli graf Q1. Analogicznie powstają grafy Q2 i Q3. Wszystkie trzy grafy są izomorficzne, czyli jednakowe w tym sensie, że jeśli ich krawędzie potraktować jak elastyczne linki, to odpowiednio je kurcząc, rozciągając i/lub przeciągając poza wierzchołki, można wszystkie grafy przekształcić w jeden graf Q4. Z kolei ten graf poddawany jest podobnej metamorfozie – usunięciu jednego wierzchołka i łączeniu „uwolnionych” krawędzi parami. Tym razem ze względu na podwójną krawędź dd powstaną trzy grafy, a praktycznie dwa – T1 i T2, bo T2 obejmie dwa grafy bliźniacze (rys. 4).

Rekurencję można by kontynuować dla grafów T, ale graf T1 jest już dostatecznie prosty, więc zastosujemy ją tylko do grafu T2, otrzymując dwa grafy D1 i jeden D2.

Pora przystąpić do obliczeń. Gdyby w grafie T1 nie było pętli, byłoby w nim tyle samo cykli, co w D1 (dwa wierzchołki połączone n=4 krawędziami), a taki graf można obejść na 2(n-1)!=12 sposobów – każde obejście odpowiada innemu cyklowi, a dwa cykle różniące się kierunkiem obejścia uważamy za różne. Pętla powoduje, że liczba sposobów wzrasta dwukrotnie, bo pętlę można obejść w dwu kierunkach. Zatem w grafie T1 są 24 cykle. Obejścia grafu D2 bez pętli są 2, a dwie pętle zwiększają tę liczbę do 8. Stąd liczba obejść grafu T2=2D1+D2=24+8=32. Ponieważ jednak grafy T2 są dwa, więc liczba obejść grafu Q4 będzie równa T1+2T2=24+64=88. Teraz wystarczy tę liczbę pomnożyć przez 3 – bo graf K₅ był rozłożony na trzy grafy izomorficzne z Q4 – aby uzyskać liczbę różnych cykli dla grafu K₅ – 264.

Powracając do domina: w grafie K_k każdy dublet można umieścić na n sposobów, więc dla k=5 i n=2 sposobów jest n^k=2⁵=32. Mnożąc 264 przez 32, otrzymamy liczbę różnych cykli możliwych do ułożenia z domina czwórkowego – 8448. Z kolei rozrywając cykl na styku kamieni, a takich miejsc styku jest 15, uzyskamy liczbę różnych dominowych łańcuchów – 8448×15=126720.

Analogiczny sposób rekurencyjny, który Tarry zastosował do tradycyjnego domina szóstkowego, a praktycznie do grafu K₇ (rys. 6), jest oczywiście dłuższy i bogatszy w grafy pośrednie. Znacznie większy jest też wynik, czyli liczba cykli dla tego grafu równa 129 976 320. Umieszczanie w tym cyklu siedmiu różnych dubletów, każdego w trzech różnych miejscach, oznacza pomnożenie tej liczby przez 3⁷, co daje 284 258 211 840 cykli dominowych, a dalej – po pomnożeniu przez 28 – blisko 8 bln różnych łańcuchów z domina szóstkowego. Nic dziwnego, że tak gigantyczna liczba, kończąca 60-stronicowy elaborat uczonego Reissa, budziła wątpliwości, które rozwiał dopiero 4-stronicowy artykuł hobbysty Tarry’ego.

Gaston Tarry (1843–1913) był urzędnikiem kolonialnej administracji w Algierze. Matematyką zajmował się amatorsko, ale wystarczająco skutecznie, aby efekty jego prac cieszyły się uznaniem zawodowców, w tym takich luminarzy jak Henri Poincaré. Nie umniejsza tych zasług fakt, że większość prac Tarry’ego dotyczyła pogranicza matematyki nazywanej dziś rekreacyjną (kwadraty magiczne, kwadraty łacińskie, labirynty), zwłaszcza że jego nazwisko zostało utrwalone także w poważnej matematyce (punkt Tarry’ego w trójkącie, teorioliczbowy problem Tarry’ego-Escotta).

Liczbę cykli w dominowym grafie K₇ (bez pętli, czyli bez dubletów) można ograniczyć znacznie poniżej 129 976 320, jeśli uwzględnić permutacje i symetrie obrotowe. W ramach permutacji wystarczy umówić się, że każde dwa cykle, zawierające 7 różnych cyfr (a, b, c, d, e, f, g) – takie, że w jednym z nich wszystkie cyfry a zmieniono na b, b na c, c na d itd., aż do g na a – uznajemy za jednakowe. Takich permutacji jest 7!=5040. Gdyby wśród cykli grafu K₇ nie było cykli symetrycznych, to liczba wszystkich cykli byłaby przez 7! podzielna – a nie jest. Pod koniec XIX wieku inny francuski matematyk-amator (z zawodu pułkownik artylerii) Camille Flye Sainte-Marie zauważył, że dwa cykle mają 7-krotną symetrię obrotową (rys. 7), zatem liczba permutacji każdego z nich będzie równa 5040:7=720. Ponadto są 32 cykle z 3-krotną symetrią obrotową (liczba permutacji 5040:3=1680). Pozostaje więc (129976320–2×720–32×1680):5040=25778 cykli niesymetrycznych, a liczba wszystkich cykli po tych zmianach radykalnie maleje – od prawie 130 mln do 25 778+32+2=25 812.

* * *

Ponieważ liczby oczek na połówkach kamieni odpowiadają cyfrom, więc z kamieni traktowanych jak pary cyfr można składać liczby. Czy uda się ułożyć każdą? Wydaje się oczywiste, że nie, bo brakuje cyfr 7, 8, 9, a ponadto parzystość kamieni narzuca tworzenie liczb złożonych z parzystej liczby cyfr. Sprawa nie jest jednak tak jednoznaczna, wiąże się bowiem z kwestiami umownymi.

Jeśli przyjmiemy, że liczby mogą zaczynać się (nieznaczącym) zerem, to korzystając z kamieni z pustą, czyli zerową połówką zwaną mydłem, uczynimy nieparzystą liczbę cyfr możliwą. Jeśli zaś przeniesiemy się do siódemkowego systemu liczbowego, to dostępne staną się prawie wszystkie liczby naturalne. Prawie, ponieważ pełny luz ograniczałby możliwość tworzenia zadań. Pozostawimy więc jeden warunek: korzystamy tylko z jednego kompletu domina, czyli kamienie nie mogą się powtarzać. Wówczas najmniejszą liczbą, której nie uda się ułożyć będzie 101₇ (50 w systemie dziesiętnym), bo wymagałoby to użycia dwóch kamieni 0–1.

Łańcuch dziewięciu kamieni na rys. 8a tworzy osiem liczb. Wszystkie są równe, ale zapisane w różnych systemach liczbowych – pierwsza (14) w systemie dziesiętnym, a każda następna w systemie o podstawie o jeden mniejszej, aż do 112 w systemie trójkowym. Uzupełnić ten łańcuch następną liczbą – w systemie dwójkowym – nie sposób, bo liczba ta równa jest 1110₂, czyli wymaga kamienia 0–1, który został już wykorzystany w 112₃.

Nie jest znany inny dominowy łańcuch ośmiu równych liczb zapisanych w różnych systemach liczbowych – od dziesiętnego do trójkowego – ułożony z różnych kamieni. Gdy liczba w systemie dziesiętnym składa się z co najmniej dwóch kamieni, to łańcuch na ogół jest formalnie dłuższy, bo ma więcej cyfr, ale liczb jest w nim mniej – kończą się wcześniej, bo łatwiej o powtórki kamieni. Rzadko udaje się dotrzeć nawet do systemu szóstkowego, jak na rys. 8b. W tym przypadku następna byłaby liczba „piątkowa” 102230₅, ale w niej powtórnie gościłyby kamienie 0-1 i 0-3.

* * *

Z kompletu domina wybieramy dwa kamienie i układamy je obok siebie tak, aby tworzyły 4-cyfrową liczbę. Na rys. 9 przedstawione są cztery takie układy o szczególnej własności: w każdym kamienie dobrane są i umieszczone tak, że biorąc cyfrę z jednej połówki albo dodając do siebie kilka kolejnych, czyli sumując liczby oczek na dwóch lub więcej kolejnych, sąsiednich połówkach, można utworzyć nieprzerwany ciąg liczb od 1 do 9. Na przykład w drugim układzie liczby 1, 2, 3 są „gotowe”; pozostałe powstają w wyniku sumowania: 4=1+3, 5=3+2, 6=3+3, 7=1+3+3, 8=3+3+2, 9=1+3+3+2. Układ żadnej innej pary kamieni nie umożliwia dotarcia poza 9 bez przerwy, czyli bez pominięcia po drodze jakiejś liczby. Na przykład w trzecim układzie suma oczek na wszystkich połówkach wynosi wprawdzie 11, ale nie sposób utworzyć dziesiątki – sumowanie 2+5+3 nie jest dozwolone, bo połówki z tymi cyframi nie są kolejnymi sąsiednimi, rozdziela je połówka z jedynką. Podobnie w ostatnim układzie niedozwolone jest dodawanie 4+6.

Jak daleko uda się „zajechać” jednym ciągiem w opisany sposób, tworząc łańcuchową liczbę z trzech kamieni? Okazuje się, że do 17, jak w przykładzie na rys. 10a.

Dla czterech kamieni zadanie staje się już dość twardym orzechem do zgryzienia. Jego pierwszym rozwiązaniem, uznawanym przez kilkadziesiąt lat za najlepsze, był układ z rys. 10b, umożliwiający dojechanie bez przerw do 23.

Dopiero w latach 50. ubiegłego wieku ustalono, że rezultat daleki jest od rekordowego, bowiem „jazdę” można wydłużyć do 29 (rys. 10c). Kto pokusi się o szukanie rekordowego wyniku dla pięciu kamieni (bez powtórek), czyli 10-cyfrowej liczby bez cyfr większych niż 6? – to ostatnie z poniższych zadań konkursowych.

Zadania

1. Jeśli cykl (pierścień) z kompletu 28 kamieni ułożony jest zgodnie z dominową zasadą (jak na rys. 1), to różnica między liczbami oczek na stykających się połówkach każdej pary kamieni równa jest zero, zatem suma wszystkich 28 różnic także jest zerem. Jeżeli układając pierścień, zrezygnujemy z dominowej zasady, to wskazane różnice będą mieścić się w takim zakresie, jak cyfry na połówkach kamieni – od 0 do 6. Jaka może być wówczas największa suma wszystkich 28 różnic?

2. Na diagramie 10×10 ułożono (ujawniono tylko częściowo – rys. 11) zgodnie z dominową zasadą (jak na rys. 1) zamknięty łańcuch z kompletu 28 kamieni 2×1, spełniający trzy warunki:

a) wszystkie połówki kamieni należą do łańcucha, czyli żaden kamień z łańcucha nie „wystaje”;

b) połówki różnych kamieni stykają się bokiem tylko wtedy, gdy są dwiema kolejnymi w łańcuchu;

c) połówki różnych kamieni nigdzie nie stykają się tylko jednym rogiem.

Ujawnione są pozycje wszystkich dubletów (niebieskie). W każdym rzędzie, na który wskazuje strzałka, na połówkach kamieni są wyłącznie cyfry umieszczone obok tej strzałki.

Zadanie polega na ujawnieniu pozycji wszystkich kamieni. Jako końcowe rozwiązanie wystarczy podać sumę cyfr na połówkach kamieni, które znajdą się na przekątnych diagramu.

3. 100002 wydaje się najmniejszą liczbą ułożoną z trzech kamieni domina taką, że jej zapisy w systemach liczbowych dziewiątkowym, ósemkowym i siódemkowym także można ułożyć z domina – każdy z trzech kamieni (rys. 12). Co istotne: każdy z tuzina kamieni użytych do ułożenia tych czterech liczb jest inny. „Wydaje się”, ponieważ jeśli przyjąć, że liczby mogą zaczynać się zerem, czyli pustą połówką kamienia (mydłem), to liczba w układzie dziesiętnym (a więc także każda z trzech pozostałych) może być mniejsza. Jaka będzie najmniejsza przy zachowaniu warunku, aby żaden kamień się nie powtarzał?

4. Z 5 różnych kamieni należy utworzyć liczbę 10-cyfrową o następującej własności: biorąc cyfrę z jednej połówki albo dodając do siebie kilka kolejnych, czyli sumując liczby oczek na dwóch lub więcej kolejnych, sąsiednich połówkach, można utworzyć m liczb, będących nieprzerwanym ciągiem liczb od 1 do m, przy czym m powinno być jak największe. Za poprawne uznawane będą rozwiązania z m mniejszym od największego możliwego o 1.

Rozwiązania prosimy nadsyłać do 28 lutego br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 02/22. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Deana R. Lomaxa Jak naprawdę żyły dinozaury. Zachowania zwierząt ukryte w skamieniałościach 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 grudniowego

1. Cyfry na przekątnej (od lewego dolnego rogu do prawego górnego): 2-4-1-5-3-2-3-1. Pełne rozwiązanie na rys. 13.

2. Piątki pentomin tworzące kwadraty 5×5: FLPUX i INTVY (drugi kwadrat można ułożyć na dwa sposoby). Pełne rozwiązanie na rys. 14.

3. Cyfry na przekątnej (od lewego dolnego rogu do prawego górnego): 7-4-3-8-1-6. Pełne rozwiązanie na rys. 15.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę P.J.E. Peeblesa Stulecie kosmologii. Jak zrozumieliśmy Wszechświat, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Adrian Gracz ze Skawy, Renata Nowak z Krakowa, Andrzej Pańka z Brześcia Kujawskiego oraz Daniel Kłobuszewski i Krzysztof Żakowicz z Warszawy.

***

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”.