wieże Hanoi opiekacz: czy minimalna ilość ruchów dla wieży Hanoi, jeśli możemy przenosić krążki tylko na sąsiednie słupki, przy n krążkach to 3ⁿ−1 ? i jak wykazać że jeśli możemy przenosić krążki tylko na sąsiednie słupki to że wszystkie możliwe ułożenia krążków pojawiają się przy rozwiązaniu?

Jack: wzor jawny : T_n = 2ⁿ − 1 dla n ≥ 0 wzor rekurencyjny : T₀ = 0 T_n=2T_n−1+1 , n>0

opiekacz: możemy przenosić krążki tylko na sąsiednie słupki

Jack: a, ze w ten... to nie pomoge

Jack: wezmy taki przyklad : 3 krazki wtedy mamy 13 ruchow... wiec chyba wzorek 3ⁿ−1 nie pasuje *zakladam ze zaczynamy na krancach, nie na srodku.

opiekacz: moje rozumowanie jeśli to komuś pomoże oznaczmy słupki A, B, C pomyślmy co musimy zrobić żeby przełożyć słupek największy z A na C musimy najpierw przenieść n−1 krążków z A na C a potem największy z A na B potem znowu n−1 z C na A i największy z B na C i n−1 krążków z A na C czyli jeśli przeniesienie n krążków oznaczymy T_n to T_n=3T_n−1+2 oraz T₁=2 baza indukcyjna: T₁=3¹−1 założenie: T_n−1=3ⁿ⁻¹−1 krok indukcyjny: T_n=3T_n−1+2=3ⁿ−1 czy to jest poprawnie?

opiekacz: myślę że jest poprawnie co do drugiej części zadania: istnieje 3ⁿ różnych konfiguracji n krążków skoro minimalna ilość ruchów to 3ⁿ−1 to musimy przejść przez 3ⁿ różnych układów gdyby układy się powtarzały to 3ⁿ−1 nie byłaby minimalną ilością ruchów zatem musimy przejść przez wszystkie