Maths Olympiad Prep

Library / /4 of 4

, 2021

Combinatorics Difficulty 5.8 AIME, harder Find the answer United States

Five balls are arranged around a circle. Chris chooses two adjacent balls at random and interchanges them. Then Silva does the same, with her choice of adjacent balls to interchange being independent of Chris's. What is the expected number of balls that occupy their original positions after these two successive transpositions?

Pick one

Solution

Label the balls in order 1 through 5. Assume without loss of generality that the first transposition is 121 \leftrightarrow 2, resulting in the order 21345. The following table shows the results of the 5 equally likely second transpositions.

2nd transpositionresultballs in original positioncount
2 \leftrightarrow 1123451,2,3,4,55
1 \leftrightarrow 3231454,52
3 \leftrightarrow 42143551
4 \leftrightarrow 52135431
5 \leftrightarrow 2513423,42

The expected number of balls that occupy their original positions is the average of the numbers in the last column, namely 15(5+2+1+1+2)=2.2\frac{1}{5}(5 + 2 + 1 + 1 + 2) = 2.2.

OR

Let XiX_i be the random variable that has the value 1 if ball ii occupies its original position after the two successive transpositions and the value 0 if it does not. The problem asks for the expected value of the sum X1+X2+X3+X4+X5X_1 + X_2 + X_3 + X_4 + X_5, which, by linearity of expectation, is the sum of the expected values. The probability that Xi=1X_i = 1 equals 2515+3535=1125\frac{2}{5} \cdot \frac{1}{5} + \frac{3}{5} \cdot \frac{3}{5} = \frac{11}{25}, because this will happen if ball ii is involved in the first transposition and the second transposition involves the same two balls, or ball ii is involved in neither transposition. Therefore the expected value of each XiX_i is 1125\frac{11}{25}, and the expected value of their sum is 51125=115=2.25 \cdot \frac{11}{25} = \frac{11}{5} = 2.2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.