On a question of Leiss regarding the Hanoi Tower problem Academic Article uri icon

abstract

  • The Tower of Hanoi problem is generalized in such a way that the pegs are located at the vertices of a directed graph GG, and moves of disks may be made only along edges of G. Leiss obtained a complete characterization of graphs in which arbitrarily many disks can be moved from the source vertex S to the destination vertex D. Here we consider graphs which do not satisfy this characterization; hence, there is a bound on the number of disks which can be handled. Denote by gngn the maximal such number as G varies over all such graphs with n vertices and S, D vary over the vertices.Answering a question of Leiss [Finite Hanoi problems: How many discs can be handled? Congr. Numer. 44 (1984) 221–229], we prove that gngn grows sub-exponentially fast. Moreover, there exists a constant C such that gn⩽Cn1/2log2n for each n. On the other hand, for each ɛ>0ɛ>0 there exists a constant Cɛ>0Cɛ>0 such that gn⩾Cɛn(1/2-ɛ)log2n for each n.

publication date

  • January 1, 2006