HMMT 二月 2024 · COMB 赛 · 第 8 题
HMMT February 2024 — COMB Round — Problem 8
题目详情
- Rishabh has 2024 pairs of socks in a drawer. He draws socks from the drawer uniformly at random, without replacement, until he has drawn a pair of identical socks. Compute the expected number of unpaired socks he has drawn when he stops.
解析
- Rishabh has 2024 pairs of socks in a drawer. He draws socks from the drawer uniformly at random, without replacement, until he has drawn a pair of identical socks. Compute the expected number of unpaired socks he has drawn when he stops. Proposed by: Rishabh Das 2024 4 ( ) Answer: − 2 4048 2024 Solution 1: We solve for the expected number of total socks drawn and subtract two at the end. Let E be the expected number of socks drawn for n pairs of socks, so that E = 2 . Suppose there n 1 are n pairs of socks, Rishabh continued to draw socks until the drawer was empty, and without loss of generality let the last sock drawn be red. If we ignore the two red socks, the process is equivalent to drawing from a drawer with n − 1 pairs of socks. Let k be the number of socks drawn until a pair of k identical socks is found, after ignoring the two red socks. Then the first red sock has probability 2 n − 1 k 2 n of being before this stopping point, so the expected value is k + = k · . Since the expected 2 n − 1 2 n − 1 value of k is E , we have n − 1 2 n E = · E . n n − 1 2 n − 1 Applying this recurrence, we get n n 2 n (2 n )!! 2 · n ! 4 · ( n !) 4 ( ) E = = = = . n 2 n (2 n − 1)!! (2 n − 1)!! (2 n )! n 2024 4 ( ) Subtracting two and plugging in n = 2024 gives a final answer of − 2 . 4048 2024 Solution 2: Let P ( k ) denote the probability that Rishabh draws more than k socks. We compute P ( k ) for all 0 ≤ k ≤ 2024 (and note P ( k ) = 0 for larger k ). The number of ways to draw k socks, none identical to each other, is 2024! k 4048 · 4046 · · · · (4050 − 2 k ) = 2 · , (2024 − k )! while the total number of ways to draw k socks is 4048! 4048 · 4047 · · · (4049 − k ) = . (4048 − k )! Thus, ( ) 2024! k k 2 · 2024! 2 (4048 − k )! 1 4048 − k (2024 − k )! k ( ) P ( k ) = = · = · 2 . 4048! 4048 4048! (2024 − k )! 2024 (4048 − k )! 2024 The expected number of socks drawn is ( ) 2024 ∑ 1 4048 − k k ( ) P (0) + P (1) + · · · + P (2024) = 2 . 4048 2024 2024 k =0 2024 This sum is equivalent to Putnam 2020 A2 . We claim that it is equal to 4 . We do this via a counting argument: we count how many ways there are to choose at least half of the elements from 4049 2 2024 the set { 1 , 2 , . . . , 4049 } . On the one hand that is = 4 . On the other hand, letting k + 1 be 2 ( ) 4048 − k the 2025 th largest element chosen, there are ways to choose the elements larger than it, and 2024 k 2 ways to choose the elements smaller than it. Varying k , we get ( ) 2024 ∑ 4048 − k k 2024 2 = 4 . 2024 k =0 This means the expected number of socks is 2024 4 ( ) , 4048 2024 2024 4 ( ) and subtracting two for the matching pair gives − 2 . 4048 2024