PUMaC 2020 · 团队赛 · 第 2 题
PUMaC 2020 — Team Round — Problem 2
题目详情
- Gary is baking cakes, one at a time. However, Gary’s not been having much success, and each failed cake will cause him to slowly lose his patience, until eventually he gives up. Initially, a 1 failed cake has a probability of 0 of making him give up. Each cake has a of turning out 2 well, with each cake independent of every other cake. If two consecutive cakes turn out well, the probability resets to 0 immediately after the second cake. On the other hand, if the cake fails, assuming that he doesn’t give up at this cake, his probability of breaking on the next failed cake goes from p to p + 0 . 5 . If the expected number of successful cakes Gary will bake p until he gives up is , for relatively prime p, q, find p + q. q a b
解析
- Gary is baking cakes, one at a time. However, Gary’s not been having much success, and each failed cake will cause him to slowly lose his patience, until eventually he gives up. Initially, a 1 failed cake has a probability of 0 of making him give up. Each cake has a of turning out 2 well, with each cake independent of every other cake. If two consecutive cakes turn out well, the probability resets to 0 immediately after the second cake. On the other hand, if the cake fails, assuming that he doesn’t give up at this cake, his probability of breaking on the next failed cake goes from p to p + 0 . 5 . If the expected number of successful cakes Gary will bake p until he gives up is , for relatively prime p, q, find p + q. q Proposed by: Frank Lu Answer: 86 Let f ( p, c ) be the function giving the expected number of cakes Gary will bake until he gives up, given that his probability of giving up after the next failed cake is currently p, and his last c cakes were successful. 1 1 1 1 1 Now, note that f ( p, 0) = + (1 − p ) f ( p + 0 . 5 , 0) + f ( p, 1) , and f ( p, c ) = + (1 − p ) f ( p + 2 2 2 2 2 1 0 . 5 , 0) + f (0 , c + 1) for c ≥ 1 . Note that this equation is not defined for c > 1 if p 6 = 0 , and 2 both equations are only defined for 0 ≤ p ≤ 0 . 9 . For p = 1 , we see that the first equation is 1 1 now f (1 , 0) = (1 + f (1 , 1)) , and the second equation is f (1 , 1) = (1 + f (0 , 2)) . 2 2 We also observe that f (0 , c ) is constant for c ≥ 2 , since Gary’s probability of giving up at a given time depends only on the last two cakes he attempted to bake, as well as his probability of giving up right before baking his last cake (so Gary baking more than 2 successes in the row doesn’t alter the expected number of cakes he bakes afterwards). Thus, we see that f (0 , c ) = 1 + f (0 . 5 , 0) for c ≥ 2 , from the second equation. 3 3 Now, note that combining these two equations yields us that f ( p, 0) = + (1 − p ) f ( p + 4 4 1 3 0 . 5 , 0) + f (0 , 2) . But then we see that, solving the system yields us that f (0 , 0) = + 4 4 3 1 f (0 . 5 , 0)+ (1+ f (0 . 5 , 0)) , or that f (0 , 0) = 1+ f (0 . 5 , 0) , and similarly we see that f (0 . 5 , 0) = 4 4 3 3 1 1 4 1 1
- f (1 , 0)+ (1+ f (0 . 5 , 0)) , or that f (0 . 5 , 0) = + f (1 , 0) , and that f (1 , 0) = 1+ f (0 . 5 , 0) . 4 4 2 4 3 2 4 11 1 44 The last two equations yield us in turn that f (0 . 5 , 0) = + f (0 . 5 , 0) , or that f (0 . 5 , 0) = , 6 8 21 65 which in turn means that f (0 , 0) = , yielding an answer of 86 . 21 a b