Difference between revisions of "2008 iTest Problems/Problem 26"
m (→Solution) |
m (→Solution) |
||
| Line 19: | Line 19: | ||
The formula for a geometric series is <math>\sum_{n=0}^{\infty}{x^n}=\frac{1}{1-x}</math>. Taking derivatives of both sides gives | The formula for a geometric series is <math>\sum_{n=0}^{\infty}{x^n}=\frac{1}{1-x}</math>. Taking derivatives of both sides gives | ||
<math>\sum_{n=1}^{\infty}{n\cdot x^{n-1}}=\frac{1}{(1-x)^2}</math> | <math>\sum_{n=1}^{\infty}{n\cdot x^{n-1}}=\frac{1}{(1-x)^2}</math> | ||
| − | So the expected number of rolls required to get face n is <math>\frac{\frac{1}{12}}{(1-\frac{ | + | So the expected number of rolls required to get face n is <math>\frac{\frac{1}{12}}{(1-\frac{11}{12})^2}=12</math>. |
Rolling a sequence to get a first n can be thought of as an independent trial and getting the full sequence of {1,2,3,4,5,6,7,8,9,10,11,12} can be | Rolling a sequence to get a first n can be thought of as an independent trial and getting the full sequence of {1,2,3,4,5,6,7,8,9,10,11,12} can be | ||
Latest revision as of 12:09, 2 January 2020
Problem
Done working on his sand castle design, Joshua sits down and starts rolling a 
-sided die he found when cleaning the storage shed. He rolls and rolls and rolls, and after 
rolls he finally rolls a 
. Just 
rolls later he rolls the first 2 
that first roll of . 
rolls later, Joshua rolls the first 
the first 
that he rolled 
the first that he rolled. His first 
rolls make the sequence 
.
Joshua wonders how many times he should expect to roll the -sided die so that he can remove all but of the numbers from the entire sequence of rolls and (without changing the order of the sequence), be left with the sequence 
. What is the expected value of the number of times Joshua must roll the die before he has such a sequence? (Assume Joshua starts from the beginning - do 
assume he starts by rolling the specific sequence of rolls above.)
Solution
The expected number of rolls required to get any particular face of the die is 12 rolls.
The proof goes as follows: the probability of rolling n on roll 1 is 
.
The probability of rolling n on roll 2 (but not roll 1) is 
.
The probability of rolling n on roll 3 (but not rolls 1 or 2) is 
.
In general, rolling your first n on roll k is 
.
The expected total number of rolls needed to get your first n is 
.
The formula for a geometric series is 
. Taking derivatives of both sides gives
So the expected number of rolls required to get face n is 
.
Rolling a sequence to get a first n can be thought of as an independent trial and getting the full sequence of {1,2,3,4,5,6,7,8,9,10,11,12} can be thought of as running 12 independent trials: trial 1 to get your first 1, then trial 2 to roll your first 2 (after the first 1), then trial 3 to roll the first 3 (after the first 2 after the first 1) etc... All of these 12 trials can be concatenated together to get the final required sequence.
Thus the total expected roll count is 
.
See Also
| 2008 iTest (Problems) | ||
| Preceded by: Problem 25 |
Followed by: Problem 27 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • 61 • 62 • 63 • 64 • 65 • 66 • 67 • 68 • 69 • 70 • 71 • 72 • 73 • 74 • 75 • 76 • 77 • 78 • 79 • 80 • 81 • 82 • 83 • 84 • 85 • 86 • 87 • 88 • 89 • 90 • 91 • 92 • 93 • 94 • 95 • 96 • 97 • 98 • 99 • 100 | ||
