2009 AIME I Problems/Problem 8
Contents
Problem
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 (bash)
When computing , the number
will be added
times (for terms
,
, ...,
), and subtracted
times. Hence
can be computed as
. Evaluating
yields:
Solution 2
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 ,
.
Solution 3
Consider the unique differences . Simple casework yields a sum of
. This method generalizes nicely as well.
Solution 4 (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)
See also
2009 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
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.