All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Towers of Hanoi (Posted on 2003-09-07)
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?

 Submitted by Lewis Rating: 3.0667 (15 votes) Solution: (Hide) The shortest method takes 31 steps: XS from pole 1 to pole 3 S from pole 1 to pole 2 XS from pole 3 to pole 2 M from pole 1 to pole 3 XS from pole 2 to pole 1 S from pole 2 to pole 3 XS from pole 1 to pole 3 L from pole 1 to pole 2 XS from pole 3 to pole 2 S from pole 3 to pole 1 XS from pole 2 to pole 1 M from pole 3 to pole 2 XS from pole 1 to pole 3 S from pole 1 to pole 2 XS from pole 3 to pole 2 XL from pole 1 to pole 3 XS from pole 2 to pole 1 S from pole 2 to pole 3 XS from pole 1 to pole 3 M from pole 2 to pole 1 XS from pole 3 to pole 2 S from pole 3 to pole 1 XS from pole 2 to pole 1 L from pole 2 to pole 3 XS from pole 1 to pole 3 S from pole 1 to pole 2 XS from pole 3 to pole 2 M from pole 1 to pole 3 XS from pole 2 to pole 1 S from pole 2 to pole 3 XS from pole 1 to pole 3 First, to find the shortest method, pretend there is only one hoop. Obviously, you only have to move it to the third pole, and you're done. Then, the case with two hoops. You have to move the top hoop to the 'extra' pole (2), then move the bottom hoop to the third pole, and then put the smaller hoop back on top of it. For three hoops, you have to move the top two hoops to the extra pole (the same way you would put two hoops onto the third pole), then put the third one where you want it, and put the two hoops back on top of it (again, the same way as moving just two hoops). Thus, it can be reasoned that the least number of steps it takes to move n hoops will twice the number of steps it took to move n-1 hoops, plus the one step to move the largest hoop to the third pool. (Sn = 2Sn-1 + 1). The least number of moves it will take to move 5 hoops, then, is: 2(2(2(2(1)+1)+1)+1)+1=31 Several methods were offered in the comments to solve this. Charlie posted a BASIC program here that uses recursion to solve the problem. DJ posted a C++ program here with a similar recursion, that also shows the state of the poles after each move. Frederico Kereki posted a simple, non-recursive method here that also yields the simplest solution.

 Subject Author Date No Subject Arjun 2007-09-08 12:20:37 re: A non-recursive solution Xen 2004-05-25 16:17:04 re(2): Stacks--Basic version Charlie 2003-09-09 14:14:52 re: Stacks--Basic version Charlie 2003-09-09 14:07:51 Parity Brian Smith 2003-09-09 10:06:49 Stacks DJ 2003-09-08 13:28:35 A non-recursive solution Federico Kereki 2003-09-08 13:18:33 C++ function DJ 2003-09-08 12:29:22 follow this order Ryan 2003-09-08 02:28:36 You blew it, Lewis !!!!! Dan 2003-09-08 01:22:33 re: Recursion challenge Charlie 2003-09-07 16:12:32 re(2): strategy Charlie 2003-09-07 15:48:01 re: solution in 11 moves with 5 poles Gamer 2003-09-07 15:40:06 solution in 19 moves Victor Zapana 2003-09-07 15:13:01 Recursion challenge Gamer 2003-09-07 14:19:04 re: strategy Gamer 2003-09-07 14:15:48 strategy Charlie 2003-09-07 11:23:12 re: Holy Hula Hoops! Charlie 2003-09-07 11:14:04 Steps to follow (not for the impatient) Jun 2003-09-07 10:41:04 Number of moves Jill 2003-09-07 10:35:31 Holy Hula Hoops! Eric 2003-09-07 10:12:37

 Search: Search body:
Forums (0)