PUMaC 2017 · 团队赛 · 第 8 题
PUMaC 2017 — Team Round — Problem 8
题目详情
- (6) Tristan is eating his favorite cereal, Tiger Crunch, which has marshmallows of two colors, black and orange. He eats the marshmallows by randomly choosing from those remaining one p at a time, and he starts out with 17 orange and 5 black marshmallows. If is the expected q number of marshmallows remaining the instant that there is only one color left, and p and q are relatively prime positive integers, find p + q . 1
解析
- Suppose there are m orange and n black marshmallows. We compute the probability of there being exactly k marshmallows of a given color the instant that color is the only one remaining. WLOG orange. First, we compute the probability of arriving at k orange and 1 black (this 1 is the state right before our desired state); then we multiply by . We need to take m − k k +1 ( ) m + n − k − 1 orange marshmallows and n − 1 black marshmallows in some order. There are ways m − k to do this. We then multiply this by m ( m − 1) · · · · · ( k + 1) = m ! /k ! and n ( n − 1) · · · · · 2 = n ! ( k +1)! 1 1 1 the denominator of this probability, · · · · · · = . This comes out with m + n m + n − 1 k +2 ( m + n )! m + n − k − 1 ( ) ( ) m ! n !( k +1)! m + n − k − 1 n − 1 = ( k + 1) . Multiplying by the probability of then choosing the m + n k !( m + n )! n − 1 ( ) m m + n − k − 1 ( ) n − 1 last remaining black marshmallow gives . The weight for the expectation is thus m + n ( ) m m + n − k − 1 ( ) n − 1 k . m + n ( ) m Using symmetry in the system to compute the case for black, we find ( ) ( ) ( ) ( ) ( ) m m + n − k − 1 n m + n − k − 1 m n ∑ ∑ ∑ ∑ 1 m + n − k − 1 m + n − k − 1 n − 1 m − 1 ( ) ( ) ( ) E = k + k = k + k m + n m + n m + n n − 1 m − 1 m m m k =1 k =1 k =1 k =1 and by the Hockey Stick Identity, (( ) ( )) 1 m + n m + n m n 28 ( ) E = + = + = , m + n n + 1 m + 1 n + 1 m + 1 9 m so the final answer is 37 . Problem written by Zack Stier