Suppose you have three vertical posts and a stack of n disks, initially placed o

Question

Suppose you have three vertical posts and a stack of n disks, initially placed on one post with the largest disk on the bottom and each disk above it smaller than the disk below. A legal move involves taking the top disk from one post and moving it so that it becomes the top disk on another post, but every move must place a disk either on an empty post, or on top of a disk larger than itself. Show that for every n there is a sequence of moves that will terminate with all the disks on a post different from the original one. (Hint: Use induction on n.)

Explanation / Answer

We proceed by induction (what else?). The base case, with with only one disk to play with, is trivial: move it to another post and you are done. Suppose then that it is possible to move n disks to another post, according to the rules. Then if you instead start with n + 1 disks, leave the bottom, largest, disk untouched and play with the top n disks. By assumption we can now move these top n disks to a different post (for the post with the largest disk kept on it is still always usable, because that any other disk can be placed on it). Then you move the so-far-untouched largest disk to the remaining empty post. Now keep that disk fixed, but off you go again, moving the n remaining disks so that they end up on top of the largest disk. We have shown, then, that we can legally move one disk, and that if we can legally move n disks we can legally move n+ 1 disks. Hence we can legally move any number of disks.

The described method requires 2n 1 steps to move n disks. That’s trivial for the case n = 1. Suppose it is true for some n that it takes 2n 1 steps to move n disks. Then on our method, to move n + 1 disks, we will need 2n 1 steps to move the top n disks to an empty post, 1 step to shift the largest disk, and then another 2n 1 steps to move the top n disks again. That sums to 2n+1 1 steps. So by induction, the claim that it always takes 2n 1 steps follows.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.