2009 AIME I Problems/Problem 8
Let . Consider all possible positive differences of pairs of elements of . Let be the sum of all of these differences. Find the remainder when is divided by .
Solution 1 (Extreme bash)
Find the positive differences in all pairs and you will get . (This is not recommended unless you can't find any other solutions to this problem)
Solution 2 (bash)
When computing , the number will be added times (for terms , , ..., ), and subtracted times. Hence can be computed as . Evaluating yields:
This solution can be generalized to apply when is replaced by other positive integers.
Extending from Solution 2, we get that the sum of all possible differences of pairs of elements in when is equal to . Let , . Then .
For , by the geometric sequence formula.
, so . Hence, for ,
, by the geometric sequence formula and the fact that .
Thus, for , .
Consider the unique differences . Simple casework yields a sum of . This method generalizes nicely as well.
|2009 AIME I (Problems • Answer Key • Resources)|
|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.