2000 AIME I Problems/Problem 11
Contents
[hide]Problem
Let be the sum of all numbers of the form where and are relatively prime positive divisors of What is the greatest integer that does not exceed ?
Solution 1
Since all divisors of can be written in the form of , it follows that can also be expressed in the form of , where . Thus every number in the form of will be expressed one time in the product
Using the formula for a geometric series, this reduces to , and .
Solution 2
Essentially, the problem asks us to compute which is pretty easy: so our answer is .
Solution 3
The sum is equivalent to Therefore, it's the sum of the factors of divided by . The sum is by the sum of factors formula. The answer is therefore after some computation. - whatRthose
Solution 4 (head on)
We can organize the fractions and reduce them in quantities to reach our answer. First, separate the fractions with coprime parts into those that are combinations of powers of 2 and 5, and those that are a combination of a 1 and another divisor.
To begin with the first list, list powers of 2 and 5 from 0 to 3. In this specific case I find it easier to augment every denominator to 1000 and then divide by 1000. To do this, write the corresponding divisor under each power. e.g. 2 - 500, 4 - 250, 5 - 200, etc. Call this the "partner" of any divisor.
Now we now the amount to multiply the numerator if given number is in the denominator. Now we simply combine and reduce these groups. If the powers of 2 are on the denominator, then every power of five will be multiplied by the partner of the power of 2. Essentially, all we have to do is a large scale distributive property application. There is nothing complicated about this except to be careful.
Add all powers of 2: 15
Add their partners: 1875
Add all powers of 5: 156
Add their partners: 1248
Then, follow this formula: (sum of powers * sum opposite power's partners)+(sum of powers * sum opposite power's partners)
Or,
Now, divide by 1000 to compensate for the denominator.
Finally, we have to calculate the other list of fractions with 1 and another divisor. e.g. 1 - 250, 1 - 20 etc. (these all count)
This time we need to list all divisors of 1000, including 1. Remove all powers of 2 or 5, because we already included those in the other list. Now, notice there are two cases. 1: 1 is in the denominator, making the fraction an integer. 2: 1 is in the numerator.
Adding all the integers in the first case gives us 2169. The second case can actually be discarded, but still can be found. Realize that if we include the powers of 2 and 5, then the second case is (sum of all divisors)/1000. Remove all partners of powers of 2 and 5, and we'll get exactly 217/1000, or 0.22.
Finally, add all the numbers together:
And divide by 10:
After an odyssey of bashing:
-jackshi2006
Solution 5 (less brain)
Since is relatively prime to everything, including itself, we start with . The numerators will be all factors of 1000, and the sum of the factors of 1000 is .
If the denominator is in the form , then the numerator must be in the form . The sum of the possible numerators is , so the sum of all such fractions with denominator is
If the denominator is in the form , then the numerator must be in the form . The sum of the possible numerators is , so the sum of all such fractions with denominator is , which is around .
If the denominator is in the form , where and , the numerator must be . We can get the sum of all such fractions from .
Adding, we get , with a bit extra, so our answer is .
~skibbysiggy
See also
2000 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.