You have three small poles and five hoops - XS, S, M, L, XL (as in extra small, small, medium, large and extra large). They are placed on pole 1 in order, with largest at the bottom.

You can move one hoop at a time, and the hoops you are not moving have to be on a pole. You also cannot place a hoop on top of a smaller one. How can you move the hoops so that they are in the same order as they are now, but on pole 3?

The strategy for moving n hoops to pole 3 is first to move n-1 hoops to pole 2, then move the nth hoop to pole 3 and then move the other n-1 hoops onto pole 3. Defining the problem this way is known as recursion. Eventually you have broken it down into the problem of moving just 1 hoop. It's apparent that the target of the bottom (nth) hoop is to be pole 3; the target of hoop n-1 is to be pole 2; etc, alternating.

From this description, the number of moves necessary for n hoops is one more than twice the number required for n-1 hoops, as n-1 must be moved to the non-target pole, the nth moved to the target pole and then the n-1 must be moved again to the target pole.

So the sequence showing the number of required moves is:
1,3,7,15,31,63,127,...

Edited on September 7, 2003, 11:24 am
Edited on September 7, 2003, 3:48 pm

Posted by Charlie on 2003-09-07 11:23:12