2013 AIME II 第 14 题

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

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

14.

对正整数 nn 和 kk,令 f(n,k)f(n, k) 为 nn 除以 kk 的余数;并对 n>1n \gt 1 定义 F(n)=max⁡1≤k≤n2f(n,k)。F(n) = \max_{1 \le k \le \frac{n}{2}} f(n, k)\text{。}求 ∑n=20100F(n)\sum_{n = 20}^{100} F(n) 除以 10001000 的余数。

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)=max⁡1≤k≤n2f(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
小提示:

当 k≤n2k \le \frac{n}{2} 时,商至少为 22,所以余数至多为 min⁡(k−1, n−2k)\min(k - 1,\ n - 2k);尝试 kk 接近 n3\frac{n}{3} 的情况。

For k≤n2k \le \frac{n}{2} the quotient is at least 2,2, so the remainder is at most min⁡(k−1, n−2k);\min(k - 1,\ n - 2k); try kk near n3\frac{n}{3}

大提示:

证明 F(3m)=m−2F(3m) = m - 2,F(3m+1)=m−1F(3m+1) = m - 1,且 F(3m+2)=mF(3m+2) = m,它们都在 k=m+1k = m + 1 处取得,然后对范围求和。

Show F(3m)=m−2,F(3m) = m - 2, F(3m+1)=m−1,F(3m+1) = m - 1, and F(3m+2)=m,F(3m+2) = m, each achieved at k=m+1,k = m + 1, then sum over the range

解答:

当 k≤n2k \le \frac{n}{2} 时,商 ⌊nk⌋\lfloor \frac{n}{k} \rfloor 至少为 22,所以余数 f(n,k)≤n−2kf(n, k) \le n - 2k,也有 f(n,k)≤k−1f(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+r−2m + r - 2,所以 F(n)≥m+r−2F(n) \ge m + r - 2。反过来,当 k≥m+1k \ge m + 1 时,f(n,k)≤n−2k≤m+r−2f(n, k) \le n - 2k \le m + r - 2,而对更小的 kk,用上界 f(n,k)≤k−1f(n, k) \le k - 1 即可完成证明:当 r=2r = 2 时,对 k≤m+1k \le m + 1,余数至多为 mm;当 r=1r = 1 时,对 k≤mk \le m,余数至多为 m−1m - 1;当 r=0r = 0 时,对 k≤m−1k \le m - 1,余数至多为 m−2m - 2,而 k=mk = m 正好整除 3m3m,余数为 00。因此 F(3m)=m−2,F(3m+1)=m−1,F(3m+2)=m。 \begin{aligned} F(3m) &= m - 2, \\ F(3m + 1) &= m - 1, \\ F(3m + 2) &= m \end{aligned}\text{。}

把 n=20,…,100n = 20, \ldots, 100 按三元组 3m−13m - 1、3m3m、3m+13m + 1 分组,其中 m=7,…,33m = 7, \ldots, 33(注意 F(3m−1)=F(3(m−1)+2)F(3m - 1) = F(3(m-1) + 2) =m−1= m - 1),每组三项贡献 (m−1)+(m−2)+(m−1)(m - 1) + (m - 2) + (m - 1) =3m−4= 3m - 4,所以 ∑n=20100F(n)=∑m=733(3m−4)=3⋅(7+33)⋅272−4⋅27=1620−108=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}\text{。}

所求余数为 512512。

For k≤n2k \le \frac{n}{2} the quotient ⌊nk⌋\lfloor \frac{n}{k} \rfloor is at least 2,2, so the remainder satisfies f(n,k)≤n−2kf(n, k) \le n - 2k as well as f(n,k)≤k−1.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+r−2,m + r - 2, so F(n)≥m+r−2.F(n) \ge m + r - 2. Conversely, for k≥m+1,k \ge m + 1, f(n,k)≤n−2k≤m+r−2,f(n, k) \le n - 2k \le m + r - 2, and for smaller kk the bound f(n,k)≤k−1f(n, k) \le k - 1 finishes the job: when r=2r = 2 it gives at most mm for k≤m+1;k \le m + 1; when r=1r = 1 it gives at most m−1m - 1 for k≤m;k \le m; and when r=0r = 0 it gives at most m−2m - 2 for k≤m−1,k \le m - 1, while k=mk = m divides 3m3m exactly, leaving remainder 0.0. Hence F(3m)=m−2,F(3m+1)=m−1,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 3m−1,3m - 1, 3m,3m, 3m+13m + 1 for m=7,…,33m = 7, \ldots, 33 (note F(3m−1)=F(3(m−1)+2)F(3m - 1) = F(3(m-1) + 2) =m−1= m - 1), each triple contributes (m−1)+(m−2)+(m−1)(m - 1) + (m - 2) + (m - 1) =3m−4,= 3m - 4, so ∑n=20100F(n)=∑m=733(3m−4)=3⋅(7+33)⋅272−4⋅27=1620−108=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 题