Šunić, Zoran Twin towers of Hanoi. (English) Zbl 1254.90287 Eur. J. Comb. 33, No. 7, 1691-1707 (2012). Summary: In the Twin Towers of Hanoi version of the well known Towers of Hanoi Problem there are two coupled sets of pegs. In each move, one chooses a pair of pegs in one of the sets and performs the only possible legal transfer of a disk between the chosen pegs (the smallest disk from one of the pegs is moved to the other peg), but also, simultaneously, between the corresponding pair of pegs in the coupled set (thus the same sequence of moves is always used in both sets). We provide upper and lower bounds on the length of the optimal solutions to problems of the following type. Given an initial and a final position of n disks in each of the coupled sets, what is the smallest number of moves needed to simultaneously obtain the final position from the initial one in each set? Our analysis is based on the use of a group, called Hanoi Towers group, of rooted ternary tree automorphisms, which models the original problem in such a way that the configurations on n disks are the vertices at level n of the tree and the action of the generators of the group represents the three possible moves between the three pegs. The twin version of the problem is analyzed by considering the action of Hanoi Towers group on pairs of vertices.© Elsevier Ltd Cited in 2 Documents MSC: 90C39 Dynamic programming 05A15 Exact enumeration problems, generating functions Keywords:Hanoi Towers group; rooted ternary tree automorphism × Cite Format Result Cite Review PDF Full Text: DOI arXiv References: [1] D’Angeli, D.; Donno, A., Self-similar groups and finite Gelfand pairs, Algebra Discrete Math., 2, 54-69, 2007 · Zbl 1164.20005 [2] Grigorchuk, R.; Nekrashevych, V.; Šunić, Z., Hanoi Towers groups, Oberwolfach Rep., 19, 11-14, 2006 [3] Grigorchuk, R.; Šunić, Z., Self-similarity and branching in group theory, 36-95, URL http://dx.doi.org/10.1017/CBO9780511721212.003 · Zbl 1185.20044 [4] Grigorchuk, R.; Šunić, Z., Schreier spectrum of the Hanoi Towers group on three pegs, 183-198 · Zbl 1170.37008 [5] Grigorchuk, R.; Šunik´, Z., Asymptotic aspects of Schreier graphs and Hanoi Towers groups, C. R. Math. Acad. Sci. Paris, 342, 8, 545-550, 2006, URL http://dx.doi.org/10.1016/j.crma.2006.02.001 · Zbl 1135.20016 [6] Hinz, A. M., The Tower of Hanoi, Enseign. Math., 35, 2, 289-321, 1989, (3–4) · Zbl 0746.05035 [7] Nekrashevych, V. [8] Romik, D., Shortest paths in the Tower of Hanoi graph and finite automata, SIAM J. Disc. Math., 20, 610-622, 2006 · Zbl 1127.68069 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.