Problem of the Week-5: Towers of Hanoi

You may be familiar with the puzzle known as the Towers of Hanoi. There are 3 posts and n disks of distinct radii each with a hole in the middle. At the start, the disks are stacked at one of the posts (say post 1) in order of decreasing size, with disk of smallest radius on top. The problem is transfer the disks from post 1 to another one (say post 2) by moving one disk at a time from one post to another and never putting a larger disk on a smaller one.

(If you have not seen this puzzle before, show first that the number of moves required for this task is 2^n-1)

This week's problem asks you to consider a version of this puzzle with 4 posts.

What is the fewest number of moves required to transfer 8 disks from post one to another if you have 4 posts to work with.

(Hint: You may use the result from the original puzzle)

Justify your answer.

Posted: 3/22/04

Submit your answers (by e-mail or hard copy) before 4 pm on 4/02/04 to Noah Aydin.

Mathematics Dept.