Exercises $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 $1kn.$ 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\frac{k+1}{2},$ the $k$ th triangular number, that is$,t_{k-1}.$ The long$-$standing conjecture, known $as$ Frame's conjecture, that this algorithm uses the fewest number $of$ moves required $to$ solve the puzzle, was proved $by$ Thierry Bousch $in2014.$

$38.$ Show that the Reve's puzzle with three disks can $be$ solved using five, and $no$ fewer, moves.

$39.$