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
Small Hint:

Since 1000=23531000 = 2^3 5^3 and a,ba, b are coprime, the prime 22 appears in at most one of them, and likewise for 55

Big Hint:

So SS factors as (1+2+4+8+12+14+18)\left(1 + 2 + 4 + 8 + \frac12 + \frac14 + \frac18\right) times the analogous sum with 55s

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