The Tower of Hanoi is a puzzle consisting of a board with three dowels and a col

Question

The Tower of Hanoi is a puzzle consisting of a board with three dowels and a collection of n disks of n different sizes (radii). The disks have holes drilled through their centers so that they can fit on the dowels on the board. Initially, all the disks are on the first dowel and are arranged in size order (from largest on the bottom to the smallest on the top). The object is to move all the disks to another dowel in as few moves as possible. Each move consists of taking the top disk off one of the stacks and placing it on another stack, with the added condition that you may not place a larger disk atop a smaller one. The figure shows how to solve the Tower of Hanoi in three movies when n=2.
Prove: For every positive interger n, the Tower of Hanoi puzzle (with n disks) can be solved in 2^n-1 moves.

Explanation / Answer

We have again an infinite family of statements we wish to prove, one
for each positive integer n. Statement 1 says that the puzzle with 1 disk can
be solved in 21 1 (= 1) move. Statement 2 says that the puzzle with 2 disks
can be solved in 22 1 moves, or 3 moves. Statement n says that the puzzle
with n disks can be solved in 2n 1 moves. The stairway we wish to climb
this time is the stairway that says that these infinitely many statements are
all true. To get off the ground, we must climb the first step, which means
we must show that the puzzle with 1 disk can be solved in 1 move. We can
show this just by doing it, as already discussed. This gets us on the first step
successfully.
Suppose we have reached step k. We wish to show that we can get to step
k + 1. To be on step k means that we are assuming that the puzzle with k
disks can be solved in 2k 1 moves. In saying that we suppose that we have
reached step k, we are saying that we are assuming that statement k is true.
What we must show next is that the puzzle with k + 1 disks can be solved in
2k+1 1 steps on the assumption that the puzzle with k disks can be solved in
2k 1 steps.

For clear diagrammatic expression

http://www.csc.lsu.edu/~karki/DA/06-RecursiveAlgorithms.pdf

http://bilder.buecher.de/zusatz/14/14851/14851065_lese_1.pdf

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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