2024 AIME II 第 7 题

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

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

7.

NN 是满足如下性质的最大四位整数:每当把它的某一位数字改为 11 时,所得数都能被 77 整除。设 NN 除以 10001000 时的商和余数分别为 QQRR。求 Q+RQ + R

Let NN be the greatest four-digit integer with the property that whenever one of its digits is changed to 1,1, the resulting number is divisible by 7.7. Let QQ and RR be the quotient and remainder, respectively, when NN is divided by 1000.1000. Find Q+R.Q + R.

答案:699
知识点:模运算数字最优化
难度评级:2650
解答:

NN 的数字为 a,b,c,da, b, c, d。把千位数字改成 11 得到 N(a1)1000N - (a - 1) \cdot 1000,所以 N1000(a1)(mod7)N \equiv 1000(a-1) \pmod 7,其他数位同理。由于 100061000 \equiv 61002100 \equiv 2、且 103(mod7)10 \equiv 3 \pmod 7N6(a1)2(b1)3(c1)d1(mod7). \begin{aligned} N &\equiv 6(a-1) \\ &\equiv 2(b-1) \equiv 3(c-1) \\ &\equiv d - 1 \pmod 7. \end{aligned}

k=Nmod7k = N \bmod 7。利用 616 \equiv -1 以及逆元 2142^{-1} \equiv 43153^{-1} \equiv 5,各位数字满足 a1ka \equiv 1 - kb1+4kb \equiv 1 + 4kc1+5kc \equiv 1 + 5kd1+k(mod7)d \equiv 1 + k \pmod 7。但同时 kNk \equiv N 6a+2b+3c+d(mod7)\equiv 6a + 2b + 3c + d \pmod 7;代入得到 k12+18k5+4kk \equiv 12 + 18k \equiv 5 + 4k,所以 3k23k \equiv 2,即 k3(mod7)k \equiv 3 \pmod 7

于是 a5a \equiv 5b6b \equiv 6c2c \equiv 2d4(mod7)d \equiv 4 \pmod 7,在每个同余类中 取最大数字,得到 a=5a = 5(同余类 {5,12,}\{5, 12, \ldots\} 中没有更大的数字)、b=6b = 6c=9c = 9d=4d = 4:所以 N=5694N = 5694。确实 1694,5194,5614,56911694, 5194, 5614, 5691 都是 77 的倍数。最后 Q=5Q = 5R=694R = 694,所以 Q+R=699Q + R = 699

Write NN with digits a,b,c,d.a, b, c, d. Changing the thousands digit to 11 produces N(a1)1000,N - (a - 1) \cdot 1000, so N1000(a1)(mod7),N \equiv 1000(a-1) \pmod 7, and similarly for the other digits. Since 10006,1000 \equiv 6, 1002,100 \equiv 2, and 103(mod7),10 \equiv 3 \pmod 7, N6(a1)2(b1)3(c1)d1(mod7). \begin{aligned} N &\equiv 6(a-1) \\ &\equiv 2(b-1) \equiv 3(c-1) \\ &\equiv d - 1 \pmod 7. \end{aligned}

Let k=Nmod7.k = N \bmod 7. Using 616 \equiv -1 and the inverses 214,2^{-1} \equiv 4, 315,3^{-1} \equiv 5, the digits satisfy a1k,a \equiv 1 - k, b1+4k,b \equiv 1 + 4k, c1+5k,c \equiv 1 + 5k, d1+k(mod7).d \equiv 1 + k \pmod 7. But also kNk \equiv N 6a+2b+3c+d(mod7);\equiv 6a + 2b + 3c + d \pmod 7; substituting gives k12+18k5+4k,k \equiv 12 + 18k \equiv 5 + 4k, so 3k23k \equiv 2 and k3(mod7).k \equiv 3 \pmod 7.

Then a5,a \equiv 5, b6,b \equiv 6, c2,c \equiv 2, d4(mod7),d \equiv 4 \pmod 7, and taking the largest digit in each class gives a=5a = 5 (the class {5,12,}\{5, 12, \ldots\} has no larger digit), b=6,b = 6, c=9,c = 9, d=4:d = 4: N=5694.N = 5694. Indeed 1694,5194,5614,56911694, 5194, 5614, 5691 are all multiples of 7.7. Finally Q=5,Q = 5, R=694,R = 694, and Q+R=699.Q + R = 699.

← 第 6 题#6
完整试卷

其他年份的第 7 题