HMMT February, 2022

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

Five cards labeled $1, 3, 5, 7, 9$ are laid in a row in that order, forming the five-digit number $13579$ when read from left to right. A swap consists of picking two distinct cards, and then swapping them. After three swaps, the cards form a new five-digit number $n$ when read from left to right. Compute the expected value of $n$ .

Solution

Solution:

For a given card, let $p(n)$ denote the probability that it is in its original position after $n$ swaps. Then
$p(n+1) = p(n) \cdot \frac{3}{5} + (1 - p(n)) \cdot \frac{1}{10},$
by casework on whether the card is in the correct position or not after $n$ swaps. In particular, $p(0) = 1$ , $p(1) = 3/5$ , $p(2) = 2/5$ , and $p(3) = 3/10$ .

For a certain digit originally occupied with the card labeled $d$ , we see that, at the end of the process, the card at the digit is $d$ with probability $3/10$ and equally likely to be one of the four non- $d$ cards with probability $7/10$ . Thus the expected value of the card at this digit is
$\frac{3d}{10} + \frac{7}{10} \cdot \frac{25 - d}{4} = \frac{12d + 175 - 7d}{40} = \frac{d + 35}{8}$
By linearity of expectation, our final answer is therefore
$\frac{13579 + 35 \cdot 11111}{8} = \frac{402464}{8} = 50308$

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

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