Solution of the Tower of Hanoi puzzle
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
3) Finally, move the n-1 disks from the intermediary peg to the
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
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.