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 ≤ k ≤ 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 tk = k(k + 1)/2, the kth triangular number, that is, tk-1
Use Exercise 43 to give an upper bound on the number of moves required to solve the Reve's puzzle for all integers n with 1 ≤ n ≤ 25.