2013 AIME II Problem 14

Below is the professionally curated solution for Problem 14 of the 2013 AIME II, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:modular arithmeticbounding to limit casessummation

Difficulty rating: 3270

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.

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.F(3m) = m - 2, \qquad F(3m + 1) = m - 1, \qquad F(3m + 2) = m.

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)=m1F(3m - 1) = F(3(m-1) + 2) = m - 1), each triple contributes (m1)+(m2)+(m1)=3m4,(m - 1) + (m - 2) + (m - 1) = 3m - 4, so n=20100F(n)=m=733(3m4)=3(7+33)272427=1620108=1512.\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.

The requested remainder is 512.512.

← Problem 13Full ExamProblem 15

Problem 14 in Other Years