Find the average value!

For each permutation a 1 , a 2 , . . . , a 10 a_1, a_2, . . . , a_{10} of the integers 1 , 2 , 3 , . . . , 10 1, 2, 3, . . . , 10 , form the sum a 1 a 2 + a 3 a 4 + a 5 a 6 + a 7 a 8 + a 9 a 10 . |a_1 - a_2| + |a_3 - a_4| + |a_5 - a_6| + |a_7 - a_8| + |a_9 - a_{10}|. Find the average value of all such sums correct up to 2 decimal places.

This is the part of Combinatorics


The answer is 18.34.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Chew-Seong Cheong
Jul 16, 2015

Let the average value of a i a j |a_i-a_j| be n \overline{n} . Then, the average value of a 1 a 2 + a 3 a 4 + a 5 a 6 + a 7 a 8 + a 9 a 10 |a_1-a_2| + |a_3-a_4| + |a_5-a_6| + |a_7-a_8| + |a_9-a_{10}| is 5 n 5\overline{n} . Let n k n_k be the number of a i a j = k |a_i-a_j| = k .

For k = 1 k=1 , we have ± 1 2 |\pm 1\mp 2| , ± 2 3 |\pm 2\mp 3| , ± 3 4 |\pm 3\mp 4| , ± 4 5 |\pm 4\mp 5| , ± 5 6 |\pm 5\mp 6| , ± 6 7 |\pm 6\mp 7| , ± 7 8 |\pm 7\mp 8| , ± 8 9 |\pm 8\mp 9| and ± 9 10 |\pm 9\mp 10| . Therefore, n 1 = 18 n_1 = 18 . Similarly, n 2 = 16 n_2 = 16 , n 3 = 14 n_3 = 14 , n k = 2 ( 10 k ) \Rightarrow n_k = 2(10-k) .

We know that n \overline{n} is the expected value of n k n_k and it is given by:

n = k = 1 9 k n k k = 1 9 n k = k = 1 9 2 k ( 10 k ) k = 1 9 2 ( 10 k ) = k = 1 9 k ( 10 k ) k = 1 9 k = 10 k = 1 9 k 2 k = 1 9 k = 10 9 ( 10 ) ( 19 ) 6 × 2 9 ( 10 ) = 10 19 3 = 11 3 \begin{aligned} \overline{n} & = \dfrac{\displaystyle \sum_{k=1}^9 k n_k} {\displaystyle \sum _{k=1} ^9 n_k} = \dfrac{\displaystyle \sum_{k=1}^9 2k(10-k)} {\displaystyle \sum _{k=1} ^9 2(10-k)} = \dfrac{\displaystyle \sum_{k=1}^9 k(10-k)} {\displaystyle \sum _{k=1} ^9 k} = 10 - \dfrac{\displaystyle \sum_{k=1}^9 k^2} {\displaystyle \sum _{k=1} ^9 k} \\ & = 10 - \frac{9(10)(19)}{6} \times \frac{2}{9(10)} = 10 - \frac{19}{3} = \frac{11}{3} \end{aligned}

Therefore, the required answer 5 n = 5 × 11 3 = 18.33 5\overline{n} = 5 \times \dfrac{11}{3} = \boxed{18.33} to two decimal places.

Moderator note:

There is a simpler (?) solution based on the ideas of the linearity of expectation, which you have tangentially touched on.

The expected contribution of 10 is clearly 10, since it would always be positive added. The expected contribution of 9 is 8 9 × 9 + 1 9 × ( 9 ) \frac{8}{9} \times 9 + \frac{1}{9} \times ( - 9 ) , because it will only be negatively added when paired with 10. This results in the sum that you stated.

The difference lies in thinking about a 1 a 2 |a_1 - a_2| as ± ( a 1 a 2 ) \pm ( a_1 - a_2 ) , as opposed to counting the number of times that a 1 a 2 = k |a_1 - a_2| = k occurs.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...