138 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 the Reve’s puzzle with four disks can be solved using nine, and no fewer, moves

Please log in or register to answer this question.

Related questions