2012 AIME I 第 11 题

先试着解答 2012 AIME I 第 11 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2012 AIME I 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

11.

一只青蛙从 P0=(0,0)P_0 = (0, 0) 出发,并按如下规则连续跳跃:若当前在 Pn=(xn,yn)P_n = (x_n, y_n),则它可以跳到 Pn+1P_{n+1},其中这个新位置可以是 (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)(xn10,yn5)(x_n - 10, y_n - 5) 中任一点。满足 x+y100|x| + |y| \le 100 且可由一系列这类跳跃到达的点 (x,y)(x, y) 共有 MM 个。求 MM 除以 10001000 的余数。

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.

答案:373
知识点:格点模运算奇偶性不变量
难度评级:2990
解答:

每次跳跃使 x+yx + y 改变 +9+915-15,并使 xyx - y 改变 ±5\pm 5。从 (0,0)(0, 0) 出发,每个可达点都满足 x+y=3jx + y = 3jxy=5kx - y = 5k,其中 jjkk 为整数;此外 x=3j+5k2x = \frac{3j + 5k}{2} 必须为整数,所以 jjkk 奇偶性相同。又因为 x+y=max(x+y,xy)|x| + |y| = \max(|x + y|,\, |x - y|),条件 x+y100|x| + |y| \le 100 变为 j33|j| \le 33k20|k| \le 20

反过来,每个这样的点都可达:一次跳跃会在相邻直线 xy=5kx - y = 5k 之间移动,同时使 jj 改变 335-5,因此翻转其奇偶性;而两步组合可以平移 (9,9)(9, 9)(15,15)(-15, -15),二者组合为两次前者加一次后者,得到位移 (3,3)(3, 3),也就是在固定直线上使参数 jj 改变 22。这些移动合起来可到达每个奇偶性相同的 (j,k)(j, k)

计数:偶数 jj3333 个,可与偶数 kk2121 个配对;奇数 jj3434 个,可与奇数 kk2020 个配对。因此 M=3321+3420=1373M = 33 \cdot 21 + 34 \cdot 20 = 1373。余数为 373373

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.

← 第 10 题#10
完整试卷

其他年份的第 11 题