You are here

Minimum way to move all circles

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?


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$