2019 AIME II Problem 9

Attempt Problem 9 of the 2019 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 2019 AIME II solutions, or check the answer key.

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

9.

Call a positive integer nn kk-pretty if nn has exactly kk positive divisors and nn is divisible by k.k. For example, 1818 is 66-pretty. Let SS be the sum of the positive integers less than 20192019 that are 2020-pretty. Find S20.\frac{S}{20}.

Answer: 472
Concepts:factor countingprime factorizationcasework
Difficulty rating: 2650
Solution:

We need 20n20 \mid n and τ(n)=20.\tau(n) = 20. Write n=2a5bmn = 2^a 5^b m with gcd(m,10)=1;\gcd(m, 10) = 1; then a2,a \ge 2, b1,b \ge 1, and (a+1)(b+1)τ(m)=20(a + 1)(b + 1)\tau(m) = 20 with a+13a + 1 \ge 3 and b+12.b + 1 \ge 2. The factor a+1a + 1 must be a divisor of 2020 that is at least 3:3: one of 4,4, 5,5, 10,10, 20.20.

If a+1=4,a + 1 = 4, then (b+1)τ(m)=5(b + 1)\tau(m) = 5 forces b=4,b = 4, m=1,m = 1, so n=2354=5000,n = 2^3 5^4 = 5000, too large. If a+1=10,a + 1 = 10, then b=1,b = 1, m=1,m = 1, and n=295=2560,n = 2^9 \cdot 5 = 2560, too large. The case a+1=20a + 1 = 20 is impossible because b+12.b + 1 \ge 2. If a+1=5,a + 1 = 5, then (b+1)τ(m)=4,(b + 1)\tau(m) = 4, giving either b=3,b = 3, m=1,m = 1, so n=2453=2000<2019,n = 2^4 5^3 = 2000 \lt 2019, or b=1b = 1 and τ(m)=2,\tau(m) = 2, so m=pm = p is a prime other than 22 and 55 and n=80p<2019,n = 80p \lt 2019, i.e. p25:p \le 25: p{3,7,11,13,17,19,23}.p \in \{3, 7, 11, 13, 17, 19, 23\}.

Therefore S=2000+80(3+7+11+13+17+19+23)=2000+8093=9440, \begin{aligned} S &= 2000 \\ &\quad {}+ 80\tiny(3 + 7 + 11 + 13 + 17 + 19 + 23) \\ &= 2000 + 80 \cdot 93 \\ &= 9440, \end{aligned} and S20=472.\frac{S}{20} = 472.

← Problem 8#8
Full Exam

Problem 9 in Other Years