HMMT 二月 2022 · COMB 赛 · 第 5 题

HMMT February 2022 — COMB Round — Problem 5

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 .

解析

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 . Proposed by: Sean Li Answer: 50308 Solution: For a given card, let p ( n ) denote the probability that it is in its original position after n 3 1 swaps. Then p ( n + 1) = p ( n ) · + (1 − p ( n )) · , by casework on whether the card is in the correct 5 10 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 3 d 7 25 − d 12 d + 175 − 7 d d + 35

= = . 10 10 4 40 8 By linearity of expectation, our final answer is therefore 13579 + 35 · 11111 402464 = = 50308 . 8 8