PUMaC 2017 · 团队赛 · 第 17 题
PUMaC 2017 — Team Round — Problem 17
题目详情
- (14) Zack keeps cutting the interval [0 , 1] of the number line, each time cutting at a uniformly random point in the interval, until the interval is cut into pieces, none of which have length p 3 greater than . The expected number of cuts that Zack makes can be written as for p and 5 q q relatively prime positive integers. Find p + q . 2
解析
- We wish to compute E = 1 · P [1] + 2 · P [2] + . . . , where P [ n ] is the probability that exactly n 3 points were necessary for none of the gaps to be greater than and n − 1 were insufficient. 5 We can rewrite this as E = P [ ≥ 1] + P [ ≥ 2] + . . . where P [ ≥ n ] is the probability that at least 3 n points were necessary for none of the gaps to be greater than and n − 1 were insufficient. 5 3 Fix n and let a be the rightmost value to the left of the -length gap among the first n − 1 points 5 3 selected (we know there is only one because 2 · > 1). We look to evaluate the probability 5 that the n th point lies If that were the case, it would lie in some small neighborhood to the right of a , of length da . If there are k − 1 points to the left of a there are n − k to the ( ) ( ( )) n − k n − 1 3 k − 1 right; so we find that this occurs with probability a 1 − a + nda (the factor k − 1 5 of n comes from symmetry – this argument could apply to any of the n points). Summing n ( ) ( ( )) ( ) ∑ n − k n − 1 n − 1 k − 1 3 3 gets a 1 − a + nda = n 1 − da and adding up over all possible k − 1 5 5 k =1 values of a gets the rudimentary integral (since the integrand is in fact a constant in a ) ∫ 3 ( ) ( ) ( ) n − 1 n n 1 − 3 3 3 5 n 1 − da = n 1 − . We add in another 1 − to account for the case in 0 5 5 5 ( ) n 3 which all n − 1 points lie to the right. This gets P [ ≥ n ] = ( n + 1) 1 − . Thus: 5 ( ) ∞ n ∑ 3 1 25 E = ( n + 1) 1 − = = ( ) 2 3 5 9 n =0 5 so our final answer is 34 . If you believe that any of these answers is incorrect, or that a problem had multiple reasonable interpretations or was incorrectly stated, you may appeal at http://tinyurl.com/PUMaCappeal2017. All appeals must be in by 1 PM to be considered. 6