Tornet i Hanoi

Sägen

I det stora templet i Benares, under kupolen som markerar världens mittpunkt, ligger en platta av mässing. I plattan är tre diamantpelare fästade. På en av pelarna placerade Gud vid världens skapelse sextiofyra skivor av rent guld. Den största skivan vilar på mässingsplattan och på denna ligger skivor av mindre och mindre storlek. Detta är guden Brahmas torn. Dag och natt utan uppehåll flyttar munkarna i templet skivor från den ena pelaren till den andra. Eftersom skivorna är ömtåliga, får ingen skiva läggas ovanpå en mindre skiva. Då munkarna flyttat alla skivor, så att de ligger på den pelare, som finns längst till höger, kommer tornet och templet att förvandlas till stoft, och med ett väldigt dån kommer världen att gå under.


Matematiska beräkningar
Med tre skivor åtgår det 7 förflyttningar (se figur)

Med 4 skivor åtgår det 15 förflyttningar och med 5 skivor 31 förflyttningar.
Generellt kan antalet förflyttningar skrivas 2n - 1, där n är antalet skivor.
Anm. 1:
För att flytta n st skivor måste man först placera (n - 1) st skivor på den mellersta pelaren och därefter den största skivan på pelaren längst till höger. Slutligen flyttas (n - 1) st skivor till pelaren längst till höger. Formelmässigt kan det beskrivas så här: (2n-1 -1)
+ 1 + (2n-1 -1) = 2 * 2n-1 - 1 = 2n -1.
Anm. 2: Vid udda antal skivor börjar man med att flytta den minsta skivan till den pelare, som ligger längst till höger. Vid jämnt antal skivor startar man istället med att flytta den minsta skivan till den mellersta pelaren.

När går världen under?
Vi antar att munkarna flyttar en skiva i sekunden.
Det ger följande beräkning:
Antal förflyttningar: 264 - 1
» 1,84 * 1019
Antal år: 1,84 * 1019 /(60*60*24*365) » 5,8 * 1011
dvs. närmare 600 miljarder år!

Det finns med andra ord inte någon anledning att oroa sig.