2013 AIME I 第 15 题

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

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

15.

设 NN 为满足以下条件的整数有序三元组 (A,B,C)(A, B, C) 的个数:

• 0≤A<B<C≤990 \le A \lt B \lt C \le 99,

• 存在整数 aa、bb、cc 和素数 pp,其中 0≤b<a<c<p0 \le b \lt a \lt c \lt p,

• pp 整除 A−aA - a、B−bB - b、C−cC - c,并且

• 每个有序三元组 (A,B,C)(A, B, C) 和 (b,a,c)(b, a, c) 都构成等差数列。

求 NN。

Let NN be the number of ordered triples (A,B,C)(A, B, C) of integers satisfying the conditions

• 0≤A<B<C≤99,0 \le A \lt B \lt C \le 99,

• there exist integers a,a, b,b, and c,c, and prime pp where 0≤b<a<c<p,0 \le b \lt a \lt c \lt p,

• pp divides A−a,A - a, B−b,B - b, and C−c,C - c, and

• each ordered triple (A,B,C)(A, B, C) and each ordered triple (b,a,c)(b, a, c) form arithmetic sequences.

Find N.N.

答案:272
知识点:等差数列模运算数对计数
难度评级:3270
小提示:

若 DD 和 dd 分别是 (A,B,C)(A,B,C) 与 (b,a,c)(b,a,c) 的公差,则模 pp 下同时有 D≡−dD \equiv -d 和 D≡2dD \equiv 2d,所以 3d3d 能被 pp 整除。

If DD and dd are the common differences of (A,B,C)(A,B,C) and (b,a,c),(b,a,c), then mod pp both D≡−dD \equiv -d and D≡2d,D \equiv 2d, so 3d3d is divisible by pp

大提示:

因为 0<2d<p0 \lt 2d \lt p,这迫使 p=3p = 3 且 (b,a,c)=(0,1,2)(b,a,c) = (0,1,2);于是数出满足 A≡1A \equiv 1、B≡0B \equiv 0、C≡2(mod3)C \equiv 2 \pmod 3 的三元组。

Since 0<2d<p,0 \lt 2d \lt p, that forces p=3p = 3 and (b,a,c)=(0,1,2);(b,a,c) = (0,1,2); count triples with A≡1,A \equiv 1, B≡0,B \equiv 0, C≡2(mod3)C \equiv 2 \pmod 3

解答:

设 dd 为 (b,a,c)(b, a, c) 的公差,则 a−b=c−a=d>0a - b = c - a = d \gt 0,且 c=b+2d<pc = b + 2d \lt p,因此 0<2d<p0 \lt 2d \lt p。设 D>0D \gt 0 为 (A,B,C)(A, B, C) 的公差。对 pp 取模,得到 D=B−A≡b−a=−dD = B - A \equiv b - a = -d,以及 D=C−B≡c−b=2dD = C - B \equiv c - b = 2d,所以 3d3d 能被 pp 整除。由于 0<d<p0 \lt d \lt p,素数 pp 不可能整除 dd,所以 p=3p = 3;此时 2d<32d \lt 3,故 d=1d = 1,且 (b,a,c)=(0,1,2)(b, a, c) = (0, 1, 2)。

因此有效三元组恰好是在 [0,99][0, 99] 中递增的等差数列,并满足 A≡1A \equiv 1、B≡0B \equiv 0、C≡2(mod3)C \equiv 2 \pmod 3。写 A=1+3jA = 1 + 3j,其中 j≥0j \ge 0;公差满足 D≡−1≡2(mod3)D \equiv -1 \equiv 2 \pmod 3,所以 D=2+3kD = 2 + 3k,其中 k≥0k \ge 0。限制为 C=A+2DC = A + 2D =5+3j+6k≤99= 5 + 3j + 6k \le 99,即 j+2k≤31j + 2k \le 31,每个这样的 (j,k)(j, k) 都可行。

对每个 k=0,1,…,15k = 0, 1, \ldots, 15,jj 有 32−2k32 - 2k 种选择,所以 N=∑k=015(32−2k)=16⋅32−2⋅15⋅162=512−240=272。 \begin{aligned} &N = \sum_{k=0}^{15} (32 - 2k) \\ &= 16 \cdot 32 - 2 \cdot \frac{15 \cdot 16}{2} \\ &= 512 - 240 = 272 \end{aligned}\text{。}

Let dd be the common difference of (b,a,c),(b, a, c), so a−b=c−a=d>0a - b = c - a = d \gt 0 and c=b+2d<p,c = b + 2d \lt p, whence 0<2d<p.0 \lt 2d \lt p. Let D>0D \gt 0 be the common difference of (A,B,C).(A, B, C). Reducing mod p,p, we get D=B−A≡b−a=−dD = B - A \equiv b - a = -d and D=C−B≡c−b=2d,D = C - B \equiv c - b = 2d, so 3d3d is divisible by p.p. Since 0<d<p,0 \lt d \lt p, the prime pp cannot divide d,d, so p=3;p = 3; then 2d<32d \lt 3 gives d=1d = 1 and (b,a,c)=(0,1,2).(b, a, c) = (0, 1, 2).

So the valid triples are exactly the increasing arithmetic progressions in [0,99][0, 99] with A≡1,A \equiv 1, B≡0,B \equiv 0, C≡2(mod3).C \equiv 2 \pmod 3. Write A=1+3jA = 1 + 3j with j≥0;j \ge 0; the difference satisfies D≡−1≡2(mod3),D \equiv -1 \equiv 2 \pmod 3, so D=2+3kD = 2 + 3k with k≥0.k \ge 0. The constraint is C=A+2DC = A + 2D =5+3j+6k≤99,= 5 + 3j + 6k \le 99, i.e. j+2k≤31,j + 2k \le 31, and every such pair (j,k)(j, k) works.

For each k=0,1,…,15k = 0, 1, \ldots, 15 there are 32−2k32 - 2k choices of j,j, so N=∑k=015(32−2k)=16⋅32−2⋅15⋅162=512−240=272. \begin{aligned} &N = \sum_{k=0}^{15} (32 - 2k) \\ &= 16 \cdot 32 - 2 \cdot \frac{15 \cdot 16}{2} \\ &= 512 - 240 = 272. \end{aligned}

第 14 题#14
完整试卷

其他年份的第 15 题