2015 AMC 10B Problem 24

P21-25~7 minPrint

Sequences & Series Coordinate Geometry Paths & Grids Compute small cases, spot the pattern, generalize

Aaron the ant walks on the coordinate plane according to the following rules. He starts at the origin $p_0=(0,0)$ facing to the east and walks one unit, arriving at $p_1=(1,0)$ . For $n=1,2,3,\dots$ , right after arriving at the point $p_n$ , if Aaron can turn $90^\circ$ left and walk one unit to an unvisited point $p_{n+1}$ , he does that. Otherwise, he walks one unit straight ahead to reach $p_{n+1}$ . Thus the sequence of points continues $p_2=(1,1), p_3=(0,1), p_4=(-1,1), p_5=(-1,0)$ , and so on in a counterclockwise spiral pattern. What is $p_{2015}$ ?

Show solution without answering

Key insight

At square step numbers the ant sits at a spiral corner. Step 1936 is at (-22, 22); then 44 steps down and 35 steps right.

Solution

Step $2015$ is far too many to trace, so trace the first few turns, find a pattern, and jump ahead.

Step 1: trace the start. The spiral goes: $1$ step east, $1$ north, $2$ west, $2$ south, $3$ east, $3$ north, $4$ west, $4$ south, and so on. The side lengths are $1, 1, 2, 2, 3, 3, 4, 4, \ldots$

Step 2: look at square numbers. Add up the side lengths: $1$ , $1 + 1 = 2$ , $+2 = 4$ , $+2 = 6$ , $+3 = 9$ , $+3 = 12$ , $+4 = 16$ . The square numbers $1, 4, 9, 16, \ldots$ show up at every other corner. Here are those corners:

step	$1$	$4$	$9$	$16$	$25$
point	$(1, 0)$	$(-1, 1)$	$(2, -1)$	$(-2, 2)$	$(3, -2)$

Step 3: the pattern for even squares. At step $2^2 = 4$ the ant is at $(-1, 1)$ , and at step $4^2 = 16$ it is at $(-2, 2)$ . In general, at step $(2k)^2$ it is at $(-k, k)$ , the top-left corner, having just walked west. From there it turns left and walks south for $2k$ steps, then turns left again and walks east for $2k + 1$ steps.

(Check with $k = 1$ : from $p_4 = (-1, 1)$ , $2$ steps south reach $(-1, -1)$ at step $6$ , then $3$ steps east reach $(2, -1)$ at step $9$ . That matches the table.)

Step 4: jump to 2015. The largest even square not above $2015$ is $44^2 = 1936$ (and $45^2 = 2025$ is too big). So with $k = 22$ :
- At step $1936$ the ant is at $(-22, 22)$ .
- It walks $44$ steps south, reaching $(-22, -22)$ at step $1936 + 44 = 1980$ .
- Then it walks east. Step $2015$ is $2015 - 1980 = 35$ steps later, at $(-22 + 35, -22) = (13, -22)$ .

The answer is $\boxed{\textbf{(D)}\ (13,-22)}$ .

Why this works

In a square spiral the side lengths go $1, 1, 2, 2, 3, 3, \ldots$ , and adding them gives square numbers at every other corner. So square step numbers are easy landmarks. Work out a few small cases, find where the landmarks are and which way the ant is facing there, then jump to the landmark just below the step you want and walk the rest.

Alternative approach

Use odd squares instead. From the table, step $(2k+1)^2$ is at $(k + 1, -k)$ , reached while walking east: step $9$ is at $(2, -1)$ and step $25$ is at $(3, -2)$ . So step $45^2 = 2025$ is at $(23, -22)$ . Step $2015$ is $10$ steps earlier on that same eastward stretch, so it is at $(23 - 10, -22) = (13, -22)$ . Getting the same point from both landmarks is a good check.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Trace the spiral and record where the ant is at perfect-square indices:
$p_1 = (1,0),\quad p_4 = (-1,1),\quad p_9 = (2,-1),\quad p_{16} = (-2,2),\quad p_{25} = (3,-2).$
The pattern: from $p_{k^2}$ the ant walks a leg of length $k$ (turning left first), then a leg of length $k+1$ , using $2k + 1$ steps and arriving at $p_{(k+1)^2}$ . Each pair of legs moves the ant to the opposite diagonal corner one ring further out. In particular, for even indices
$p_{(2k)^2} = (-k, k),$
reached while walking west, so the next leg goes south (length $2k$ ) and the one after goes east (length $2k+1$ ).

Since $44^2 = 1936 \le 2015 < 2025 = 45^2$ , start from $p_{1936} = (-22, 22)$ . The ant walks $44$ steps south to $p_{1980} = (-22, -22)$ , then heads east. The remaining $2015 - 1980 = 35$ steps go east:
$p_{2015} = (-22 + 35, -22) = (13, -22).$

The answer is $\boxed{\textbf{(D)}\ (13,-22)}$ .

Review in the AoPS books

Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Introduction to Geometry, Chapter 17: Analytic Geometry
Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)