Hacène Belbachir, El-Mehdi Mehiri: Counting elementary moves in the optimal solution of the Tower of Hanoi problem, 127-148

Abstract:

In the Tower of Hanoi puzzle, moving a disc from one peg to another is called an elementary move, in total there are six elementary moves. In this paper, we present the sequence $\varphi_{n}$, and how it can be applied to find the numbers $f_{n}^{ij}(x)$, respectively $g_{n}^{ij}(d,x)$, of moves of one of six types $x$ made by all, respectively each, of the $n$ discs $d$ in the optimal solution for the classical Tower of Hanoi game to transfer a tower from peg $i$ to peg $j$. We establish many results related to $\varphi_{n}$, $f_{n}^{ij}(x)$, and $g_{n}^{ij}(d,x)$, such as explicit and implicit forms, generating functions, and more.

Key Words: Tower of Hanoi, recursion, sequences, enumeration, counting.

2020 Mathematics Subject Classification: 00A08, 05A15, 05A19, 11Y55.

Download the paper in pdf format here.