Solution of the Tower of Hanoi puzzle

5.1

This is how to transfer n disks from the source peg to the destination

peg using the intermediary peg:

1) First transfer n-1 disks from the source peg to the intermediary peg

2) Then move the bottom (largest) disk from the source peg to the

destination peg

3) Finally, move the n-1 disks from the intermediary peg to the

destination peg.

Let Hn be the number of moves needed for moving n disks.

Then, according to the above strategy,

Hn= Hn-1+1+ Hn-1 = 2Hn-1+1

H0 = 0 = 20-1

H1 = 2(20-1) + 1 = 21-1

H2 = 2(21-1) + 1 = 22-1

H3 = 2(22-1) + 1 = 23-1

…

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

Thus, the monks will need

264-1 = 18,446,744,073,709,551,615

moves. With 1 second per move, this

is over 500 billion years.

The world should survive for quite a while.

Previous slide

Back to first slide

View graphic version