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, 2018. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in HSO for personal use (for details see http://www.universitypressscholarship.com/page/privacy-policy).date: 16 August 2018

Solving the Tower of Hanoi with Random Moves

Solving the Tower of Hanoi with Random Moves

Chapter:
(p.65) 5 Solving the Tower of Hanoi with Random Moves
Source:
The Mathematics of Various Entertaining Subjects
Author(s):

Max A. Alekseyev

Toby Berger

Publisher:
Princeton University Press
DOI:10.23943/princeton/9780691164038.003.0005

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.