Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1996 AIME Problems/Problem 12"

(→‎Problem)
(solutions, (1) by agolsme)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
For each permutation <math>a_1,a_2,a_3,\cdots,a_{10}</math> of the integers <math>1,2,3,\cdots,10</math>, form the sum
+
For each [[permutation]] <math>a_1,a_2,a_3,\cdots,a_{10}</math> of the integers <math>1,2,3,\cdots,10</math>, form the sum
  
−
<math>|a_1-a_2|+|a_3-a_4|+|a_5-a_6|+|a_7-a_8|+|a_9-a_{10}|</math>.
+
<cmath>|a_1-a_2|+|a_3-a_4|+|a_5-a_6|+|a_7-a_8|+|a_9-a_{10}|.</cmath>
  
−
The average value of all such sums can be written in the form <math>\dfrac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
+
The [[average (Arithmetic)|average]] value of all such sums can be written in the form <math>\dfrac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
  
 +
__TOC__
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
=== Solution 1 ===
 +
Because of symmetry, we may find all the possible values for <math>|a_n - a_{n - 1}|</math> and multiply by the number of times this value appears. Each occurs <math>5 \cdot 8!</math>, because if you fix <math>a_n</math> and <math>a_{n + 1}</math> there are still <math>8!</math> spots for the others and you can do this <math>5</math> times because there are <math>5</math> places <math>a_n</math> and <math>a_{n + 1}</math> can be.
 +
 
 +
To find all possible values for <math>|a_n - a_{n - 1}|</math> we have to compute <math>|1 - 10| + |1 - 9| + \ldots + |1 - 2| + |2 - 1| + |2 - 3| + \ldots + |2 - 10| + \ldots + |10 - 9|</math>.
 +
 
 +
This is equivalent to
 +
 
 +
<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>.
 +
 
 +
=== Solution 2 ===
 +
[[Without loss of generality]], let <math>a_1 > a_2;\, a_3 > a_4;\, \ldots ;\, a_9 > a_{10}</math>. We may do this because all sums obtained from these paired sequences are also obtained in another <math>2^5-1</math> ways by permuting the adjacent terms <math>\{a_1,a_2\},\{a_3,a_4\}, \cdots , \{a_9, a_{10}\}</math>, and thus are canceled when the average is taken.
 +
 
 +
So now we only have to form the sum <math>S= (a_1 + a_3 + a_5 + a_7 + a_9) - (a_2 + a_4 + a_6 + a_8 + a_{10})</math>. Due to the symmetry of this situation, we only need to compute the [[expected value]] of the result. <math>10</math> must always be the greatest number in its pair; <math>9</math> will be the greater number in its pair <math>\frac{8}{9}</math>
 +
of the time and the lesser number <math>\frac 19</math> of the time; <math>8</math> will be the greater number in its pair <math>\frac 79</math> of the time and the lesser <math>\frac 29</math> 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
 +
 
 +
<cmath>\begin{align*}
 +
\overline{S} &= 10 + \left(\frac{8}{9} \cdot 9\right) - \left(\frac{1}{9} \cdot 9\right) + \left(\frac{7}{9} \cdot 8\right) - \left(\frac 29 \cdot 8\right) + \cdots + \left(\frac{1}{9} \cdot 2\right) - \left(\frac{8}{9} \cdot 2\right) - 1 \\
 +
&= \frac{9 \cdot 10 + 7 \cdot 9 + 5 \cdot 8 + 3 \cdot 7 + 1 \cdot 6 - 1 \cdot 5 - 3 \cdot 4 - 5 \cdot 3 - 7 \cdot 2 - 9 \cdot 1}{9} \\
 +
&= \frac{55}{3}
 +
\end{align*}</cmath>
 +
 
 +
And the answer is <math>m+n = \boxed{058}</math>.
 +
 
 
== See also ==
 
== See also ==
−
*[[1996 AIME Problems]]
+
{{AIME box|year=1996|num-b=11|num-a=13|t=394253}}
  
−
{{AIME box|year=1996|num-b=11|num-a=13}}
+
[[Category:Intermediate Combinatorics Problems]]

Revision as of 14:57, 29 July 2008

Problem

For each permutation $a_1,a_2,a_3,\cdots,a_{10}$ of the integers $1,2,3,\cdots,10$, form the sum

\[|a_1-a_2|+|a_3-a_4|+|a_5-a_6|+|a_7-a_8|+|a_9-a_{10}|.\]

The average value of all such sums can be written in the form $\dfrac{p}{q}$, where $p$ and $q$ are relatively prime positive integers. Find $p+q$.

Solution

Solution 1

Because of symmetry, we may find all the possible values for $|a_n - a_{n - 1}|$ and multiply by the number of times this value appears. Each occurs $5 \cdot 8!$, because if you fix $a_n$ and $a_{n + 1}$ there are still $8!$ spots for the others and you can do this $5$ times because there are $5$ places $a_n$ and $a_{n + 1}$ can be.

To find all possible values for $|a_n - a_{n - 1}|$ we have to compute $|1 - 10| + |1 - 9| + \ldots + |1 - 2| + |2 - 1| + |2 - 3| + \ldots + |2 - 10| + \ldots + |10 - 9|$.

This is equivalent to

\[2\sum\limits_{k = 1}^{9}\sum\limits_{j = 1}^{k}j = 330\]

The total number of permutations is $10!$, so the average value is $\frac {330 \cdot 8! \cdot 5}{10!} = \frac {55}{3}$, and $m+n = \boxed{058}$.

Solution 2

Without loss of generality, let $a_1 > a_2;\, a_3 > a_4;\, \ldots ;\, a_9 > a_{10}$. We may do this because all sums obtained from these paired sequences are also obtained in another $2^5-1$ ways by permuting the adjacent terms $\{a_1,a_2\},\{a_3,a_4\}, \cdots , \{a_9, a_{10}\}$, and thus are canceled when the average is taken.

So now we only have to form the sum $S= (a_1 + a_3 + a_5 + a_7 + a_9) - (a_2 + a_4 + a_6 + a_8 + a_{10})$. Due to the symmetry of this situation, we only need to compute the expected value of the result. $10$ must always be the greatest number in its pair; $9$ will be the greater number in its pair $\frac{8}{9}$ of the time and the lesser number $\frac 19$ of the time; $8$ will be the greater number in its pair $\frac 79$ of the time and the lesser $\frac 29$ 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

\begin{align*} \overline{S} &= 10 + \left(\frac{8}{9} \cdot 9\right) - \left(\frac{1}{9} \cdot 9\right) + \left(\frac{7}{9} \cdot 8\right) - \left(\frac 29 \cdot 8\right) + \cdots + \left(\frac{1}{9} \cdot 2\right) - \left(\frac{8}{9} \cdot 2\right) - 1 \\ &= \frac{9 \cdot 10 + 7 \cdot 9 + 5 \cdot 8 + 3 \cdot 7 + 1 \cdot 6 - 1 \cdot 5 - 3 \cdot 4 - 5 \cdot 3 - 7 \cdot 2 - 9 \cdot 1}{9} \\ &= \frac{55}{3} \end{align*}

And the answer is $m+n = \boxed{058}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_AIME_Problems/Problem_12&oldid=27241"