Wieże Hanoi… z sera?

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.

Wyjściowe ułożenie serów.

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.

Wieże z Hanoi z n=4 krążkami…

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

… po 3 ruchach…

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

… i po 7 ruchach.

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ść:

    \[x_{n+1}=2x_n+1\qquad\text{dla}\qquad n=1,2,3,\ldots\]

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

    \[x_n=2^n-1\qquad\text{dla wszystkich $n$ naturalnych.}\]

Dowód tego faktu opiera się na równości

    \[2\cdot(2^n-1)+1=2\cdot 2^n-2+1=2^{n+1}-1,\]

która potwierdza, że zależność, jaką spełniają kolejne wyrazy naszego ciągu spełniają też liczby postaci 2^n-1. A ponieważ dodatkowo x_1=1=2^1-1, więc oba ciągi: (x_n) oraz (2^n-1) są tożsame.

Można teraz próbować oszacować czas potrzebny mnichom na wykonanie swojego zadania. Ponieważ 2^{64}-1=18446744073709551615, 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ż z_n\leqslant x_n=2^n-1 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 k – krążków przekładamy z użyciem trzech słupków wolnych, a pozostałe (n-1)-k krążków – z użyciem tylko dwóch wolnych słupków; ten etap, jak wiemy, wymaga wykonania x_{n-1-k}=2^{n-1-k}-1 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ę k 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 (n-1) krążków w opisany sposób, to powyższe rozumowanie prowadzi do zależności

    \[z_n=y_{n-1}+1+y_{n-1},\qquad\quad y_{n-1}=\min\limits_{0\leqslant k\leqslant n-1}\{z_k+x_{n-1-k}\}\eqno{(1)}\]

dla n\in\mathbf{N}. Należy podać jeszcze wartości początkowe obu ciągów aby uzyskana rekurencja mogła ,,wystartować”: z_0=0 oraz y_0=0. Teraz możemy już wyznaczyć po kilka początkowych wartości ciągów (z_n) oraz (y_n).

n12345678
y_n12468121620
z_n135913172533

Zauważmy jeszcze, że z równości (1) wynika następująca zależność

    \[y_{n}=\min\limits_{0<k\leqslant n}\{2y_{k-1}+2^{n-k}\},\qquad n=1,2,3,\ldots.\]

Rekurencja ta jest mało wygodna do wyznaczania kolejnych wyrazów ciągu (y_n). 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ę k=r=r(n), tzn.

    \[y_n=2y_{r-1}+2^{n-r}.\]

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 n-r 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:

    \[y_{n+1}=2y_{s-1}+2^{n+1-s}.\]

Wówczas mielibyśmy

    \begin{eqnarray*} 2y_{s-1}+2^{n+1-s}&=&y_{n+1}=\min\limits_{0<k\leqslant n+1}\{2y_{k-1}+2^{n+1-k}\}\leqslant\\\nonumber  &\leqslant& 2y_{r-1}+2^{n+1-r}=2y_{r-1}+2^{n-r}+2^{n-r}=\nonumber\\ &=&y_{n}+2^{n-r}=\min\limits_{0<k\leqslant n}\{2y_{k-1}+2^{n-k}\}+2^{n-r}\leqslant\nonumber\\ &\leqslant& 2y_{s-1}+2^{n-s}+2^{n-r}.\nonumber \end{eqnarray*}

Porównując skrajne wyrazy po obu stronach nierówności, otrzymamy 2^{n+1-s}\leqslant 2^{n-s}+2^{n-r}, czyli s\geqslant r.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *