2012 AIME I Problem 11

Below is the professionally curated solution for Problem 11 of the 2012 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:lattice pointmodular arithmeticparityinvariant

Difficulty rating: 2990

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.

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 10Full ExamProblem 12

Problem 11 in Other Years