Domino - wąż paton

 
Kamienie domina mają po dwa pola.
Na każdym polu jest pewna liczba 'oczek' (czasem 0).

 

Z kamieni układa się 'węża' tak, by na sąsiadujących polach były te same liczby oczek.
Węża można wydłużać, dostawiając kamienie tylko na początku lub na końcu łańcucha.
Łańcuch z rysunku można wydłużyć, dostawiając jeden kamień z tych, które pozostały. - trzeba go obrócić.

 

W tradycyjnym zestawie domina na każdym polu jest nie więcej niż 6 oczek. W komplecie są wszystkie możliwe kombinacje złożone z par takich pól. Nie ma dwóch jednakowych.
 
Domino - zestaw tradycyjny.
Ma 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 kamieni.
 


 

Można rozważać inne zestawy. Powiemy, że zestaw jest n-kompletny, gdy:
- na poszczególnych polach jest nie więcej niż n oczek,
- w zestawie są wszystkie możliwe takie kamienie,
- nie ma dwóch jednakowych kamieni.
 
Domino - zestaw 4-kompletny.
Ma 5 + 4 + 3 + 2 + 1 = 15 kamieni.
 


 

Domino - zestaw 5-kompletny.
Ma 6 + 5 + 4 + 3 + 2 + 1 = 21 kamieni.
 


 

Domino - zestaw 8-kompletny ma 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 kamieni.
 


 

---

 

 
Powróćmy do domina klasycznego
(czyli do zestawu 6-kompletnego).

 

Gdy w trakcie rozgrywki powstanie wąż taki jak obok, a gracze mają jeszcze kamienie, to sytuacja jest p a t o w a . Żaden z nich nie może dołożyć kamienia, bo żaden z nich nie ma kamienia o polu z trzema oczkami.
Niech taki wąż nazywa się: paton.

To też jest wąż paton. Są w nim wszystkie kamienie o polach z dwoma oczkami.
Jest 7 takich kamieni.

 

Oto przykład najkrótszego patona
(o najmniejszej liczbie kamieni).

Uwaga.   Po udzieleniu powyższej odpowiedzi odczułem lekki niepokój:

skąd wiadomo, że nie ma krótszych patonów? Przecież to, że nie umiem znaleźć krótszego patona, nie oznacza wcale, że krótszego nie ma. Może ktoś bardziej sprytny go znajdzie?
 

Oto przykład patona o najmniejszej liczbie oczek (równej 42).

Uwaga.   Po udzieleniu powyższej odpowiedzi odczułem pewien niepokój:

skąd wiadomo, że nie ma patonów o mniejszej liczbie oczek? Przecież to, że nie umiem znaleźć lepszego, nie oznacza wcale, że takiego nie ma. Może ktoś bardziej sprytny go znajdzie?
 

Oto przykład węża złożonego ze WSZYSTKICH 28 kamieni.
(Zauważ, że taki wąż nie pojawi się w żadnej rozgrywce domina - dlaczego? Może natomiast wystąpić krótszy, bez ostatniego kamienia.)

 

---

 

 
Przejdźmy teraz do zestawu 5-kompletnego.
 
Tu powinno być łatwiej znajdować węże patony. Spróbuj.

Zadziwiające jest, że po wielu, wielu próbach nie udało mi się znaleźć węża zbudowanego ze WSZYSTKICH kamieni zestawu 5-kompletnego. Czy to znaczy, że nie istnieje taki wąż? Przecież to, że nie umiem go znaleźć, nie oznacza wcale, że go nie ma. Może ktoś bardziej sprytny go znajdzie?

Okazuje się, że takiego węża nie ma wcale. Jak to UZASADNIĆ?
To trochę dłuższa historia. Najpierw zbudujemy graf:

 
Na polach kamieni zestawu 5-kompletnego może być: 0, 1, 2, 3, 4 lub 5 oczek. Zaznaczmy 6 punktów (będziemy je nazywać wierzchołkami) i oznaczmy 0, 1, 2, 3, 4, 5.

Połączmy wierzchołki liniami (niekoniecznie prostymi), każdy wierzchołek z każdym - nawet z samym sobą. Takie linie nazywać będziemy krawędziami grafu.
(Ignorujemy przecięcia krawędzi, można myśleć, że to kable, które przechodzą jeden nad drugim.)
 
Na rysunku brakuje kilku krawędzi. 4

A teraz kluczowa sprawa:
krawędzie utożsamiamy z kamieniami domina,
mianowicie krawędź łączącą wierzchołki 5 i 2 utożsamiamy z kamieniem .
Analogicznie w przypadku innych krawędzi.
(Na rysunku podpisano tylko niektóre krawędzie.)
Na rysunku brakuje kilku krawędzi. 4

 

Wężom odpowiadają wędrówki po grafie, a dokładniej po jego krawędziach - po każdej co najwyżej jeden raz:
 

 

 

Zauważ, że w trakcie wędrówki po grafie, w wierzchołkach (z wyjątkiem startu i mety - jeśli są różne) przechodzimy przez parzystą liczbę 'odnóg' = fragmentów krawędzi wychodzących z wierzchołka (to na żółtym tle).
Bo dochodząc, zaraz wychodzimy.
Na rysunku: w wędrówce 3-1-5-2-2-4-5 wykorzystujemy:
- 4 odnogi wierzchołka 2,
- 2 odnogi wierzchołka 4,
- 2 odnogi wierzchołka 1.

A teraz NAJWAŻNIEJSZE:
 
w grafie odpowiadającym zestawowi 5-kompletnemu, każdy wierzchołek ma SIEDEM odnóg.
 
Zatem nie ma wędrówki po WSZYSTKICH krawędziach tego grafu.
 
Zatem nie ma węża złożonego ze WSZYSTKICH kamieni zestawu 5-kompletnego.
 

Uwaga. Mamy wreszcie rozumowanie pokazujące, że czegoś nie ma, że czegoś nie można znaleźć. Nawet jeśli szukał będzie ktoś bardzo sprytny.
 

Powyższe rozumowanie jest fragmentem dowodu twierdzenia Eulera:

Graf spójny jest jednobieżny
(tzn. można obejść wszystkie jego krawędzie, przechodząc przez każdą dokładnie jeden raz)

wtedy i tylko wtedy, gdy każdy wierzchołek ma stopień parzysty (tzn. ma parzystą liczbę odnóg)
albo
dokładnie dwa wierzchołki mają stopień nieparzysty.
 

 

---

 

Na koniec zobaczmy, jak w krótszej notacji opisać węża złożonego ze wszystkich kamieni tradycyjnego domina 6-kompletnego:
 

0-0-1-1-2-2-3-3-4-4-5-5-6-6-0-2-4-6-1-3-5-0-3-6-2-5-1-4-0