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 .
When computing , the number will be added times (for terms , , ..., ), and subtracted times. Hence can be computed as .
We can now simply evaluate . One reasonably simple way:
In this solution we show a more general approach that can be used even if were replaced by a larger value.
As in Solution 1, we show that .
Let and let . Then obviously .
Computing is easy, as this is simply a geometric series with sum . Hence .
We can compute using a trick known as the change of summation order.
Imagine writing down a table that has rows with labels 0 to 10. In row , write the number into the first columns. You will get a triangular table. Obviously, the row sums of this table are of the form , and therefore the sum of all the numbers is precisely .
Now consider the ten columns in this table. Let's label them 1 to 10. In column , you have the values to , each of them once. And this is just a geometric series with the sum . We can now sum these column sums to get . Hence we have . This simplifies to .
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|