Aaron the ant walks on the coordinate plane according to the following rules. He starts at the origin facing to the east and walks one unit, arriving at . For , right after arriving at the point , if Aaron can turn left and walk one unit to an unvisited point , he does that. Otherwise, he walks one unit straight ahead to reach . Thus the sequence of points continues , and so on in a counterclockwise spiral pattern. What is ?
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
At perfect-square indices the spiral sits on a diagonal: p_{(2k)^2} = (-k, k); from p_1936 = (-22, 22) walk 44 south, then 35 east.
Solution
Trace the spiral and record where the ant is at perfect-square indices:
The pattern: from the ant walks a leg of length (turning left first), then a leg of length , using steps and arriving at . Each pair of legs moves the ant to the opposite diagonal corner one ring further out. In particular, for even indices
reached while walking west, so the next leg goes south (length ) and the one after goes east (length ).
Since , start from . The ant walks steps south to , then heads east. The remaining steps go east:
The answer is .
Why this works
Spirals are governed by squares: the -th "corner turn" happens after steps because accumulates to consecutive squares. Once the anchor points are identified with their direction of travel, any index is a short walk from the nearest square below it. Compute a handful of small cases, locate the square pattern, then jump.
Alternative approach
Use the odd squares instead: , reached walking east. So , and ten steps earlier along that eastward leg is . Consistency between the two anchors is a good check.
The trap
Off-by-one in the leg lengths (each new pair of legs has lengths k and k+1) or walking the last leg in the wrong direction, landing on (-13, -22) or (22, -13).
Common mistakes
- Off-by-one in the leg lengths (each new pair of legs has lengths k and k+1) or walking the last leg in the wrong direction, landing on (-13, -22) or (22, -13).
- Anchoring at but forgetting that the southward leg has length (not or ), which shifts the final -coordinate.
Techniques
Compute small cases, spot the pattern, generalize