2000 AIME I Problem 11

Below is the professionally curated solution for Problem 11 of the 2000 AIME I, 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 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:factorprime factorizationgeometric sequence

Difficulty rating: 2450

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}?

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.S = \left(1 + 2 + 4 + 8 + \tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8}\right) \left(1 + 5 + 25 + 125 + \tfrac{1}{5} + \tfrac{1}{25} + \tfrac{1}{125}\right) = \frac{127}{8} \cdot \frac{19531}{125}.

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 10Full ExamProblem 12

Problem 11 in Other Years