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 n1 hoops to pole 2, then move the nth hoop to pole 3 and then move the other n1 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 n1 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 n1 hoops, as n1 must be moved to the nontarget pole, the nth moved to the target pole and then the n1 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 20030907 11:23:12 