1996 AIME Problems/Problem 12
From AoPSWiki
Problem
For each permutation 
of the integers 
, form the sum
The average value of all such sums can be written in the form 
, where 
and 
are relatively prime positive integers. Find 
.
Contents |
Solution
Solution 1
Because of symmetry, we may find all the possible values for 
and multiply by the number of times this value appears. Each occurs 
, because if you fix 
and 
there are still 
spots for the others and you can do this 
times because there are places and can be.
To find all possible values for we have to compute
This is equivalent to
The total number of permutations is 
, so the average value is 
, and 
.
Solution 2
Without loss of generality, let 
. We may do this because all sums obtained from these paired sequences are also obtained in another 
ways by permuting the adjacent terms 
, and thus are canceled when the average is taken.
So now we only have to form the sum 
. Due to the symmetry of this situation, we only need to compute the expected value of the result. 
must always be the greatest number in its pair; 
will be the greater number in its pair 
of the time and the lesser number 
of the time; 
will be the greater number in its pair 
of the time and the lesser 
of the time; and so forth. Each number either adds or subtracts from the sum depending upon whether it is one of the five greater or five lesser numbers in the pairs, respectively. Thus
And the answer is .
See also
| 1996 AIME (Problems • Resources) | ||
| Preceded by Problem 11 | Followed by Problem 13 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
