Hanoin torni

Hanoin torni-nimellä tunnettuun lautapeliin kuuluu kahdeksan erikokoista kiekkoa, joissa kaikissa on reikä keskellä sekä lauta, johon on kiinnitetty kolme tappia. Aluksi kiekot ovat yhdessä tapissa järjestettyinä koon mukaan siten, että niistä muodostuu kartio. Suurin kiekko on alimmaisena.

Pelissä kartio pitää siirtää toiseen tappiin samanlaiseksi kartioksi. Vain yhden kiekon saa siirtää kerrallaan. Pienemmän kiekon päälle ei saa koskaan panna isompaa kiekkoa. Kuinka monta siirtoa pitää tehdä, jotta kartio saadaan rakennettua toiseen tappiin?
PICT

Vihje 1

Mieti ensin tapaukset, joissa kiekkoja on vain 1, 2 ja 3. Kun kiekkoja on neljä, pitää kolme ylimmäistä kiekkoa siirtää ensin, jotta neljäs kiekko voidaan siirtää. Tämän jälkeen kolme kiekkoa on vielä siirrettävä neljännen päälle.

Laske n + 1 kiekon siirtämiseen tarvittavien siirtojen määrä, kun n kiekon siirtämiseen tarvittavien siirtojen määrä tiedetään.

Vihje 2

Kun kiekkoja on (n + 1) kappaletta, voidaan alimmaista siirtää vasta, kun n ylimmäistä on siirretty. Näiden n ylimmäisen kiekon siirtämiseen tarvitaan s(n) siirtoa. Vasta tämän jälkeen voidaan siirtää (n + 1). kiekko. Muut kiekot on vielä siirrettävä suurimman kiekon päälle eli tarvitaan vielä s(n) siirtoa.

Vihje 3/3 Ratkaisu Vastaus