Henry decides one morning to do a workout, and he walks of the way from his home to his gym. The gym is kilometers away from Henry's home. At that point, he changes his mind and walks of the way from where he is back toward home. When he reaches that point, he changes his mind again and walks of the distance from there back toward the gym. If Henry keeps changing his mind when he has walked of the distance toward either the gym or home from the point where he last changed his mind, he will get very close to walking back and forth between a point kilometers from home and a point kilometers from home. What is ?
- A)
- B)
- C)
- D)
- E)
Answer
C
Key insight
In the long run Henry bounces between two fixed turning points. Walking toward the gym from A must end at B, and walking home from B must end at A.
Solution
Measure every position in kilometers from home, so home is and the gym is .
Step 1: what one leg of the walk does.
- Walking of the way home from position : he covers of the distance , so he ends at .
- Walking of the way toward the gym from position : the distance left is , so he ends at .
Step 2: watch the first few turns.
- Start at . Toward the gym: . Home: . Gym: . Home: . Gym: .
- The turning points settle near and . Let us find them exactly.
Step 3: the settled points reproduce each other.
5. Call the point near home and the point near the gym . Walking toward the gym from lands on , and walking home from lands on :
6. Substitute into the first equation: . So and .
7. Then .
8. .
The answer is .
Why this works
When a back-and-forth process settles down, the points it settles on must reproduce themselves: one step from gives , and one step from gives again. Writing that down gives two simple equations, which is much faster than following the walk forever. A few steps of the actual walk are still useful as a check on the numbers.
The trap
Using the first two turning points, 3/2 and 3/8, as A and B instead of the points the walk settles down to.
Concise solution
Measure positions in kilometers from home, with the gym at .
- Walking of the way toward the gym from position ends at .
- Walking of the way toward home from position ends at .
In the limit, Henry oscillates between a point (where he turns toward the gym) and a point (where he turns toward home). Each must produce the other:
Substituting the second into the first: , so and . Then .
The answer is .
Review in the AoPS books
- Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
- Introduction to Algebra, Chapter 3: One-Variable Linear Equations (§3.3, §3.4)
- Intermediate Counting & Probability, Chapter 10: Recursion
- Intermediate Algebra, Chapter 17: More Sequences and Series (§17.1, §17.2)
Techniques
Set up the equation/formula and compute; no special trick needed · Define states/recurrence and iterate