2016 AIME II Problem 11

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

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

11.

For positive integers NN and k,k, define NN to be kk-nice if there exists a positive integer aa such that aka^k has exactly NN positive divisors. Find the number of positive integers less than 10001000 that are neither 77-nice nor 88-nice.

Answer: 749
Concepts:factor countingmodular arithmeticinclusion-exclusion
Difficulty rating: 2990
Solution:

If a=p1m1ptmt,a = p_1^{m_1} \cdots p_t^{m_t}, then aka^k has (km1+1)(km2+1)(km_1 + 1)(km_2 + 1) (kmt+1)\cdots (km_t + 1) positive divisors, and each factor is 1(modk),\equiv 1 \pmod{k}, so the product is too. Conversely, if N=km+1,N = km + 1, then a=pma = p^m gives ak=pkma^k = p^{km} with exactly NN divisors. So NN is kk-nice exactly when N1(modk).N \equiv 1 \pmod{k}.

Among 1,2,,9991, 2, \ldots, 999 there are 143143 integers 1(mod7)\equiv 1 \pmod{7} (namely 1,8,,9951, 8, \ldots, 995) and 125125 integers 1(mod8)\equiv 1 \pmod{8} (namely 1,9,,9931, 9, \ldots, 993). Since lcm(7,8)=56,\operatorname{lcm}(7, 8) = 56, there are 1818 integers 1(mod56)\equiv 1 \pmod{56} (namely 1,57,,9531, 57, \ldots, 953). By inclusion-exclusion, 143+12518=250143 + 125 - 18 = 250 of them are 77-nice or 88-nice.

Hence 999250=749999 - 250 = 749 positive integers less than 10001000 are neither.

← Problem 10#10
Full Exam

Problem 11 in Other Years