There are some poles, and on the first pole are some rings, each a different size. The sizes of the rings increases from the top to the bottom of the pole. The only allowable move is to take the top ring from any pole and place onto another pole. You cannot place a ring on top of another ring unless the other ring is exactly one size bigger. You can make as many moves as you like.

Your goal is to move all the rings onto the second pole, in the same order. What is the highest number of rings that can be moved when there are N poles? How can you move this many rings?

(In reply to re(2): solution (I think) by Erik O.)

Leming is right, it's 2^n-1, so with one additional pole you can move 1, with two additional poles you can move 3, with 3 additional poles you can move 7, and with 4 additional poles you can move 15.

The idea is you move them into midway points like this:

(my notation: each consecutive group of letters represents one pole, left to right reads top to bottom of the rings, 'a' being the smallest ring)

For three poles:

c <empty> ab

This can be easily seen how to get to (a->2, b->3 a->3), then you move c>2 and transfer a and b on top.

For four poles:

g <empty> ef abcd

To do this, recursively move abc somewhere as in 3 poles, then move d, then move abc on top.  Move e->2, f->3, then e->3. Now move g, and put everything on top.

For five poles:

o <empty> mn ijkl abcdefgh

For this, recursively move abcdefg somewhere as in 4 poles, move h, then abcdefg on top. Then recursively move ijk somewhere as in 3 poles, move l, then move ijk on top. Then m->2, n->3, m->3. Now move o, and put everything on top.

For six poles:

You get the idea?

Edited on May 3, 2005, 7:45 pm

Posted by Avin on 2005-05-03 19:43:48