*Max A. Alekseyev and Toby Berger*

- Published in print:
- 2015
- Published Online:
- October 2017
- ISBN:
- 9780691164038
- eISBN:
- 9781400881338
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691164038.003.0005
- Subject:
- Mathematics, History of Mathematics

This chapter studies solutions of the Tower of Hanoi puzzle and some of its variants with random moves, where each move is chosen uniformly from the set of the valid moves in the current state. The ...
More

This chapter studies solutions of the Tower of Hanoi puzzle and some of its variants with random moves, where each move is chosen uniformly from the set of the valid moves in the current state. The Tower of Hanoi puzzle consists of n disks of distinct sizes distributed across three pegs. At a single move it is permitted to transfer a disk from the top of one peg to the top of another peg, if this results in a valid state, i.e. a particular distribution of the disks across the pegs. The chapter proves the exact formulas for the expected number of random moves to solve the puzzles. It also presents an alternative proof for one of the formulas that couples a theorem about expected commute times of random walks on graphs with the delta-to-wye transformation used in the analysis of three-phase AC systems for electrical power distribution.Less

This chapter studies solutions of the Tower of Hanoi puzzle and some of its variants with random moves, where each move is chosen uniformly from the set of the valid moves in the current state. The Tower of Hanoi puzzle consists of *n* disks of distinct sizes distributed across three pegs. At a single move it is permitted to transfer a disk from the top of one peg to the top of another peg, if this results in a valid state, i.e. a particular distribution of the disks across the pegs. The chapter proves the exact formulas for the expected number of random moves to solve the puzzles. It also presents an alternative proof for one of the formulas that couples a theorem about expected commute times of random walks on graphs with the delta-to-wye transformation used in the analysis of three-phase AC systems for electrical power distribution.