edited by
120 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 $k$ is as chosen in question $41,$ then $R(n) − R(n − 1) = 2^{k−1}.$
edited by

Please log in or register to answer this question.

Related questions