The Towers of Hanoi

How Hard Is It?

One Disk

Easiest case. One move or 2^1 - 1.

Two Disks

2^1 - 1 First use the one disk solution to get the top disk to the center,
1 move the bottom disk to final location,
2^1 - 1 use the one disk solution to get the top disk to the right.

2^2 - 1 Is the sum.

Three Disks

2^2 - 1 First use the two disk solution to get the top disks to the center,
1 move the bottom disk to final location,
2^2 - 1 use the two disk solution to get the top disks to the right.

2^3 - 1 Is the sum.

Non-Math, non-CS majors can simply take the following at face value. Majors will be able to prove the following by induction someday.

N Disks

2^(N-1) - 1 First use the N-1 disk solution to get the top disks to the center,
1 move the bottom disk to final location,
2^(N-1) - 1 use the N-1 disk solution to get the top disks to the right.

2^N - 1 Is the sum.

Is 60 moves hard?

A table of approximate number of moves:

Disks	Moves (est)	Moves (act)
10	1,000		1,023
20	1,000,000	1,048,575
30	1,000,000,000	1,073,741,823
40	1,000,000,000,000
50	1,000,000,000,000,000
60	1,000,000,000,000,000,000

For fun, assume that your computer averaged one microsecond (0.000001) for each move. It would take 34,865 years to move all the disks using this solution.