Search

Providing the example of a disc whose number of moves performed in some minimal solution for the Tower of Hanoi problem is not a power of 2, we show that the argument given in a paper by Demontis in this journal is false and the method incapable of solving the Frame–Stewart conjecture on the Tower of Hanoi with more than three pegs. [ABSTRACT FROM AUTHOR]

The generalized Tower of Hanoi with p (≥ 3) pegs and n (≥ 1) discs, proposed by Stewart (1939) is well-known. To solve the problem, the scheme followed is : First, move the tower of the topmost i (smallest, consecutive) discs (optimally) to one of the auxiliary pegs in a tower, using the p pegs; next, move the remaining n – i (largest) discs (optimally) to the destination peg in a tower, using the p – 1 pegs available; and finally, transfer the discs on the auxiliary peg to the destination peg (optimally) in a tower. This is the so-called Frame-Stewart conjecture, which remains to be settled. The minimum number of moves under the scheme is denoted by SF(n, p). Chen and Shen (2004) have re-considered the Frame-Stewart conjecture in more detail, and claimed that SF(n, p) is of the order of 2[n(p-2)!]1/(p-2) This paper gives a better lower bound of SF(n, p), which shows that the claim of Chen et al. (2004) is not correct. [ABSTRACT FROM AUTHOR]