A fair -sided die is repeatedly rolled until an odd number appears. What is the probability that every even number appears at least once before the first occurrence of an odd number?
- A)
- B)
- C)
- D)
- E)
Answer
C
Key insight
Rolls that repeat a number already seen change nothing, so skip them. Then the first three different numbers to appear must be 2, 4, 6: (1/2)(2/5)(1/4) = 1/20.
Solution
Key idea: ignore repeats. Suppose the die has already shown . Rolling again does not help or hurt: we still need the other evens, and no odd has appeared. So we only care about each roll that shows a number not seen before. The next such new number is equally likely to be any of the numbers not yet seen.
1. The first roll. It must be even, or the game ends at once. Chance: .
2. The next new number. One even has been seen. The unseen numbers are evens and odds, and the next new one is equally likely to be any of them. We need an even: chance .
3. The next new number after that. Two evens have been seen. The unseen numbers are even and odds. We need the even: chance .
4. Once all three evens have appeared, it does not matter what comes next. Multiply the chances:
The answer is .
Why this works
When a question only asks which things happen first, repeated outcomes can be ignored. What matters is the order in which new outcomes first appear, and each new outcome is equally likely to be any of the ones still unseen. This trick turns an endless sequence of rolls into three simple steps.
Alternative approach
Imagine rolling forever and writing down each number the first time it appears. You get the six numbers in some order, and every order is equally likely. The event we want says the first three numbers in that list are , , in some order. There are equally likely ways to choose which of the numbers come first, and only one of those choices is the three evens. So the chance is .
The trap
Thinking the three even numbers must come on three rolls in a row. An even number can repeat before the next new one shows up.
Concise solution
Repeated faces are irrelevant; only the order in which new faces first show up matters. Keep rolling (imagine continuing past the first odd) and record each face the first time it appears. The first recorded face is uniform over the six faces; whenever some faces remain unseen, the next new face is equally likely to be any of them, since repeats are just skipped. So the order of first appearances is a uniformly random permutation of .
The event "every even number appears before the first odd number" says exactly that the first three faces to appear are in some order. Among the equally likely choices for which three faces appear first, only one is .
The probability is . The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 7: Introduction to Probability
- Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.5)
- Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)
- Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Techniques
Map the objects to something easier to count · Exploit symmetry to reduce work or pair up objects