A Note on the Frame-Stewart Conjecture on the Generalized Tower of Hanoi Problem

Authors

  • AAK Majumdar Ritsumeikan Asia-Pacific University, Beppu-shi 874–8577, Japan

DOI:

https://doi.org/10.3329/jbas.v43i1.42236

Keywords:

Multi-peg Tower of Hanoi, Frame-Stewart conjecture, lower bound

Abstract

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

Download data is not yet available.
Abstract
359
PDF
470

Downloads

Published

2019-07-16

How to Cite

Majumdar, A. (2019). A Note on the Frame-Stewart Conjecture on the Generalized Tower of Hanoi Problem. Journal of Bangladesh Academy of Sciences, 43(1), 79–83. https://doi.org/10.3329/jbas.v43i1.42236

Issue

Section

Articles