Article ID Journal Published Year Pages File Type
4648199 Discrete Mathematics 2012 7 Pages PDF
Abstract
For the multi-peg Tower of Hanoi problem with k≥4 pegs, so far the best solution is obtained by the Stewart's algorithm in [15], based on the following recurrence relation: Sk(n)=min1≤t≤n{2⋅Sk(n−t)+Sk−1(t)},S3(n)=2n−1. In this paper, we generalize this recurrence relation to Gk(n)=min1≤t≤n{pk⋅Gk(n−t)+qk⋅Gk−1(t)},G3(n)=p3⋅G3(n−1)+q3, for two sequences of arbitrary positive integers (pi)i≥3 and (qi)i≥3 and we show that the sequence of differences (Gk(n)−Gk(n−1))n≥1 consists of numbers of the form (∏i=3kqi)⋅(∏i=3kpiαi), with αi≥0 for all i, arranged in nondecreasing order. We also apply this result to analyze recurrence relations for the Tower of Hanoi problems on several graphs.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,