1Department of Mathematics University of Munich 2German Space Operations Center 3Department of Mathematics University of Munich Department for Mathematics and Computer Science University of Maribor 4Department for Mathematics and Computer Science University of Maribor
The electronic journal of combinatorics, Tome 21 (2014) no. 4
In contrast to the widespread interest in the Frame-Stewart conjecture (FSC) about the optimal number of moves in the classical Tower of Hanoi task with more than three pegs, this is the first study of the question of investigating shortest paths in Hanoi graphs $H_p^n$ in a more general setting. Here $p$ stands for the number of pegs and $n$ for the number of discs in the Tower of Hanoi interpretation of these graphs. The analysis depends crucially on the number of largest disc moves (LDMs). The patterns of these LDMs will be coded as binary strings of length $p-1$ assigned to each pair of starting and goal states individually. This will be approached both analytically and numerically. The main theoretical achievement is the existence, at least for all $n\geqslant p(p-2)$, of optimal paths where $p-1$ LDMs are necessary. Numerical results, obtained by an algorithm based on a modified breadth-first search making use of symmetries of the graphs, lead to a couple of conjectures about some cases not covered by our ascertained results. These, in turn, may shed some light on the notoriously open FSC.
Classification :
05C12, 05C38, 68W05
Mots-clés :
Tower of Hanoi, Hanoi graphs, shortest paths, symmetries, breadth-first search
Affiliations des auteurs :
Simon Aumann
1
;
Katharina A.M. Götz
2
;
Andreas M. Hinz
3
;
Ciril Petr
4
1
Department of Mathematics
University of Munich
2
German Space Operations Center
3
Department of Mathematics
University of Munich
Department for Mathematics and Computer Science
University of Maribor
4
Department for Mathematics and Computer Science
University of Maribor
@article{10_37236_4252,
author = {Simon Aumann and Katharina A.M. G\"otz and Andreas M. Hinz and Ciril Petr},
title = {The number of moves of the largest disc in shortest paths on {Hanoi} graphs},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {4},
doi = {10.37236/4252},
zbl = {1305.05059},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4252/}
}
TY - JOUR
AU - Simon Aumann
AU - Katharina A.M. Götz
AU - Andreas M. Hinz
AU - Ciril Petr
TI - The number of moves of the largest disc in shortest paths on Hanoi graphs
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/4252/
DO - 10.37236/4252
ID - 10_37236_4252
ER -
%0 Journal Article
%A Simon Aumann
%A Katharina A.M. Götz
%A Andreas M. Hinz
%A Ciril Petr
%T The number of moves of the largest disc in shortest paths on Hanoi graphs
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4252/
%R 10.37236/4252
%F 10_37236_4252
Simon Aumann; Katharina A.M. Götz; Andreas M. Hinz; Ciril Petr. The number of moves of the largest disc in shortest paths on Hanoi graphs. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4252
