More Iterative Dice Rolling

Three 6 6 -sided fair dice are rolled and their sum is recorded. If the three dice show all different values, then stop. Otherwise, roll any dice with the same value again, and add the sum of these re-rolled dice to the previous sum. Continue this process until all three dice show different values, and let X X be the final total of the values of all the dice rolled.

Here is an example:

  • Roll 1 : ( 5 , 5 , 3 ) (5,5,3) are thrown, for a running total of 13. 13.
  • Roll 2 : The two dice showing 5 5 are rolled again and come up ( 3 , 1 ) , (3,1), for a running total of 13 + 4 = 17. 13+4=17. The three dice now show ( 3 , 1 , 3 ) . (3,1,3).
  • Roll 3 : The two dice showing 3 3 are rolled again and come up ( 1 , 1 ) , (1,1), for a running total of 17 + 2 = 19. 17+2=19. The three dice now show ( 1 , 1 , 1 ) . (1,1,1).
  • Roll 4 : All three dice are rolled again and come up ( 5 , 5 , 6 ) , (5,5,6), for a running total of 19 + 16 = 35. 19+16=35.
  • Roll 5 : The two dice showing 5 5 are rolled again and come up ( 1 , 5 ) , (1,5), for a running total of 35 + 6 = 41. 35+6=41. The three dice now show ( 1 , 5 , 6 ) , (1,5,6), so we stop with X = 41. X=41.

The expected value of X X can be written as a b , \frac{a}{b}, where a a and b b are coprime positive integers.

What is a + b ? a+b?


This problem was inspired by a previous featured problem . In this version, all of the dice must show different numbers (not just the numbers that were just rolled).


The answer is 691.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

7 solutions

Mark Hennings
Aug 28, 2018

