|
To solve this problem, we will need a good algorithm to move as many possible hoops from one pole to another when there are N hoops.
In this algorithm, I define H(N) to be the maximum number of hoops that can be moved from pole 1 to pole 2 when there are N poles (including the first pole). F(N) is the maximum number of hoops that can be moved from pole 1 to pole 2 when there are indefinitely many extra hoops on pole 1 and N *empty* poles.
Algorithm for moving F(N) hoops:
1. There are indefinitely hoops on pole 1, and N+1 poles. Move F(N-1) hoops from pole 1 to pole 2.
2. Move F(N-2) hoops from pole 1 to pole 3.
3. Move F(N-3) hoops from pole 1 to pole 4.
4. Repeat this pattern until only the last pole is empty.
5. Move the last hoop from the first pole to the last pole. All steps previous to this one are repeated backwards, moving all the hoops onto the last pole instead of the first.
From this algorithm we determine that F(N) is equal to the sum F(N-1)+F(N-2)+F(N-3)+...+F(2)+F(1)+1. Since F(1) is trivially 1, F(N) must be 2(N-1).
The algorithm for moving H(N) is exactly the same, except we start with H(N) hoops and N poles. When the last hoop is moved to the last pole, pole 1 is empty and available to complete the steps. From this algorithm we determine that H(N) is equal to F(N-1)+F(N-2)+...+F(3)+F(2)+1. Since F(N) is a known function, H(N) is easily proven to be 2(N-1)-1. |
