The Mathematical Garden

Example: The Towers of Hanoi

According to legend, a certain Buddhist temple contains three thin diamond poles on one of which, at the of creation, God placed 64 golden disks that decrease in size as they rise from the base. The priests of the temple work unceasingly to transfer all the disks one by one from the first pole to one of the others, but they must never place a larger disk on top of a smaller one. As soon as they have completed their task, "tower, temple and Brahmins alike will crumble into dust, with a thunderclap the world will vanish".

The question is this: Assuming the priests work as efficiently as possible, how long will it be from the time of creation until the end of the world ?

Solution:

An elegant and efficient way to solve this problem is to think recursively. Suppose that you have found the most efficient way possible to transfer a tower of k-1 disks from one pole to another, obeying the restriction that you never place a larger disk on top of a smaller one. What is the most efficient way to move a tower of k disks from one pole to another ? Assume that pole A is the initial pole and pole C is the target pole.

• Step 1 is to move the top k-1 disks from pole A to pole B.

• Step 2 is to move the bottom disk from pole A to pole C.

• Step 3 is to move the top k-1 disks from pole B to pole C.

To see that this sequence of moves is most efficient, observe that to move the bottom disk of a stack of k disks from one pole to another, you must first move the top k-1 disks to a third pole to get them out of the way. Thus moving the stack of k disks from pole A to pole C requires at least two transfers of the top k-1 disks, one to move them off the bottom disk to free the disk so it can be moved and another to move them back on top of the bottom disk after the bottom disk has been moved to pole C. If the bottom disk were not moved directly from pole A to pole C but were moved to pole B first, at least two additional transfers of the top k-1 disks would be necessary, one to move them from pole A to pole C so that the bottom disk could be moved from pole A to pole B and another to move them off pole C so that the bottom disk could be moved onto pole C. This would increase the total number of moves and result in a less efficient transfer.

Thus the minimum sequence of moves can be described as follows:

é ê ê ê ê ê ë the minimum number of moves needed to transfer a tower of k disks from pole A to pole C ù ú ú ú ú ú û = é ê ê ê ê ê ë the minimum number of moves needed to transfer a tower of k-1 disks from pole A to pole B ù ú ú ú ú ú û + é ê ê ê ê ê ë the minimum number of moves needed to transfer the bottom disk from pole A to pole B ù ú ú ú ú ú û + é ê ê ê ê ê ë the minimum number of moves needed to transfer a tower of k-1 disks from pole B to pole C ù ú ú ú ú ú û .

For each integer n ³ 1, let M_n be the minimum number of moves needed to move a tower of n disks from one pole to another. Note that the numbers M_n are independent of the labeling of the poles; it takes the same minimum number of moves from transfer n disks from pole A to pole C as to transfer n disks from pole A to pole B, for example. Therefore, we have

Mk = Mk-1 + 1 + Mk-1 = 2 Mk-1 + 1

for all integers k ³ 2. (recurrence relation) The initial condition M₁ is equal to the the minimum number of moves needed to move a tower of one disk from one pole to another. It should be equal to 1.

The time from the beginning of creation to the end of the world would be M₆₄ seconds Using a calculator or a computer, the approximate result is

1.844674 ×109  seconds » 5.84542 ×1011   years » 584.5  billion   years.

Surprisingly, this figure is close to scientific estimates of the life of the universe.