2000 AIME I Problem 11

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

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

11.

Let SS be the sum of all numbers of the form ab,\frac{a}{b}, where aa and bb are relatively prime positive divisors of 1000.1000. What is the greatest integer that does not exceed S10?\frac{S}{10}?

Answer: 248
Concepts:factorprime factorizationgeometric sequence
Difficulty rating: 2450
Solution:

Write a=2i5ja = 2^i 5^j and b=2k5lb = 2^k 5^l with exponents between 00 and 3.3. Coprimality means min(i,k)=0\min(i, k) = 0 and min(j,l)=0,\min(j, l) = 0, and these two constraints are independent. So as (a,b)(a, b) runs over all coprime pairs, the factor 2ik2^{i - k} independently takes each value in {23,,23}\{2^{-3}, \ldots, 2^{3}\} exactly once, and similarly for 5jl.5^{j - l}. Hence S=(1+2+4+8+12+14+18)(1+5+25+125+15+125+1125)=127819531125. \begin{aligned} S &= \scriptsize \left(1 + 2 + 4 + 8 + \tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8}\right) \\ &\quad \scriptsize {}\cdot \left(1 + 5 + 25 + 125 + \tfrac{1}{5} + \tfrac{1}{25} + \tfrac{1}{125}\right) \\ &= \frac{127}{8} \cdot \frac{19531}{125}. \end{aligned}

This equals 24804371000=2480.437,\frac{2480437}{1000} = 2480.437, so S10=248.0437,\frac{S}{10} = 248.0437, and the greatest integer not exceeding it is 248.248.

← Problem 10#10
Full Exam

Problem 11 in Other Years