Skąd te sery?
Niezwykła łamigłówka o serach właśnie (the Reve’s puzzle) rozpoczyna książkę The Canterbury Puzzles autorstwa Henry’ego Dudeney’a – angielskiego matematyka i popularyzatora królowej nauk. Oto ta zagadka.
Tytułowe sery zostały ustawione w piramidę jeden na drugim na stołku – od najmniejszego na górze do największego u podstawy; poszczególne bloki różniły się wielkością tak, że nie było dwóch takich samych, a wszystkich bloków było 8.

Obok zajętego stołka zostawiono jeszcze trzy puste. Należy w jak najmniejszej liczbie ruchów przestawić całą piramidę na ostatni pusty stołek. W jednym ruchu można wziąć tylko jeden blok sera, a dodatkowo: nigdy większy kawałek nie może zostać położony na mniejszym. Ile ten optymalny sposób wymaga ruchów? A gdyby początkowa piramida składała się z 21 różnych bloków?
Wieże Hanoi
Przedstawiona łamigłówka w naturalny sposób przywodzi na myśl klasyczną już legendę, według której mnisi w Hanoi mając do dyspozycji 3 słupki – przekładają znajdujące się na nich krążki. Krążki w liczbie 64, także o parami różnych promieniach, początkowo ustawione w piramidę, wszystkie znajdowały się na jednym słupku; pozostałe dwa słupki stały wolne. W jednym ruchu można przestawić tylko jeden krążek i – podobnie jak sery wyżej – nie wolno położyć krążka większego na mniejszym. Gdy mnisi, zgodnie z tymi regułami, przełożą wszystkie krążki na inny słupek, nastąpi… koniec świata!
Dokładny schemat postępowania w tym przypadku jest znany. Aby opisać, w jaki sposób należy przekładać kolejne krążki, spróbujmy podać procedurę dla liczby n = 4 krążków. Dla wygody opisu, poszczególne słupki oznaczmy przez A, B i C. Cel: przełożyć wszystkie krążki z A na B.

Krążek 1 przenosimy na słupek C (1 → C), następnie 2 → B i 1 → B. Po trzech ruchach sytuację pokazuje kolejny rysunek.

Następnie przenosimy krążek 3 na słupek C, po czym – wykorzystując słupek A jako pomocniczy – przenosimy krążki 1 i 2 na krążek 3. To daje nam kolejne 1 + 3 = 4 ruchy. Po wszystkich siedmiu do tej pory wykonanych przeniesieniach, otrzymujemy układ

Teraz przenosimy krążek 4 na docelowy słupek i ponownie wykonujemy siedem ruchów dla krążków 1-2-3. Łącznie należy wykonać więc 7 + 1 + 7 ruchów.
Dla większej liczby, powiedzmy n+1 krążków sytuacja jest podobna. Przenosimy najpierw n górnych krążków na słupek pomocniczy – załóżmy, że wymaganych jest tu xn ruchów – następnie największy ostatni krążek przekładamy na słupek docelowy i ponownie wykonując xn ruchów, układamy wieżę. Stąd mamy zależność:
Bezpośrednio sprawdzamy, że x1 = 1, stąd już łatwo wyznaczać kolejne wartości ciągu (xn). Wynoszą one: 1, 3, 7, 15, 31, 63, 127, 255, … Można zauważyć, że liczby te układają zgodnie ze wzorem




Można teraz próbować oszacować czas potrzebny mnichom na wykonanie swojego zadania. Ponieważ , to przy założeniu, że mnisi wykonują jeden ruch w ciągu sekundy (dzień i noc, bez wytchnienia!), zajmie im to… 584542046090 lat. Wydaje się więc, że o losy świata możemy póki co być spokojni.
Powrót do serów
Dla pełni analogii, sery z wyjściowego zadania będziemy nazywali krążkami, zaś stołki – słupkami. Oznaczmy dodatkowo te ostatnie kolejno przez A, B, C i D. Naszym celem jest obliczenie ile ruchów (i podanie – jakie to mają być ruchy) należy wykonać, aby przenieść 8 (lub ogólnie: n) krążków ze słupka A na słupek B.
Szukaną liczbę przełożeń dla n krążków oznaczmy przez zn. Ponieważ mamy teraz do dyspozycji 3 wolne słupki (a nie 2, jak dla wież z Hanoi), to oczywistym jest iż dla wszystkich liczb naturalnych n.
Aby przełożyć największy krążek na docelowy słupek należy wcześniej jakoś rozmieścić pierwsze n – 1 krążków na pozostałych dwóch słupkach. Przy czym pewną liczbę – powiedzmy – krążków przekładamy z użyciem trzech słupków wolnych, a pozostałe
krążków – z użyciem tylko dwóch wolnych słupków; ten etap, jak wiemy, wymaga wykonania
ruchów. Następnie przekładamy krążek największy (1 ruch) i dalej wykonujemy ruchy powrotne w takiej samej liczbie jak poprzednio ale w odwrotnej kolejności. Liczbę
należy dobrać w taki sposób, aby łączna liczba ruchów była jak najmniejsza. Jeśli przez yn-1 oznaczymy liczbę ruchów potrzebną na przełożenie
krążków w opisany sposób, to powyższe rozumowanie prowadzi do zależności
dla . Należy podać jeszcze wartości początkowe obu ciągów aby uzyskana rekurencja mogła ,,wystartować”:
oraz
. Teraz możemy już wyznaczyć po kilka początkowych wartości ciągów
oraz
.
![]() | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
![]() | 1 | 2 | 4 | 6 | 8 | 12 | 16 | 20 |
![]() | 1 | 3 | 5 | 9 | 13 | 17 | 25 | 33 |
Zauważmy jeszcze, że z równości (1) wynika następująca zależność
Rekurencja ta jest mało wygodna do wyznaczania kolejnych wyrazów ciągu . Zwiększanie indeksu m skutkuje koniecznością wybierania minimum z coraz liczniejszego zbioru. Na szczęście można tu poczynić pewne dodatkowe spostrzeżenie. Ustalmy wskaźnik n > 1 (liczba krążków wynosi więc n + 1) i załóżmy, że powyższe minimum jest realizowane przez liczbę
, tzn.
Oznacza to, że podczas przekładania wierzchnich n krążków, dokładnie r jest przenoszonych przy użyciu 3 pustych słupków pomocniczych, a krążków (bez ostatniego – największego) jest przenoszonych przy użyciu tylko dwóch słupków.
Analogicznie dla początkowej liczby krążków większej o 1 niż poprzednio. Załóżmy, że dokładnie s krążków (spośród przenoszonych wierzchnich (n + 1) sztuk) należy przenieść z użyciem 3 pustych słupków i jest to optymalny wybór:
Wówczas mielibyśmy

