Submitted by yonatan zilpa on

Consider a game with three vertical sticks and 5 circles, where each circle has a hole in the middle. The circles arranged in one stick as shown in the following picture:
The task is to move all the circles to a nearby stick, circles can be move from one stick to another, but a circle cannot be put over a smaller one. What are the minimum number of steps needed to complete this task?

## Answer

It is fairly easy to see that in the case of two circles (instead of 5) we need $3=2^2-1$ steps to
complete the task. In the case of 3 circles we need $7=2^3-1$ steps. Now in the case of 4 circles we may
ignore the big circle in the bottom move all the remaining 3 to a nearby stick, this will
require 7 steps. Then we can move the biggest circle to the other nearby stick this will require
one additional step. We then can move the 3 circles to the same stick where we positioned the
big stick, this will require additional 7 steps. Hence, in the case of 4 circles we can accomplish
the task with a minimum of $15=2^4-1$ steps. In general for $n$ circles we would need a minimum of
$2^n-1$ steps to accomplish the task. Hence the answer would be $31=2^5-1$ steps. $\square$