Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648199 | Discrete Mathematics | 2012 | 7 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jonathan Chappelon, Akihiro Matsuura,