A statistical analysis of the towers of hanoi problem

Abstract

The Towers of Hanoi problem is analyzed with the aid of Hanoi graphs depicting legal configurations (i. e. arrangements of the disks on the pegs) and the transitions among them. Specifically, the mean and the standard deviation of the minimum numbers of moves required to change an arbitrary initial configuration into an arbitrary final configuration are computed, and are shown to be approximately 0.52655 · 2 ⁿ and 0.25025 · 2 ⁿ respectively for n disks.

Keywords:

• Towers of Hanoi
• Hanoi graph

C.R. Categories:

• F.2.2