Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 iTest Problems/Problem 26"

(Created page with "==Problem== Done working on his sand castle design, Joshua sits down and starts rolling a <math>12</math>-sided die he found when cleaning the storage shed. He rolls and roll...")
 
m (→‎Solution)
 
(One intermediate revision by one other user not shown)
Line 10: Line 10:
  
 
The expected number of rolls required to get any particular face of the die is 12 rolls.  
 
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 <math>\frac{1}{12}</math>.
+
The proof goes as follows: the probability of rolling n on roll 1 is <math>(\frac{1}{12})</math>.
−
The probability of rolling n on roll 2 (but not roll 1) is <math>\frac{11}{12}\cdot \frac{1}{12}</math>.
+
The probability of rolling n on roll 2 (but not roll 1) is <math>(\frac{11}{12})\cdot (\frac{1}{12})</math>.
−
The probability of rolling n on roll 3 (but not rolls 1 or 2) is <math>(\frac{11}{12})^2 \cdot \frac{1}{12}</math>.
+
The probability of rolling n on roll 3 (but not rolls 1 or 2) is <math>(\frac{11}{12})^2 \cdot (\frac{1}{12})</math>.
−
In general, rolling your first n on roll k is <math>(\frac{11}{12})^(k-1) \cdot \frac{1}{12}</math>.
+
In general, rolling your first n on roll k is <math>(\frac{11}{12})^{(k-1)} \cdot (\frac{1}{12})</math>.
−
The expected total number of rolls needed to get your first n is <math>1\cdot \frac{1}{12}+2\cdot \frac{11}{12}\frac{1}{12}+3\cdot (\frac{11}{12})^2\frac{1}{12}+4\cdot (\frac{11}{12})^3\frac{1}{12}+\cdots =
+
The expected total number of rolls needed to get your first n is <math>1\cdot \frac{1}{12}+2\cdot (\frac{11}{12})(\frac{1}{12})+3\cdot (\frac{11}{12})^{2}(\frac{1}{12})+4\cdot (\frac{11}{12})^3(\frac{1}{12})+\cdots =
−
\sum_{k=1}^{\infty}{k\cdot (11/12)^(k-1)(1/12)}</math>.
+
\sum_{k=1}^{\infty}{k\cdot (\frac{11}{12})^{(k-1)}(\frac{1}{12})}</math>.
  
 
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{1}{12})^2}=12</math>.  
+
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 13:09, 2 January 2020

Problem

Done working on his sand castle design, Joshua sits down and starts rolling a $12$-sided die he found when cleaning the storage shed. He rolls and rolls and rolls, and after $17$ rolls he finally rolls a $1$. Just $3$ rolls later he rolls the first 2 $\textit{ after}$ that first roll of $1$. $11$ rolls later, Joshua rolls the first $3\textit{ after}$ the first $2$ that he rolled $\textit{after}$ the first $1$ that he rolled. His first $31$ rolls make the sequence $4,3,11,3,11,8,5,2,12,9,5,7,11,3,6,10,\textbf{1},8,3,\textbf{2},10,4,2,8,1,9,7,12,11,4,\textbf{3}$. Joshua wonders how many times he should expect to roll the $12$-sided die so that he can remove all but $12$ of the numbers from the entire sequence of rolls and (without changing the order of the sequence), be left with the sequence $1,2,3,4,5,6,7,8,9,10,11,12$. 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 $\textit{not}$ assume he starts by rolling the specific sequence of $31$ rolls above.)


Solution

$\boxed{144}$

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 $(\frac{1}{12})$. The probability of rolling n on roll 2 (but not roll 1) is $(\frac{11}{12})\cdot (\frac{1}{12})$. The probability of rolling n on roll 3 (but not rolls 1 or 2) is $(\frac{11}{12})^2 \cdot (\frac{1}{12})$. In general, rolling your first n on roll k is $(\frac{11}{12})^{(k-1)} \cdot (\frac{1}{12})$. The expected total number of rolls needed to get your first n is $1\cdot \frac{1}{12}+2\cdot (\frac{11}{12})(\frac{1}{12})+3\cdot (\frac{11}{12})^{2}(\frac{1}{12})+4\cdot (\frac{11}{12})^3(\frac{1}{12})+\cdots = \sum_{k=1}^{\infty}{k\cdot (\frac{11}{12})^{(k-1)}(\frac{1}{12})}$.

The formula for a geometric series is $\sum_{n=0}^{\infty}{x^n}=\frac{1}{1-x}$. Taking derivatives of both sides gives $\sum_{n=1}^{\infty}{n\cdot x^{n-1}}=\frac{1}{(1-x)^2}$ So the expected number of rolls required to get face n is $\frac{\frac{1}{12}}{(1-\frac{11}{12})^2}=12$.

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 $12\cdot 12 = 144$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_iTest_Problems/Problem_26&oldid=114030"