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$