in Combinatory edited by
227 views
0 votes
0 votes
Question $38–45$ involve the Reve’s puzzle, the variation of the Tower of Hanoi puzzle with four pegs and $n$ disks. Before presenting these exercises, we describe the Frame–Stewart algorithm for moving the disks from peg $1$ to peg $4$ so that no disk is ever on top of a smaller one. This algorithm, given the number of disks $n$ as input, depends on a choice of an integer $k$ with $1 \leq k \leq n.$ When there is only one disk, move it from peg $1$ to peg $4$ and stop. For $n > 1,$ the algorithm proceeds recursively, using these three steps. Recursively move the stack of the $n − k$ smallest disks from peg $1$ to peg $2,$ using all four pegs. Next move the stack of the $k$ largest disks from peg $1$ to peg $4,$ using the three-peg algorithm from the Tower of Hanoi puzzle without using the peg holding the $n − k$ smallest disks. Finally, recursively move the smallest $n − k$ disks to peg $4,$ using all four pegs. Frame and Stewart showed that to produce the fewest moves using their algorithm, $k$ should be chosen to be the smallest integer such that $n$ does not exceed $t_{k} = k(k + 1)/2,$ the $k^{\text{th}}$ triangular number, that is, $t_{k−1} < n \leq t_{k}.$ The unsettled conjecture, known as $\textbf{Frame’s conjecture,}$ is that this algorithm uses the fewest number of moves required to solve the puzzle, no matter how the disks are moved.

Show that if $R(n)$ is the number of moves used by the Frame–Stewart algorithm to solve the Reve’s puzzle with $n$ disks, where $k$ is chosen to be the smallest integer with $n \leq k(k + 1)/2,$ then $R(n)$ satisfies the recurrence relation $R(n) = 2R(n − k) + 2^{k} − 1,$ with $R(0) = 0\:\text{and}\: R(1) = 1.$
in Combinatory edited by
by
227 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true