HMMT 二月 2021 · 冲刺赛 · 第 31 题

HMMT February 2021 — Guts Round — Problem 31

[18] Roger initially has 20 socks in a drawer, each of which is either white or black. He chooses a sock uniformly at random from the drawer and throws it away. He repeats this action until there are equal numbers of white and black socks remaining. Suppose that the probability he stops before all socks are gone is p . If the sum of all distinct possible a values of p over all initial combinations of socks is for relatively prime positive integers a and b , compute b 100 a + b .

解析

[18] Roger initially has 20 socks in a drawer, each of which is either white or black. He chooses a sock uniformly at random from the drawer and throws it away. He repeats this action until there are equal numbers of white and black socks remaining. Suppose that the probability he stops before all socks are gone is p . If the sum of all distinct possible a values of p over all initial combinations of socks is for relatively prime positive integers a and b , b compute 100 a + b . Proposed by: Michael Diao Answer: 20738 Solution: Let b and w be the number of black and white socks left after i socks have been thrown i i out. In particular, b + w = 20. 0 0 b i The key observation is that the ratio r = is a martingale (the expected value of r given r is i i +1 i b + w i i just r ). i Suppose WLOG that b < w (we will deal with the case b = w later). Say that we stop at i if b = 0 0 0 0 0 i or b = w . Then the expected value of r when we stop is i i i 1 b 0 · p + 0 · (1 − p ) = 2 b + w 0 0 2 b 0 This rearranges to p = . b + w 0 0 Meanwhile, if b = w = 10, we can reduce to the case b = 9 < 10 = w . Hence 0 0 1 1 ( ) 10 9 ∑ ∑ 2 b 18 9 18 207 0 p = + = + = . 20 19 2 19 38 b =0 b 0 0