Home > Riddles > The tower of Hanoi
Few pieces unite mechanism and growth so well. Each movement is simple; The amazing thing appears when that simplicity is repeated until an unexpectedly large quantity is produced.
There are three rods and a tower of 7 discs of different sizes, stacked from largest to smallest on one of them. You can only move one disk at a time and you can never place a large disk on top of a small one.
What is the minimum number of movements necessary to move the entire tower to another rod?
Answer: 127 movements are needed. To move a tower of $n$ discs, the larger disc cannot be moved until the upper $n-1$ discs are on the auxiliary rod. That first block requires $T(n-1)$ movements. The larger disk is then moved only once. Finally, the $n-1$ discs must be moved from the auxiliary rod to the destination rod, which requires further $T(n-1)$ movements. Therefore: $$
T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1.
$$ As $T(1)=1$, you get: $$
T(n)=2^n-1.
$$ For 7 discs: $$
T(7)=2^7-1=128-1=127.
$$ So the minimum is 127 moves.
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.