2013 AIME II Problem 14

Attempt Problem 14 of the 2013 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2013 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

14.

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.

Answer: 512
Concepts:modular arithmeticbounding to limit casessummation
Difficulty rating: 3270
Solution:

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.

← Problem 13#13
Full Exam

Problem 14 in Other Years