Jump to ContentJump to Main Navigation
The Mathematics of Various Entertaining SubjectsResearch in Recreational Math$
Users without a subscription are not able to see the full content.

Jennifer Beineke and Jason Rosenhouse

Print publication date: 2015

Print ISBN-13: 9780691164038

Published to Princeton Scholarship Online: October 2017

DOI: 10.23943/princeton/9780691164038.001.0001

Show Summary Details
Page of

PRINTED FROM PRINCETON SCHOLARSHIP ONLINE (www.princeton.universitypressscholarship.com). (c) Copyright Princeton University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in PRSO for personal use.date: 19 September 2021

Solving the Tower of Hanoi with Random Moves

Solving the Tower of Hanoi with Random Moves

(p.65) 5 Solving the Tower of Hanoi with Random Moves
The Mathematics of Various Entertaining Subjects

Max A. Alekseyev

Toby Berger

Princeton University Press

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.

Keywords:   Tower of Hanoi, random moves, random walks, delta-to-wye transformation, electrical power distribution

Princeton Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us.