HMMT 十一月 2020 · 团队赛 · 第 9 题

HMMT November 2020 — Team Round — Problem 9

[55] Alice and Bob take turns removing balls from a bag containing 10 black balls and 10 white balls, with Alice going first. Alice always removes a black ball if there is one, while Bob removes one of the remaining balls uniformly at random. Once all balls have been removed, the expected number of a black balls which Bob has can be expressed as , where a and b are relatively prime positive integers. b Compute 100 a + b .

解析

[55] Alice and Bob take turns removing balls from a bag containing 10 black balls and 10 white balls, with Alice going first. Alice always removes a black ball if there is one, while Bob removes one of the remaining balls uniformly at random. Once all balls have been removed, the expected number of a black balls which Bob has can be expressed as , where a and b are relatively prime positive integers. b Compute 100 a + b . Proposed by: Benjamin Qi Answer: 4519 Solution: Suppose a is the number of black balls and b is the number of white balls, and let E a,b denote the expected number of black balls Bob has once all the balls are removed with Alice going first. Then we want to find E . It is evident that if E = 0. Also, since Bob chooses a black ball 10 , 10 0 ,b a − 1 with probability , if a > 0 we have a + b − 1 a − 1 b E = ( E + 1) + E a,b a − 2 ,b a − 1 ,b − 1 a + b − 1 a + b − 1 ( a − 1)( E + 1) + bE a − 2 ,b a − 1 ,b − 1 = a + b − 1 a ( a − 1) 45 We claim that E = , which will yield an answer of . To prove this, we use induction. In a,b 2( a + b − 1) 19 a ( a − 1) the base case of a = 0 we find = 0, as desired. Also, for a > 0 we have that by the inductive 2( a + b − 1) hypothesis ( a − 1)(( a − 2)( a − 3) + 2( a + b − 3)) + b ( a − 1)( a − 2) E = a,b 2( a + b − 1)( a + b − 3) ( a − 1)( a − 2)( a + b − 3) + 2( a − 1)( a + b − 3) = 2( a + b − 1)( a + b − 3) a ( a − 1) = , 2( a + b − 1) as desired.