Difference between revisions of "2000 AIME I Problems/Problem 11"

Problem

Let $S$ be the sum of all numbers of the form $a/b,$ where $a$ and $b$ are relatively prime positive divisors of $1000.$ What is the greatest integer that does not exceed $S/10$?

Solution 1

Since all divisors of $1000 = 2^35^3$ can be written in the form of $2^{m}5^{n}$, it follows that $\frac{a}{b}$ can also be expressed in the form of $2^{x}5^{y}$, where $-3 \le x,y \le 3$. Thus every number in the form of $a/b$ will be expressed one time in the product

$$(2^{-3} + 2^{-2} + 2^{-1} + 2^{0} + 2^{1} + 2^2 + 2^3)(5^{-3} + 5^{-2} +5^{-1} + 5^{0} + 5^{1} + 5^2 + 5^3)$$

Using the formula for a geometric series, this reduces to $S = \frac{2^{-3}(2^7 - 1)}{2-1} \cdot \frac{5^{-3}(5^{7} - 1)}{5-1} = \frac{127 \cdot 78124}{4000} = 2480 + \frac{437}{1000}$, and $\left\lfloor \frac{S}{10} \right\rfloor = \boxed{248}$.

Solution 2

Essentially, the problem asks us to compute $$\sum_{a=-3}^3 \sum_{b=-3}^3 \frac{2^a}{5^b}$$ which is pretty easy: $$\sum_{a=-3}^3 \sum_{b=-3}^3 \frac{2^a}{5^b} = \sum_{a=-3}^3 2^a \sum_{b=-3}^3 \frac{1}{5^b} = \sum_{a=-3}^3 2^a 5^{3}\bigg( \frac{1-5^{-7}}{1-\frac{1}{5}} \bigg) = 5^{3}\bigg( \frac{1-5^{-7}}{1-\frac{1}{5}} \bigg) \sum_{a=-3}^3 2^a = 5^{3}\bigg( \frac{1-5^{-7}}{1-\frac{1}{5}} \bigg)2^{-3} \bigg( \frac{1-2^7}{1-2} \bigg) = 2480 + \frac{437}{1000}$$ so our answer is $\left\lfloor \frac{2480 + \frac{437}{1000}}{10} \right\rfloor = \boxed{248}$.