Home Strefa Ucznia Strefa Nauczyciela Strefa Otwarta Sklep Matematyczny



Materiały » Lekcje




Wieża Hanoi


WSTĘP

Wieżę Hanoi wymyślił francuski matematyk Édouard Lucas dla zabawy w 1883 roku. Édouard Lucas jest również autorem wzoru na n-ty wyraz ciągu Fibonacciego.

ZASADY GRY

Wieża składa się z trzech słupków: początkowy, końcowy, pomocniczy (tzw.bufor). Naszym zadaniem jest przenieść wszystkie krążki z początkowego słupka na końcowy z zachowaniem tego samego kształtu wieży, pomagając sobie słupkiem pomocniczym i stosując następujące zasady:

  • Można układać tylko mniejszy na większy krążek
  • Można przekładać tylko jeden krążek jednocześnie
  • Można brać tylko krążek z samej góry

Na początek spróbuj rozwiązać łamigłówkę samodzielnie, wybierając różną ilość krążków.

GRA - WIEŻA HANOI

Jeżeli masz problem z ułożeniem krążków, możesz obejrzeć symulację rozwiązania dla poszczególnych ilości krążków, wybierając odpowiednią opcję w grze.

WZÓR REKURENCYJNY

WZÓR REKURENCYJNY na obliczenie ilości potrzebnych ruchów w zależności od ilości krążków: f(n)=2f(n-1)+1

Uzasadnienie wzoru rekurencyjnego:

WZÓR OGÓLNY: f(n)=2^n-1


Dowód indukcyjny z wykorzystaniem wzoru rekurencyjnego.

Twierdzenie: f(n)=2^n-1

Dowód:

Sprawdzenie dla n=1     f(1) = 2^1-1=1

Istotnie tyle trzeba ruchów do przeniesienia jednopiętrowej wieży, zatem twierdzenie jest prawdziwe dla n=1

  • Założenie indukcyjne. Zakładamy, że twierdzenie jest prawdziwe dla pewnej dodatniej liczby naturalnej k

f(k) = 2^k-1    k\in N_+

  • Teza indukcyjna. Twierdzenie dla  k+1

f(k+1) = 2^{(k+1)}-1

  • Krok indukcyjny. Pokażemy, że jeśli twierdzenie jest prawdziwe dla k, to jest prawdziwe także dla k+1

Przekształcając wzór rekurencyjny f(n) = 2f(n-1)+1 dla n=m+1 otrzymujemy f(m+1) = 2f(m)+1

Podstawiając na miejsce f(m) wzór z założenia indukcyjnego otrzymujemy:

f(m+1) = 2(2^m-1)+1 = 2^{m+1}-2+1 = 2^{m+1}-1

Otrzymaliśmy tezę indukcyjną, więc wzór jest poprawny.


Wyprowadzenie wzoru ogólnego:

f(n) = 2f(n-1) + 1   \;\;\;\ |+1

f(n) + 1 = 2f(n-1) + 2 = 2(f(n-1) + 1)

Niech: g(n) = f(n) + 1

Wtedy: g(n) = f(n) + 1 = 2(f(n-1) + 1) = 2g(n-1)

g(n) = 2g(n-1)

Czyli otrzymaliśmy równanie określające ciąg geometryczny.

Wiedząc, że f(1) = 1, to g(1) = f(1) + 1 = 1 + 1 = 2
g(2) = 2g(1) = 2\cdot 2 = 4
g(3) = 8

g(n) = 2^n

Po powrocie do f(n) otrzymujemy: f(n) = g(n)-1= 2^n- 1

 LEGENDA

Jak głosi stara hinduska legenda, przy stworzeniu świata, w jego środku, pod dachem świątyni, umieszczone zostały trzy diamentowe pałeczki. Na jedną z nich nałożonych było 64 złotych krążków o zmniejszających się średnicach tworząc złoty stożek. Dzień i noc, zmieniając się bezustannie, mnisi przekładali krążki na trzecią pałeczkę. Musieli jednak zachować pewne zasady. Mogli posiłkować się drugą pałeczką, jednakże nie wolno było im przenosić więcej niż jeden krążek i umieszczać większego na mniejszym. Gdy wykonają swoje zadanie - nastąpi koniec świata!

OBLICZMY WIĘC DATĘ KOŃCA ŚWIATA ZGODNIE Z LEGENDĄ

Podstawiając do wzoru otrzymujemy: 2^{64}-1=18 446 744 073 709 551 615 (blisko 18 i pół tryliona) sekund, co daje około 584 542 mld lat, a wszechświat ma około 13,7 mld lat.









Adres
Mińsk Mazowiecki Pl. Kilińskiego 7
Kontakt
T. +48 51-81118-51
matematykainnegowymiaru@elitmat.pl
GG: 10158257