PUMaC 2017 · 团队赛 · 第 14 题
PUMaC 2017 — Team Round — Problem 14
题目详情
- (10) Eric rolls a ten-sided die (with sides labeled 1 through 10) repeatedly until it lands on 3, 5, or 7. Conditional on all of Eric’s rolls being odd, the expected number of rolls can be m expressed as , where m and n are relatively prime positive integers. Compute m + n . n y 2017
解析
- If you got , consider yourself trolled. You cannot simply assume that you have a five-sided 3 die (with just the odd numbers) and calculate the expected number of rolls until you roll a 3, 5, or 7. An intuitive way to realize this is that short sequences of rolls are particularly likely because the longer the roll, the likelier it is that at some point you’ll roll an even number. Instead, we use the identity P r [ A | B ] P r [ B ] = P r [ B | A ] P r [ A ] (known as Bayes’s theorem). Specifically we have the following: P r [length = k | all odd] P r [all odd] = P r [all odd | length = k ] P r [length = k ] . We wish to know the first probability above as part of computing the expected value. The ( ) 2 3 2 3 2 3 3 second probability is easily computed: it is + · + · + · · · = . The second 10 10 10 10 10 8 ( ) k − 1 k − 1 2 · 3 2 k − 1 probability is = , because there are 2 · 3 ways to roll the dice so that all rolls k − 1 7 · 3 7 k − 1 are odd and only the last roll is 3, 5, or 7, and 7 · 3 total ways to roll the dice so that only ( ) k − 1 7 3 the last roll is 3, 5, or 7. The third probability is · since a sequence of rolls has 10 10 length k if and only if the first k − 1 rolls are not 3, 5, or 7 and the last roll is 3, 5, or 7. This gives us ( ) ( ) k − 1 k − 1 8 2 7 3 4 P r [length = k | all odd] = · · · = . k 3 7 10 10 5 Thus, the answer is 4 4 4 · 1 + · 2 + · 3 + . . . . 5 25 125 ( ) ( ) 4 4 4 4 We can write this as + + . . . + + + . . . + . . . . The geometric series formula tells 5 25 25 125 1 1 us that the parenthetical values are, respectively, 1, , , and so on, and using the geometric 5 25 5 series formula once more gives us a final answer of . Therefore, we have m + n = 9 . 4 Problem written by Eric Neyman; inspired by Elchanan Mossel 2016 y 2017 y 2016 y