Logika domina, czyli kwadryle Lucasa
Typowy, tradycyjny komplet domina (rys. 1) nazywamy szóstkowym, ponieważ szóstka jest największą liczbą oczek na połówkach 28 kamieni. Komplet obejmuje wszystkie pary liczb od zera do sześciu, ale można z niego wyodrębniać mniejsze komplety. Podkomplet dwójkowy, złożony z sześciu kamieni (rys. 1 u góry, na szarym tle), jest najmniejszym, którego wydzielenie ma sens, ponieważ przydaje się do paru prostych łamigłówek. Jedna z nich polega na ułożeniu kamieni w taki sposób, aby każde ich cztery połówki z jednakową liczbą oczek tworzyły kwadrat 2×2, a więc w przypadku kolorowego domina powinny powstać trzy połączone kwadraty – każdy w innym kolorze. Łatwo zauważyć, że możliwe są tylko trzy układy z trzech kamieni, których cztery połówki tworzą wymagany kwadrat (rys. 2). Pierwszy układ należy jednak odrzucić, bo połówki b i c są za daleko od siebie, więc nigdzie nie uda się umieścić kamienia b-c. Dwa pozostałe układy prowadzą do geometrycznie jedynego rozwiązania (rys. 3; w środku schemat ogólny zwany komórkowym). Arytmetycznie rozwiązań jest sześć, bo każdą literę można zastąpić dowolną z trzech liczb – jeden z konkretnych układów na rys. 3 z prawej.
Ta dziecinnie prosta układanka stała się w połowie XIX wieku, a więc w okresie dominowego boomu w Europie, zalążkiem tematu zapoczątkowanego i wnikliwie analizowanego przez kilku ówczesnych matematyków francuskich (Gastona Tarry’ego, Émile’a Lemoine’a, Ernesta Laquière, Charles-Ange Laisanta, Henriego Delannoya, Édouarda Lucasa). Wprawdzie nie byli to uczeni wysokiego lotu, choć kilka nazwisk pojawia się w fachowej terminologii (ciąg Lucasa, punkt Tarry’ego, punkt Lemoine’a, liczby Delannoya), ale wszyscy zasługują na miano pionierów wykorzystania matematyki rekreacyjnej w edukacji, czyli prekursorów uczenia przez zabawę. Wyróżnienie w tym gronie należy się zwłaszcza Lucasowi, autorowi trzytomowego dzieła poświęconego rozrywkom matematycznym, wydanego w roku 1892. Część drugiego tomu dotyczy łamigłówek dominowych. Znajduje się w niej rozdział zatytułowany „Kwadryle” (Les Quadrilles), zaczynający się od ilustracji, będącej graficzną definicją tytułowych obiektów (rys. 4a). Z pełnego kompletu domina ułożony jest kwadryl – krewniak figury z rys. 3: takie same liczby na połówkach tworzą 4-liczbowe kwadraty 2×2, a ponieważ w komplecie każda z siedmiu liczb pojawia się 8 razy, więc wszystkich kwadratów jest 14 – po 2 z każdą liczbą. Z czasem ten i inne kwadryle „ożywiono”: stały się 14-komórkowcami – organizmami zbudowanymi z 7 różnych kwadratowych komórek, z których każda występuje dwukrotnie (rys. 4b); a ponadto organizmami mającymi dominową strukturę (rys. 4c)
Komplety dwójkowy i szóstkowy są praktycznie jedynymi, które umożliwiają tworzenie układów z charakterystycznymi dla kwadryli kwadratowymi komórkami. Wynika to z faktu, że w kompletach tych liczba połówek kamieni z taką samą liczbą jest wielokrotnością czterech – tak jest wówczas, gdy największa liczba w komplecie wyraża się wzorem 4k–2 (k = 1, 2, 3, …). Dla k=1 mamy komplet dwójkowy, dla k=2 klasyczny szóstkowy. Dla k≥3 komplety są niepraktyczne ze względu na nadmiar kamieni (66 dla k=3), co czyni zabawę zbyt żmudną i skomplikowaną, aczkolwiek w ewentualnej teorii kwadryli należałoby uwzględniać wszystkie „czwórkowe” komplety.
Istnieje tylko jeden „gatunek” minikwadryla z kompletu dwójkowego (rys. 2). Ile jest różnych kwadryli szóstkowych – dokładnie nie wiadomo, szacunkowo kilkaset. Kwadryle są oczywiście różne, jeśli mają różny kształt. Jeżeli natomiast kształt jest taki sam, to „różne” oznacza niemożność zmiany jednego kwadryla w inny w wyniku obrotów i odbić lustrzanych (gdy kształt jest symetryczny, jak na rys. 4) albo w wyniku zamiany miejscami wszystkich cyfr x z cyframi y. W praktyce główne kryterium odmienności kwadryli o jednakowym kształcie stanowi położenie dubletów (szare na rys. 4c), a drugim kryterium jest rozmieszczenie cyfr.
Gdyby wziąć komplet 28 kamieni i spróbować ułożyć z nich jakikolwiek kwadryl, nie znając jego kształtu, to szansa powodzenia byłaby bliska zeru. Przede wszystkim dlatego, że musi być spełnionych kilka warunków. Co gorsza, wszystkie one są konieczne, ale w sumie nie tworzą warunku dostatecznego. Kwadryl-wizytówka (rys. 4a) zaprezentowany przez Lucasa, ułożony przez Delannoya, stanowił więc owoc benedyktyńskiej pracy, w której najtrudniejsze było trafienie w odpowiedni (z założenia symetryczny) kształt. Nie wiemy, w jaki sposób Delannoy zmierzał do celu. Jest mało prawdopodobne, aby znał warunek podany dopiero w połowie XX wieku przez holenderskiego matematyka Frederika Schuha:
(1) kwadryl musi mieć co najmniej 10 kątów (ale tylko jeden 10-kąt jest kwadrylem – i nie jest on symetryczny).
Natomiast z pewnością wiedział, że:
(2) każda para komórek jednoimiennych (z taką samą cyfrą x) powinna w sumie sąsiadować bokami z co najmniej sześcioma komórkami, w tym dokładnie z sześcioma z różnymi cyframi innymi niż x.
Jeśli więc do każdej komórki wpiszemy liczbę jej sąsiadek (np. niebieskie liczby na rys. 4b), to:
(3) suma wszystkich 14 liczb powinna być nie mniejsza niż sześciokrotność liczby par komórek, czyli 7×6=42.
Na rys. 4b suma ta jest znacznie większa (50), co teoretycznie stwarza bardzo wiele możliwości tworzenia par komórek jednoimiennych, jednak ograniczenie stanowi warunek (2).
Kluczem do konstruowania kwadryla są także możliwe układy trzech lub czterech kamieni tworzących komórkę. Jeśli kamienie są trzy, to jest wśród nich dublet, a możliwe układy są trzy (rys. 2). Jeżeli natomiast komórkę tworzą połówki czterech kamieni, to różne ich układy mogą być cztery (rys. 5).
Praktycznie rekonstrukcja kwadryla o zadanym kształcie – a właściwie kwadryli, bo zwykle efektem jest przynajmniej kilka różnych – z reguły obejmuje dwa etapy. Pierwszy etap ogranicza się do geometrii, czyli podziału 14-komórkowca na dominowe prostokąty – bez uwzględniania liczb, ale trzeba pamiętać o tym, że dubletów jest 7, a każdy kamień, czyli każda para liczb występuje dokładnie raz. Lucas nazwał ten etap wyznaczaniem ram. Dla kwadryla o takim kształcie, jak na rys. 3, ustalone wstępnie jednoznaczne fragmenty ram przedstawione są na rys. 6: kreski oznaczają miejsca, w których muszą leżeć kamienie (czerwone kreski to dublety), krzyżyki – miejsca, gdzie kamieni być nie może. Dalsza skomplikowana i żmudna analiza prowadzi do wyznaczenia czterech możliwych ram (na rys. 6 w postaci kreskowej). Równie zawiły jest drugi etap, czyli wypełnianie ram literami zastępującymi cyfry. Efektem jest ustalenie liczby różnych kwadryli: dla ramy I jest ich 8, dla ramy II – 4, dla ramy III – 14, dla ramy IV – 8. W sumie są zatem 34 różne kwadryle o zadanym dwusymetrycznym kształcie. Konkretny przykład na rys. 4a jest jednym z ośmiu odpowiadających ramie I z rys. 7.
Powyższy opis rekonstrukcji 34 kwadryli jest z konieczności ogólnikowy, ponieważ pełna analiza zajęłaby więcej miejsca niż cały ten artykuł. Jednak to wyjątek, bo „wypełnianie” większości kwadryli, zwłaszcza niesymetrycznych, jest dość prostą i wciągającą łamigłówką. Przykładem może być wspomniany wcześniej jedyny kwadryl 10-kątny, przedstawiony w komórkowej postaci na rys. 8.
Podstawą logicznego wnioskowania są, jak poprzednio, dwie cechy kompletu: nie ma dwóch identycznych kamieni, a dubletów jest siedem. I w tym przypadku właśnie od dubletów warto zacząć, oznaczając miejsca, w których muszą się one pojawić.
Jedyna możliwa pozycja dubletów w komórkach a i f pozwala wyznaczyć granice sąsiednich kamieni. Następnie łatwo ustalić konieczne pozycje dubletów w komórkach l, m, n oraz k i na końcu j – inne pozycje doprowadziłyby do powtórzenia się kamieni. W ten sposób siedem różowych dubletów i kilka sąsiednich kamieni trafia na swoje miejsca (rys. 9). Dalej jak po sznurku można dokończyć całą „ramę”, czyli narysować granice wszystkich kamieni, a potem, dla usprawnienia rozwiązywania, przypisać dubletom konkretne liczby (rys. 10). Warto też zauważyć, że niejako przy okazji ujawnione zostały trzy kamienie: 1–3, 4–5 i 5–6.
Końcowym etapem jest przyporządkowanie cyfr od 0 do 6 literom b, c, d, e, g, h, i. W tym celu przyda się poniższa tabelka.
Krzyżyk umieszczony na przecięciu wiersza i kolumny oznacza, że dana cyfra nie pasuje do litery. Proszę sprawdzić, pamiętając o unikaniu powtórek oraz o trzech ujawnionych niedubletach, że wszystkie krzyżyki umieszczone są prawidłowo. Najtrudniej wykazać, że h nie może być równe 1 ani 3 (dla h=1 nie będzie miejsca dla drugiej komórki z trójkami, a dla h=3 nie ma gdzie wstawić drugiej komórki jedynkowej; w obu przypadkach powtórzyłyby się niektóre kamienie z trójką lub jedynką). Zatem h=2 lub 5. Ustalenie, ile jest różnych rozwiązań dla h=2, a ile dla h=5, to dobry trening przed pokonywaniem zadań konkursowych. Zapewne jako sprawdzian przyda się informacja, że w sumie jednych i drugich jest 14.
Zadania
1. Wspomniani na początku XIX-wieczni matematycy francuscy zajmowali się kwadrylami wyłącznie symetrycznymi. Dopiero w połowie XX wieku w Holandii, gdzie domino jest rekwizytem niemal kultowym (tu zainicjowano tzw. Dzień Domina), przychylność zyskały także te „brzydsze” układy. Niektóre z nich są zresztą całkiem urokliwe, jak choćby piesek na rys. 11. Ile różnych rozwiązań ma ten 18-kątny niesymetryczny kwadryl?
2. Przed półwieczem miłośnicy dominowych łamigłówek zaczęli tworzyć kwadryle z otworami. Jeden z najciekawszych, bo symetrycznych układów znajduje się na rys. 12. Ile ma różnych rozwiązań?
3. Z trójkowego kompletu domina liczącego 10 kamieni (rys. 13) zrobić kwadryl nie sposób, bo każda liczba występuje w nim pięciokrotnie. Można jednak utworzyć tzw. q-kwadryl. To wielokąt złożony z pięciu komórek, z których każda składa się z czterech różnych liczb – 0, 1, 2 i 3. Zadanie polega na ułożeniu z trójkowego kompletu takiego q-kwadryla, który będzie miał najmniejszą możliwą liczbę kątów.
Rozwiązania prosimy nadsyłać do 28 lutego br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 02/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ą Lindsaya McCrae Rok wśród pingwinów 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. Najmniejszą liczbą, której trwałość iloczynowa Erdösa (TIE) jest większa od jej zwykłej trwałości iloczynowej (TI) jest 205 (TIE=2: 205→10→1; TI=1: 205→0).
2. Najmniejszą liczbą (inną niż 10n) zaczynającą ciąg, który od pewnego wyrazu jest stały, a każdy kolejny wyraz stanowi iloczyn poprzedniego wyrazu i sumy jego cyfr, jest 125 (125*8=1000; ciąg – 125, 1000, 1000, 1000, …). Nieco naciąganą, ale poprawną, jest także odpowiedź „zero”.
3. W ciągu, który zaczyna się jedynką, a każdy kolejny wyraz jest sumą wyrazu poprzedniego i tworzących go cyfr, znajdzie się liczba 31 054 288.
4. Drugim wyrazem ciągu iloczynowego jest 192 (ciągi: iloczynowy 468→192→18→8; sumowy 468→18→9).
5. x=146.
Za poprawne rozwiązanie przynajmniej trzech zadań książkę Davida Attenborough, Podróże na drugi kraniec świata. Dalsze przygody młodego przyrodnika, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Adam Baraniak z Kluczborka, Robert Krawczyk z Obry, Karol Manijak z Krakowa oraz Andrzej Wilczek i Gabriela Zgola z Chorzowa.