3. Let n be a positive integer. Suppose that there are three pegs and on one of

Question

3. Let n be a positive integer. Suppose that there are three pegs and on one of themn rings are stacked, with each ring being smaller in diameter than the one below 1t. We want to transfer all the rings to another peg according to the following rules: (a) only one ring may be moved at a time, (b) a ring may be moved to any peg but may never be placed on top of a smaller ring. Note that the second rule implies that the final order on the new peg will be the same as their original order on the first peg Prove that the game can be completed in 2" - 1 moves but cannot be completed in fewer moves.

Explanation / Answer

This is similar to classic tower of hanoi problem.

1. transfer the top n 1 smaller disks to the middle peg (requiring Tn1 moves)

2. move the largest disk to the third peg (requiring 1 move)

3. transfer the n 1 smallest onto the largest disk (requiring Tn1 moves).

Thus we can transfer n disks (n > 0) in at most 2Tn1 + 1 moves : Tn 2Tn1 + 1, for n > 0.

That is, 2Tn1 + 1 moves suffice. Are 2Tn1 + 1 moves necessary? At some point we must move the largest disk to the third peg. When we do, the n 1 smallest must be on the middle peg, and it has taken at least Tn1 moves. At least 1 move is required to move the largest disk. After moving the largest disk, we again require at least Tn1 moves. Hence Tn 2Tn1 + 1, for n > 0.

So

T0 = 0 (boundary value)

Tn = 2Tn1 + 1 for n > 0.

Adding 1 to both sides of the equations T0 = 0 and Tn = 2Tn1 + 1 for n > 0 and letting un = Tn + 1, we get u0 = 1 and un = 2un1 for n > 0. Hence un = 2n . Thus Tn = 2n 1, for n 0.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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