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

Ratkaisu

Jos n kappaletta kiekkoja siirretään, tarvitaan vähintään s(n) siirtoa. Jos kiekkoja on yhtensä n + 1, voidaan isoin kiekko siirtää vasta, kun n pienempää kiekkoa on siirretty. Kun tämä isoin kiekko on siirretty, tarvitaan vielä s(n) siirtoa, jotta n muuta kiekkoa saadaan siirrettyä isoimman kiekon päälle. Saadaan

s(n + 1) = 2s(n) + 1.

Koska kartion, jossa on vain yksi kiekko (n = 1) siirtämiseen tarvitaan vain yksi siirto, on s(1) = 1. Yhtälöiden

s(n + 1) = 2s(n) + 1 ja s(1) = 1

avulla voidaan rekursiivisestilaskea arvot s(2), s(3), s(4).... Saadaan s(8) = 255.

Jotta s(n) saadaan määritettyä eksplisiittisesti, lasketaan aluksi rekursiivisen kaavan avulla arvoja s(n):lle eri n:n arvoilla.

s(2)= 2 .   1 + 1 = 2 + 1
s(3)= 2(2 + 1) + 1 = 22 + 2 + 1
s(4)= 2(22 + 2 + 1) + 1 = 23 + 22 + 2 + 1

Näiden kolmen yhtälön perusteella päätellään, että

s(n) = 2n-1 + 2n-2 + ... + 22 + 21 + 20.

Tästä yhtälöstä voidaan laskea s(8).

Koska s(n) on geometrisen sarjan (suhdelukuna 2) osasumma, voidaan lauseke sieventää muotoon

s(n) = n sum -1 i=02i = n 1---2-- 1 - 2 = 2n - 1.

Osoitetaan vielä induktiotodistusta käyttäen, että funktion s(n) = 2n - 1 määrittelee rekursiivinen kaava

s(n + 1) = 2s(n) + 1 ja s(1) = 1, missä n = 0, 1, 2, ....

1) s(1) = 21 - 1 = 1 on tosi.
2) Todistetaan induktioaskel: jos s(n) = 2n - 1, niin s(n + 1) = 2n+1 - 1. Rekursiivisesta kaavasta saadaan s(n + 1) = 2s(n) + 1 = 2(2n - 1) + 1 = 2n+1 - 1. Yhtälön toisen yhtäläisyysmerkin kohdalla on oletettu, että s(n) on tosi. Siis s(n + 1) on tosi.

Piilota ratkaisu