Difference between revisions of "1996 AIME Problems/Problem 12"
Talkinaway (talk | contribs) (→Solution) |
(→Solution 1) |
||
(9 intermediate revisions by 5 users not shown) | |||
Line 23: | Line 23: | ||
<cmath>2\sum\limits_{k = 1}^{9}\sum\limits_{j = 1}^{k}j = 330</cmath> | <cmath>2\sum\limits_{k = 1}^{9}\sum\limits_{j = 1}^{k}j = 330</cmath> | ||
− | The total number of permutations is <math>10!</math>, so the average value is <math>\frac {330 \cdot 8! \cdot 5}{10!} = \frac {55}{3}</math>, and <math>m+n = \boxed{058}</math>. | + | The total number of permutations is <math>10!</math>, so the average value is <math>\frac {330 \cdot 8! \cdot 5}{10!} = \frac {55}{3}</math>, and <math>m+n = \boxed{058}</math>. |
+ | |||
+ | Note from SuperJJ: Another way to think about this is that the total sum is 330. Because you have a total of <math>10 \cdot 9</math> possible "pairs" or "differences", the average difference is <math>\frac{330}{90} = \frac{11}{3}</math>. Because the question asks for the expected value of the sum of <math>5</math> of these pairs / differences, our answer is just <math>\frac{11}{3} \cdot 5 = {\frac{55}{3}}</math>. | ||
=== Solution 2 === | === Solution 2 === | ||
Line 40: | Line 42: | ||
===Solution 3 === | ===Solution 3 === | ||
− | Similar to Solution 1, we can find the average value of <math>|a_2 - a_1|</math>, and multiply this by 5 due to symmetry. And again due to symmetry, we can arbitrarily choose <math>a_2 > a_1</math>. Thus there are <math>45</math> ways to pick the two values of <math>a_2</math> and <math>a_1</math>, and the sum of these <math>45</math> ways is: | + | Similar to Solution 1, we can find the average value of <math>|a_2 - a_1|</math>, and multiply this by 5 due to symmetry. And again due to symmetry, we can arbitrarily choose <math>a_2 > a_1</math>. Thus there are <math>\binom{10}{2} = 45</math> ways to pick the two values of <math>a_2</math> and <math>a_1</math> from the set <math>\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}</math> such that <math>a_2 > a_1</math>. First fix <math>a_2 = 10</math>, and vary <math>a_1</math> from <math>1</math> to <math>9</math>. Then fix <math>a_2 = 9</math>, and vary <math>a_1</math> from <math>1</math> to <math>8</math>. Continue, and you find that the sum of these <math>45</math> ways to pick <math>|a_2 - a_1|</math> is: |
<math>\sum\limits_{k = 1}^{9}\sum\limits_{j = 1}^{k}j = 45+36+28+21+15+10+6+3+1 = 165</math>. | <math>\sum\limits_{k = 1}^{9}\sum\limits_{j = 1}^{k}j = 45+36+28+21+15+10+6+3+1 = 165</math>. | ||
Line 46: | Line 48: | ||
Thus, each term contributes on average <math>\frac{165}{45}</math>, and the sum will be five times this, or <math>\frac{165}{9} = \frac{55}{3}</math>. | Thus, each term contributes on average <math>\frac{165}{45}</math>, and the sum will be five times this, or <math>\frac{165}{9} = \frac{55}{3}</math>. | ||
− | The final answer is <math> | + | The final answer is <math>p+q = \boxed{058}</math>. |
+ | |||
+ | ===Solution 4(Expected Value)=== | ||
+ | We use expected value of one of the sums, say <math>|a_2 - a_1|</math>, since all five are similar, so the average or expected value of the sum is just 5 times the expected value of one of them. | ||
+ | |||
+ | To pick two random expected numbers from 1 to 10, we use a well known expected value trick by tying the two ends 1 and 10 with an extra number 0.* This gives 11 spaces, and we distribute 3 gaps evenly to choose our two numbers. We get <math>\frac{11}{3}</math> and <math>\frac{22}{3}</math> giving an absolute difference of <math>\frac{11}{3}</math>. Therefore, the average/expected value of the sum of the five would be <math>\frac{55}{3}</math>. This gives <math>55+3=\boxed{058}</math>. | ||
+ | |||
+ | *This is like a bendable stick that has equally spaced marks "end-1-2-3-4-5-6-7-8-9-10-end", and the ends are bent together giving a circle with 11 equally spaced marks(the ends produce 1 mark together). | ||
== See also == | == See also == | ||
Line 52: | Line 61: | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 11:23, 5 September 2021
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
.
Note from SuperJJ: Another way to think about this is that the total sum is 330. Because you have a total of possible "pairs" or "differences", the average difference is
. Because the question asks for the expected value of the sum of
of these pairs / differences, our answer is just
.
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 .
Solution 3
Similar to Solution 1, we can find the average value of , and multiply this by 5 due to symmetry. And again due to symmetry, we can arbitrarily choose
. Thus there are
ways to pick the two values of
and
from the set
such that
. First fix
, and vary
from
to
. Then fix
, and vary
from
to
. Continue, and you find that the sum of these
ways to pick
is:
.
Thus, each term contributes on average , and the sum will be five times this, or
.
The final answer is .
Solution 4(Expected Value)
We use expected value of one of the sums, say , since all five are similar, so the average or expected value of the sum is just 5 times the expected value of one of them.
To pick two random expected numbers from 1 to 10, we use a well known expected value trick by tying the two ends 1 and 10 with an extra number 0.* This gives 11 spaces, and we distribute 3 gaps evenly to choose our two numbers. We get and
giving an absolute difference of
. Therefore, the average/expected value of the sum of the five would be
. This gives
.
- This is like a bendable stick that has equally spaced marks "end-1-2-3-4-5-6-7-8-9-10-end", and the ends are bent together giving a circle with 11 equally spaced marks(the ends produce 1 mark together).
See also
1996 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
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.