A Note on the Frame-Stewart Conjecture on the Generalized Tower of Hanoi Problem
DOI:
https://doi.org/10.3329/jbas.v43i1.42236Keywords:
Multi-peg Tower of Hanoi, Frame-Stewart conjecture, lower boundAbstract
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.
Journal of Bangladesh Academy of Sciences, Vol. 43, No. 1, 79-83, 2019
Downloads
5
8