Question

Consider the following variants of the Towers of Hanoi. For each of variant, describe an algorithm to solve it 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. In all the following variants, you are not allowed to put a bigger disk on top of a smaller disk. Consider the disappearing Tower of Hanoi puzzle where the largest remaining disk will disappear if there is nothing on top of it. The goal here is to get all the disks to disappear and be left with three empty pegs (in as few moves as possible). Provide an upper bound, as tight as possible, on the number of moves your algorithm uses.

For reference, the original Hanoi function is written as so:

Hanoi(n, src, dest, temp){

if(n > 0) {

   Hanoi(n-1, src, temp, dest)

   Move disk n from src to dest

   Hanoi(n − 1, temp, dest, src)

}

}

Answer 1

In this variation, if the largest remaining disk becomes free with nothing on top, it disappears.

The goal is to make the whole tower disappear. For instance, an = 0 when n ≤ 1 (with either no disks or one free disk). With two disks, once the smallest is moved, the largest disk becomes free and disappears, so the smallest, being now the largest remaining free disk, will follow, resulting in a2 = 1. Similarly, it is not hard to see that a3 = 2.

The optimal solution can be derived as follows:

To free the largest disk, one must move the second largest, which as illustrated for the case of n = 2, will also disappear. Observe that no disks can disappear prior to the largest. Therefore, we first transfer n−2 disks to some peg, then move the second largest disk to another, hence freeing two disks for two disappearing at once, and finally repeat the solution for the remaining n − 2 disks.

Disappearing(n, x, y, z)

if n > 1

then Hanoi(n − 2, x, z, y)

Move(1, x, z)

disks n and n − 1 disappear

Disappearing(n − 2, y, x, z)