Let E a E_a be the total value of the dice rolled, if we start by rolling just two dice, while the third dice is already showing a a (for any 1 a 6 1 \le a \le 6 ). Then, conditioning upon the outcomes of the two dice rolls, E [ E a ] = 1 36 u , v = 1 6 ( u + v + T a , u , v ) = 7 + 1 36 u , v = 1 6 T a , u , v \mathbb{E}[E_a] \; =\; \tfrac{1}{36}\sum_{u,v=1}^6\big(u + v + T_{a,u,v}\big) \; = \; 7 + \tfrac{1}{36}\sum_{u,v=1}^6 T_{a,u,v} where T a , u , v = { E [ X ] u = v = a E [ E a ] u = v a E [ E u ] u v = a E [ E v ] v u = a 0 o . w . T_{a,u,v} \; = \; \left\{ \begin{array}{lll} \mathbb{E}[X] & \hspace{1cm} & u = v = a \\ \mathbb{E}[E_a] & & u = v \neq a \\ \mathbb{E}[E_u] & & u \neq v = a \\ \mathbb{E}[E_v] & & v \neq u = a \\ 0 & & \mathrm{o.w.}\end{array} \right. and hence E [ E a ] = 7 + 1 36 ( E [ X ] + 5 E [ E a ] + 2 b a E [ E b ] ) = 7 + 1 36 ( E [ X ] + 3 E [ E a ] + 2 b = 1 6 E [ E b ] ) \mathbb{E}[E_a] \; = \; 7 + \tfrac{1}{36}\left(\mathbb{E}[X] + 5\mathbb{E}[E_a] + 2\sum_{b \neq a}\mathbb{E}[E_b]\right) \; = \; 7 + \tfrac{1}{36}\left(\mathbb{E}[X] + 3\mathbb{E}[E_a] + 2\sum_{b=1}^6\mathbb{E}[E_b]\right) From this it is clear that E [ E 1 ] = E [ E 2 ] = E [ E 3 ] = E [ E 4 ] = E [ E 5 ] = E [ E 6 ] = E \mathbb{E}[E_1]=\mathbb{E}[E_2]=\mathbb{E}[E_3]=\mathbb{E}[E_4]=\mathbb{E}[E_5]=\mathbb{E}[E_6]= \mathcal{E} (say), where E = 7 + 1 36 ( E [ X ] + 15 E ) \mathcal{E} \; = \; 7 + \tfrac{1}{36}(\mathbb{E}[X] + 15\mathcal{E}) and so 21 E = 252 + E [ X ] 21\mathcal{E} \; = \; 252 + \mathbb{E}[X] A similar argument gives us that E [ X ] = 1 216 u , v , w = 1 6 ( u + v + w + Q u , v , w ) \mathbb{E}[X] \; = \; \tfrac{1}{216}\sum_{u,v,w=1}^6 \big(u + v + w + Q_{u,v,w}\big) where Q u , v , w = E [ X ] Q_{u,v,w} = \mathbb{E}[X] if u = v = w u=v=w , Q u , v , w = E Q_{u,v,w} = \mathcal{E} if two if u , v , w u,v,w are equal with the other distinct, and Q u , v , w = 0 Q_{u,v,w} = 0 if u , v , w u,v,w are all distinct. Hence E [ X ] = 21 2 + 1 36 E [ X ] + 5 12 E \mathbb{E}[X] \; = \; \tfrac{21}{2} + \tfrac{1}{36}\mathbb{E}[X] + \tfrac{5}{12}\mathcal{E} and hence 35 E [ X ] = 378 + 15 E 35\mathbb{E}[X] \; = \; 378 + 15\mathcal{E} Solving these equations simultaneously, we obtain E [ X ] = 651 40 \mathbb{E}[X] = \tfrac{651}{40} and E = 511 40 \mathcal{E} = \tfrac{511}{40} . This makes the answer 651 + 40 = 691 651+40=\boxed{691} .

@Mark Hennings , sir, you use different ideas in all your solutions. Can you please refer some books on maths and physics which have good problems and also teach concepts from basic to advance level?? Thank you!

Mr. India - 2 years, 3 months ago
Jeremy Galvagni
Aug 28, 2018

I solved this in a manner similar to how @Patrick Corn solved the Inspiration problem. This variation is just a tiny bit harder. With more opportunities to reroll, the expected value should be higher.

In fact, the first equation is identical:

E = 5 9 ( 10.5 ) + 5 12 ( 10.5 + E 2 ) + 1 36 ( 10.5 + E ) E=\frac{5}{9}(10.5)+\frac{5}{12}(10.5+E_{2})+\frac{1}{36}(10.5+E)

What's different is if we see a single matched pair, there are more possibilities, so E 2 E_{2} is different. There's a 5 9 \frac{5}{9} chance of rolling those two dice and seeing no matches, 5 12 \frac{5}{12} of seeing a single pair again, and 1 36 \frac{1}{36} of now having three that match. This last choice brings us back to E E . So

E 2 = 5 9 ( 7 ) + 5 12 ( 7 + E 2 ) + 1 36 ( 7 + E ) E_{2}=\frac{5}{9}(7)+\frac{5}{12}(7+E_{2})+\frac{1}{36}(7+E)

E 2 = 12 + 1 21 E E_{2}=12+\frac{1}{21}E

Substitute this into the upper equation:

E = 5 9 ( 10.5 ) + 5 12 ( 10.5 + [ 12 + 1 21 E ] ) + 1 36 ( 10.5 + E ) E=\frac{5}{9}(10.5)+\frac{5}{12}(10.5+[12+\frac{1}{21}E])+\frac{1}{36}(10.5+E)

E = 651 40 = 16.275 E=\frac{651}{40}=16.275

651 + 40 = 691 651+40=\boxed{691}

Your second formula for E 2 E_2 , while correct, dodges much detail. In the previous problem, when rolling two dice, the value of the third did not matter. The way you are setting out the solution, the value of the third die does matter, at least until you prove that it does not.

You are conditioning on the possible outcomes of the two dice rolls. Instead of just E 2 E_2 , suppose that E 2 , a E_{2,a} is the expected total score if we roll two dice, with the third showing a a Then the other two dice can show one of:

  • two copies of a a ,
  • two copies of something other than a a ,
  • one copy of a a and one of something else,
  • two distinct values different from a a

If we condition on these outcomes (which is what you want to do), we should get E 2 , a = 1 36 ( 2 a + E ) + 1 36 b a ( 2 b + E 2 , a ) + 1 18 b a ( a + b + E 2 , b ) + 1 36 b c b , c a ( b + c ) E_{2,a} \; = \; \tfrac{1}{36}(2a + E) +\tfrac{1}{36}\sum_{b \neq a}(2b + E_{2,a}) + \tfrac{1}{18}\sum_{b \neq a}(a+b+E_{2,b}) + \tfrac{1}{36}\sum_{{b \neq c} \atop {b,c \neq a}} (b+c) which evaluates as E 2 , a = 1 18 a + 1 36 E + 1 18 ( 21 a ) + 5 36 E 2 , a + 1 18 ( 21 + 4 a ) + 1 18 b a E 2 , b + 4 18 ( 21 a ) = 7 + 1 36 E + 5 36 E 2 , a + 1 18 b a E 2 , b \begin{aligned} E_{2,a} & = \; \tfrac{1}{18}a + \tfrac{1}{36}E + \tfrac{1}{18}(21-a) + \tfrac{5}{36}E_{2,a} + \tfrac{1}{18}(21+4a) + \tfrac{1}{18}\sum_{b \neq a}E_{2,b} + \tfrac{4}{18}(21-a) \\ & = \; 7 + \tfrac{1}{36}E + \tfrac{5}{36}E_{2,a} + \tfrac{1}{18}\sum_{b \neq a}E_{2,b} \end{aligned} It is only when you get to here that you can say that the E 2 , a E_{2,a} are all the same, and obtain the formula you want.

Mark Hennings - 2 years, 9 months ago

Log in to reply

I sort of did that on paper, but when I did those calculations and found it didn't matter how you ended up getting from two matching to two matching again. I basically assumed it didn't warrant mentioning.

Thanks for bridging the gap.

Jeremy Galvagni - 2 years, 9 months ago

To elaborate on why it is not obvious, consider the case where you rolled { 3 , 3 , 1 } \{ 3, 3, 1 \} vs { 3 , 3 , 6 } \{ 3, 3, 6 \} . Then, while you have the same possibility of re-rolling a 1 or 6, the impact on the running total is different.

Thinking like this, it should feel surprising that these events give the same expected outcome.

(Yes, I know you said it, but sometimes an explicit example helps.)

Calvin Lin Staff - 2 years, 9 months ago
John Ross
Sep 9, 2018

If the expected value is E E , then we have E = 10.5 + 5 9 ( 0 ) + 5 12 ( E 2 ) + 1 36 ( E ) E=10.5+\frac 59(0)+\frac{5}{12}(E_2)+\frac{1}{36}(E) where E 2 E_2 is the expected value from rolling two dice. Notice that E 2 E_2 is exactly the same as E E except that we don't count the value of one of the three dice for E 2 E_2 . This means that E 2 = E 3.5 E_2=E-3.5 and we can solve for E E to get E = 651 40 E=\boxed{\dfrac{651}{40}}

Like Jeremy, you omit the unexpected fact that the value of E 2 E_2 does not depend on the value of the third die that is not being rolled. While true, this is not obvious, and should be proved.

Mark Hennings - 2 years, 9 months ago

Log in to reply

We can think of rolling 3 dice (for E E ) as rolling one, noticing its value, then rolling the other two. We are doing exactly the same thing for E 2 E_2 except not recording the value of the first dice. Thus E 2 E_2 should be E E minus (expected value of the first dice). Is my reasoning incorrect? It does not seem at all unexpected to me that the value of the first dice doesn't affect E 2 E_2

John Ross - 2 years, 9 months ago

Log in to reply

Since the value of the third die affects when you have to recollect, and what scores you can’t have obtained by the time you reroll, I think it would take a brave person to assume that the value of the third dice was irrelevant. See my proof to see why it in fact is unimportant...

Mark Hennings - 2 years, 9 months ago

Log in to reply

@Mark Hennings Should be able to do a simple symmetry argument to ignore this. I'll write an answer, feel free to point out any mistakes.

Alex Burgess - 2 years, 2 months ago

@Mark Hennings We can just look at the number of dice rolled. Pair each game with the one viewed by someone watching from below a glass table (looking at the bottoms). And notice the expected value is equal to expected number of rolls * 7 2 \frac{7}{2} .

Alex Burgess - 2 years, 2 months ago

Log in to reply

@Alex Burgess This argument resorts to the special design of the die, where the opposite numbers add up to 7. It is not necessary. The equal probability of obtaining any number provides the symmetry sought.

Hansen Chen - 1 year, 9 months ago

Log in to reply

@Hansen Chen True, this was just a visual way of thinking about the bijection.

Alex Burgess - 1 year, 8 months ago
K T
Sep 16, 2018

We set up a Markov chain with 3 possible states:

A: we are going to roll 3 dice (at start, or when there are 3 equal dice)
B: we are going to roll 2 dice (there are 2 equal dice)
C: we are done (all dice are different)

By considering the probabilities when throwing the dice we get the transition probabilities [read (x->y) as P(new state=y|old state=x)]

(A -> A) = 1/36 (A -> B) = 15/36 (A -> C) = 20/36
(B -> A) = 1/36 (B -> B) = 15/36 (B -> C) = 20/36
(C -> A) = 0 (C -> B) = 0 (C -> C) = 1

Using the transition probabilities above, we set up the expected number of visits to each state (a, b and c):

a = 1+ a/36 + b/36
b = 15a/36 + 15b/36
c = 20a/36 + 20b/30

From this, solve a=21/20, b=3/4, c=1 . When in A we throw 3 dice, when in B we throw 2 dice, when in C we throw none. The average points a die throw yields is 7/2 (no matter the state we're in, because the whole thing is symmetric with respect to the possible values 1..6), so we have for the expected total of thrown eyes:

E = (3a+2b+0c)×(7/2) = 651/40. The requested answer then is 651+40=691.

Alex Burgess
Mar 25, 2019

We can pair each game with a mirrored version, where we instead add the number facing downwards. The total amount from both of these games will be 7 7* (number of dice rolled). Hence, the average total for a game with n n rolls is 7 n 2 \frac{7n}{2} .

Let E d = E_d = expected number of rolled dice.

E d = 3 + 1 6 2 E d + 15 6 2 E 2 E_d = 3 + \frac{1}{6^2} E_d + \frac{15}{6^2} E_2 .

Where E 2 E_2 is the expected number from rolling 2 dice, leaving the 3rd face up.

E 2 = E d 1 E_2 = E_d - 1 .

Hence E d = 93 20 E_d = \frac{93}{20} .

Therefore the expected total value is 93 7 20 2 = 651 40 \frac{93*7}{20*2} = \frac{651}{40} .

Brilliant use of symmetry! The derivation can be further generalized though. This argument resorts to the special design of the die, where the opposite numbers add up to 7 7 . It is not necessary. The equal probability of obtaining any number provides the symmetry sought. There is a typo: The second equation should write E 2 = E d 1 E_2=E_d-1 . Also, the definition of E 2 E_2 is not very clear. I suggest we phrase it as, the expected number of rolled dice starting with rolling 2 2 of them where the face-up number of these two are different from the third die.

Hansen Chen - 1 year, 9 months ago

True, I used the opposite sides adding up to 7 as a more visual way to see the solution. Really it is just a bijection onto itself where each pair adds to 7.

Alex Burgess - 1 year, 8 months ago

Log in to reply

Even the "bijection onto itself where each pair adds to 7" is not necessary. As I said, "The equal probability of obtaining any number provides the symmetry sought." The multiplicative factor is just the arithmetic average of all the numbers on a die, even if the numbers are not an arithmetic progression which gives the pairing you refer to. In fact, that was how I approached the problem, with my two equations being yours multiplied by the arithmetic average of the numbers on a die.

Hansen Chen - 1 year, 8 months ago
Vinod Kumar
Sep 13, 2018

In this problem, three dices are rolled and we define:

X=Average score ( iterated) for 2-dice,

Y=Average score ( iterated) for 3-dice?

The data required is given:

Prob for 2-dice (same face)=(90/216),

Average score for 2-dice=(14/2),

Prob for 3-dice (same face)=(6/216),

Average score for 3-dice=(21/2),

The equations are:

Y=(21/2) + (90/216)X + (6/216)Y,

X=(14/2) + (90/216)X + (6/216)Y,

Therefore, subtracting the above two, we get,

Y - X = (7/2).

Solving, we get:

Y=(31/2) + (6/216)(1+5/7)Y,

Y=651/40 = 16.275

Answer = (651+40) = 691

Vilim Lendvaj
Sep 13, 2018

I solved the system of equations with Gaussian Elimination. These people with actual solutions amaze me.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...