Let us suppose that we are trying to solve a Towers of Hanoi puzzle [1] that has

Question

Let us suppose that we are trying to solve a Towers of Hanoi puzzle [1] that has n disks. To keep track of our moves, label the top disk 0, the next disk 1 and so forth, so that the largest disk is labeled n - 1. For example, suppose n=3. At the beginning of the puzzle, disk 0 will be on top of disk 1, which rests on top of disk 2, all of which are stacked on the left-most peg. As you solve the puzzle, record the number of the disk that you move. With n=3, first move disk 0, then disk 1, disk 0 (onto disk 1), disk 2, disk 0 (onto the empty peg), disk 1 and finally disk 0. In short, the disks moved are 0102010. On the cube below, note that there are three directions in which we can travel: left/right, front/back, up/down. Also notice that if we start at any vertex, we can travel in each of the three listed directions. Start at the vertex v. Now, read your solution to the 3-disk puzzle and create a path using the following rules. Each time you encounter a 0, move left or right. Each time you encounter a 1, move forwards or backwards. Each time you encounter a 2, (you guessed it) move up or down. Question: What kind of path is the resulting path? Explain in your own words why the solution to this problem gives this kind of path.

Explanation / Answer

we see that The Towers of Hanoi puzzle is easy when n = 1. We may just move the singledisk to the far peg. Suppose by induction that we know we can move k disks from one peg to another. If we have a tower of k + 1 disks, then we begin by moving the top k disks to the middle peg. Then we can move the remaining largest disk to the farthest peg. Then we can move the k disks from the center peg over the to farthest peg. We have just shown by induction that the Towers of Hanoi puzzle can be solved for any number of disks. therefore between every pair of arbitrary distributions of disks there are one or two different shortest paths. From every arbitrary distribution of disks, there are one or two different longest non selfcrossing paths to move all disks to one of the three pegs. Between every pair of arbitrary distributions of disks there are one or two different longest non selfcrossing paths.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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