2013 AIME II 第 14 题

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

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

14.

对正整数 nnkk,令 f(n,k)f(n, k)nn 除以 kk 的余数;并对 n>1n \gt 1 定义 求 n=20100F(n)\sum_{n = 20}^{100} F(n) 除以 10001000 的余数。 F(n)=max1kn2f(n,k).F(n) = \max_{1 \le k \le \frac{n}{2}} f(n, k).

For positive integers nn and k,k, let f(n,k)f(n, k) be the remainder when nn is divided by k,k, and for n>1n \gt 1 let F(n)=max1kn2f(n,k).F(n) = \max_{1 \le k \le \frac{n}{2}} f(n, k). Find the remainder when n=20100F(n)\sum_{n = 20}^{100} F(n) is divided by 1000.1000.

答案:512
知识点:模运算极限情形界定求和
难度评级:3270
解答:

kn2k \le \frac{n}{2} 时,商 n/k\lfloor n/k \rfloor 至少为 22,所以余数 f(n,k)n2kf(n, k) \le n - 2k,也有 f(n,k)k1f(n, k) \le k - 1。写 n=3m+rn = 3m + r,其中 r{0,1,2}r \in \{0, 1, 2\}。用 k=m+1k = m + 1 去除,商为 22,余数为 m+r2m + r - 2,所以 F(n)m+r2F(n) \ge m + r - 2。反过来,当 km+1k \ge m + 1 时,f(n,k)n2km+r2f(n, k) \le n - 2k \le m + r - 2,而对更小的 kk,用上界 f(n,k)k1f(n, k) \le k - 1 即可完成证明:当 r=2r = 2 时,对 km+1k \le m + 1,余数至多为 mm;当 r=1r = 1 时,对 kmk \le m,余数至多为 m1m - 1;当 r=0r = 0 时,对 km1k \le m - 1,余数至多为 m2m - 2,而 k=mk = m 正好整除 3m3m,余数为 00。因此 F(3m)=m2,F(3m+1)=m1,F(3m+2)=m. \begin{aligned} F(3m) &= m - 2, \\ F(3m + 1) &= m - 1, \\ F(3m + 2) &= m. \end{aligned}

n=20,,100n = 20, \ldots, 100 按三元组 3m13m - 13m3m3m+13m + 1 分组,其中 m=7,,33m = 7, \ldots, 33(注意 F(3m1)=F(3(m1)+2)F(3m - 1) = F(3(m-1) + 2) =m1= m - 1),每组三项贡献 (m1)+(m2)+(m1)(m - 1) + (m - 2) + (m - 1) =3m4= 3m - 4,所以 n=20100F(n)=m=733(3m4)=3(7+33)272427=1620108=1512. \begin{aligned} \tiny \sum_{n=20}^{100} F(n) &= \sum_{m=7}^{33} (3m - 4) \\ &= 3 \cdot \frac{(7 + 33) \cdot 27}{2} - 4 \cdot 27 \\ &= 1620 - 108 = 1512. \end{aligned}

所求余数为 512512

For kn2k \le \frac{n}{2} the quotient n/k\lfloor n/k \rfloor is at least 2,2, so the remainder satisfies f(n,k)n2kf(n, k) \le n - 2k as well as f(n,k)k1.f(n, k) \le k - 1. Write n=3m+rn = 3m + r with r{0,1,2}.r \in \{0, 1, 2\}. Dividing by k=m+1k = m + 1 gives quotient 22 and remainder m+r2,m + r - 2, so F(n)m+r2.F(n) \ge m + r - 2. Conversely, for km+1,k \ge m + 1, f(n,k)n2km+r2,f(n, k) \le n - 2k \le m + r - 2, and for smaller kk the bound f(n,k)k1f(n, k) \le k - 1 finishes the job: when r=2r = 2 it gives at most mm for km+1;k \le m + 1; when r=1r = 1 it gives at most m1m - 1 for km;k \le m; and when r=0r = 0 it gives at most m2m - 2 for km1,k \le m - 1, while k=mk = m divides 3m3m exactly, leaving remainder 0.0. Hence F(3m)=m2,F(3m+1)=m1,F(3m+2)=m. \begin{aligned} F(3m) &= m - 2, \\ F(3m + 1) &= m - 1, \\ F(3m + 2) &= m. \end{aligned}

Grouping n=20,,100n = 20, \ldots, 100 as triples 3m1,3m - 1, 3m,3m, 3m+13m + 1 for m=7,,33m = 7, \ldots, 33 (note F(3m1)=F(3(m1)+2)F(3m - 1) = F(3(m-1) + 2) =m1= m - 1), each triple contributes (m1)+(m2)+(m1)(m - 1) + (m - 2) + (m - 1) =3m4,= 3m - 4, so n=20100F(n)=m=733(3m4)=3(7+33)272427=1620108=1512. \begin{aligned} \tiny \sum_{n=20}^{100} F(n) &= \sum_{m=7}^{33} (3m - 4) \\ &= 3 \cdot \frac{(7 + 33) \cdot 27}{2} - 4 \cdot 27 \\ &= 1620 - 108 = 1512. \end{aligned}

The requested remainder is 512.512.

← 第 13 题#13
完整试卷

其他年份的第 14 题