Question

Describe an algorithm to solve the variant of the Towers of Hanoi in as few moves as possible. Prove that your algorithm is correct. Initially, all the n disks are on peg 1, and you need to move the disks to peg 2. You are not allowed to put a bigger disk on top of a smaller disk.

1. Suppose you are only allowed to move disks from peg 0 to peg 1, from peg 1 to peg 2, or from peg 2 to peg 0. Provide an upper bound, as tight as possible, on the nubmer of moves that your algorithm uses.

Answer 1

The Towers of Hanoi problem can be solved recursively as follows. Let Tn be the minimum number of steps needed to move an n-disk tower from one post to another. For example, a bit of experimentation shows that T1 = 1 and T2 = 3. For 3 disks, the solution given above proves that T3 ≤ 7. We can generalize the approach used for 3 disks to the following recursive algorithm for n disks. Step 1. Move the top n − 1 disks from the first post to the third post. This can be done in Tn−1 steps. 1

  | 1 |   | | | | | 1 |

| 2 . | | | | | | . |

| . | | | | | | 2 |

| n | | | ⇒ | n | | n-1 |

Step 2. Move the largest disk from the first post to the to the second post. This requires just 1 step. 1 2 . . . n n−1 ⇒ 1 2 . . . n n−1

|      |   | 1 | |    | 1 | |

|    | | 2 | | | . | |

| . | | | | | 2 | |

| n| | n-1 | ⇒     | n   | n-1 | |

Step 3. Move the n − 1 disks from the third post onto the second post. Again, Tn−1 steps are required. 1 2 . . . n n−1 ⇒ 1 2 . . . n

|      |   | 1 | | | | 1 |

|    | | 2 | | | | 2 |

| . | | | | | | . |

| | n | n-1 | ⇒ |     | | n |

This calculation shows that Tn, the quantity of steps needed to move n plates to an alternate post, is all things considered 2Tn−1 + 1. We can utilize this reality to register upper limits on the quantity of steps required for different quantities of circles:

T3 ≤ 2 · T2 + 1 = 7 T4 ≤ 2 · T3 + 1 ≤ 15

it shows that the quantity of steps required is in any event 2Tn−1 + 1. Since we gave a calculation utilizing precisely that number of steps, we presently have a repeat for Tn, the quantity of moves needed to finish the Tower of Hanoi issue with n plates: T1 = 1 Tn = 2Tn−1 + 1 (for n ≥ 2) We can utilize this repeat to presume that T2 = 3, T3 = 7, T4 = 15, . . ..