Halfway through the process of moving the n washers, the largest washer lies alone on its original peg, and the chosen final peg is free to receive it. The other n-1 washers are distributed among the h= k-2 auxiliary pegs, and we may assume that the n1 largest of these washers are on the first peg, the next n2 on the next, etc.* and the nh smallest ones on the last. In some cases the solution requiring the least number of moves is unique; in others it is not. We shall describe one of these" most economical" methods, understanding that others may be equally short but not shorter. In the trivial case h> n-1, only nI auxiliary pegs need be used, so the number of moves required is the same as for h= n-1. Otherwise, if the smallest washer is to cover nh-1 others at this stage, it is a most economical method to have these be the smallest washers, so that these in turn do not block other pegs. Similarly in each of the h auxiliary piles the washers may be arranged in consecutive order according to size. It is also a most economical method to have the larger piles contain the smaller washers, since the latter have access to more pegs at the time of their transfer. Hence (1) n= I+ nl+ n2+*+ nh, 1< nl_ n2_<< nh.

To complete the transfer we move the largest washer to its destination, then move the n, next largest washers onto it using one auxiliary peg, then the next n2 using two auxiliary pegs, etc..., and finally move the nh smallest washers using h auxiliary pegs. The minimum number of moves, m (h, n), required to move n washers using hI= k-2 auxiliary pegs is thus given by