2012 AIME I Problem 11

Attempt Problem 11 of the 2012 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2012 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

11.

A frog begins at P0=(0,0)P_0 = (0, 0) and makes a sequence of jumps according to the following rule: from Pn=(xn,yn),P_n = (x_n, y_n), the frog jumps to Pn+1,P_{n+1}, which may be any of the points (xn+7,yn+2),(x_n + 7, y_n + 2), (xn+2,yn+7),(x_n + 2, y_n + 7), (xn5,yn10),(x_n - 5, y_n - 10), or (xn10,yn5).(x_n - 10, y_n - 5). There are MM points (x,y)(x, y) with x+y100|x| + |y| \le 100 that can be reached by a sequence of such jumps. Find the remainder when MM is divided by 1000.1000.

Answer: 373
Concepts:lattice pointmodular arithmeticparityinvariant
Difficulty rating: 2990
Solution:

Each jump changes x+yx + y by +9+9 or 15-15 and changes xyx - y by ±5.\pm 5. Starting from (0,0),(0, 0), every reachable point therefore has x+y=3jx + y = 3j and xy=5kx - y = 5k for integers jj and k;k; moreover x=3j+5k2x = \frac{3j + 5k}{2} must be an integer, so jj and kk have the same parity. Since x+y=max(x+y,xy),|x| + |y| = \max(|x + y|,\, |x - y|), the condition x+y100|x| + |y| \le 100 becomes j33|j| \le 33 and k20.|k| \le 20.

Conversely, every such point is reachable: a single jump moves between neighboring lines xy=5kx - y = 5k (changing jj by 33 or 5,-5, which flips its parity), and two-jump combinations translate by (9,9)(9, 9) or (15,15),(-15, -15), which combine — two of the former plus one of the latter — into the shift (3,3),(3, 3), moving jj by 22 along a fixed line. Together these reach every pair (j,k)(j, k) of equal parity.

Counting: even jj (3333 values) pairs with even kk (2121 values), and odd jj (3434 values) with odd kk (2020 values), so M=3321+3420=1373.M = 33 \cdot 21 + 34 \cdot 20 = 1373. The remainder is 373.373.

← Problem 10#10
Full Exam

Problem 11 in Other Years