March 28th, 2020 at 9:04:15 AM
permalink

The website www.fivethirtyeight.com has riddlers each week that are usually math related. Here's one from this week. I'm thinking you'd need to take a Markov Chain approach to this? It's been too long though, don't remember how to do them.

You start with a fair 6-sided die and roll it six times, recording the results of each roll. You then write these numbers on the six faces of another, unlabeled fair die. For example, if your six rolls were 3, 5, 3, 6, 1 and 2, then your second die wouldn’t have a 4 on it; instead, it would have two 3s.

Next, you roll this second die six times. You take those six numbers and write them on the faces of yet another fair die, and you continue this process of generating a new die from the previous one.

Eventually, you’ll have a die with the same number on all six faces. What is the average number of rolls it will take to reach this state?

Extra credit: Instead of a standard 6-sided die, suppose you have an N-sided die, whose sides are numbered from 1 to N. What is the average number of rolls it would take until all N sides show the same number?

You start with a fair 6-sided die and roll it six times, recording the results of each roll. You then write these numbers on the six faces of another, unlabeled fair die. For example, if your six rolls were 3, 5, 3, 6, 1 and 2, then your second die wouldn’t have a 4 on it; instead, it would have two 3s.

Next, you roll this second die six times. You take those six numbers and write them on the faces of yet another fair die, and you continue this process of generating a new die from the previous one.

Eventually, you’ll have a die with the same number on all six faces. What is the average number of rolls it will take to reach this state?

Extra credit: Instead of a standard 6-sided die, suppose you have an N-sided die, whose sides are numbered from 1 to N. What is the average number of rolls it would take until all N sides show the same number?

March 28th, 2020 at 1:05:10 PM
permalink

Good problem. I'm on it.

It's not whether you win or lose; it's whether or not you had a good bet.

March 28th, 2020 at 3:43:18 PM
permalink

I'll let you guys do the math (because I can't) but I come up with an average number of rolls of 9.662... which seems a little seems low to me.

March 28th, 2020 at 4:14:53 PM
permalink

Quote:EdCollinsI'll let you guys do the math (because I can't) but I come up with an average number of rolls of 9.662... which seems a little seems low to me.

Ed, your answer appers to be the number of dice used; the number of rolls would be 6 times that

I did it with a Markov chain, using eleven "states":

State 0 is {6}

State 1 is {5,1}

State 2 is {4,2}

State 3 is {4,1,1}

State 4 is {3,3}

State 5 is {3,2,1}

State 6 is {3,1,1,1}

State 7 is {2,2,2}

State 8 is {2.2.1.1}

State 9 is {2,1,1,1,1}

State 10 is {1,1,1,1,1,1}

The numbers indicate how many times a particular number appears on a die - for example, {5,1} could be 226262, or 344333, or 155551 - any permutation of 4 of one number and 2 of another

The initial state is state 10; the question is, how many rolls (which is 6 times the number of dice) are needed to get to state 0

This is 10 equations in 10 unknowns:

23,328 = 13,938 E(1) - 4,875 E(2) - 1,250 E(4)

729 = - 204 E(1) + 429 E(2) - 160 E(4)

7,776 = - 2,058 E(1) - 1,365 E(2) + 6,456 E(3) - 430 E(4) - 1,680 E(5) - 240 E(7)

32 = - 6 E(1) - 15 E(2) + 22 E(4)

23,328 = - 2,586 E(1) - 4,335 E(2) - 3,240 E(3) - 2,510 E(4) + 14,688 E(5) - 1,620 E(7)

3,888 = - 372 E(1) - 345 E(2) - 660 E(3) - 140 E(4) - 1,200 E(5) + 3,528 E(6) - 210 E(7) - 540 E(8)

243 = - 12 E(1) - 30 E(2) - 30 E(3) - 20 E(4) - 120 E(5) + 213 E(7)

23,328 = - 798 E(1) - 1,575 E(2) - 2,640 E(3) - 970 E(4) - 8,400 E(5) - 2,400 E(6) - 1,800 E(7) + 18,648 E(8)

11,664 = - 222 E(1) - 345 E(2) - 990 E(3) - 190 E(4) - 2,880 E(5) - 1,800 E(6) - 630 E(7) - 3,510 E(8) + 10,584 E(9)

7,776 = - 30 E(1) - 75 E(2) - 300 E(3) - 50 E(4) - 1,200 E(5) - 1,200 E(6) - 300 E(7) - 2,700 E(8) - 1,800 E(9) + 7,656 E(10)

Solving gets E(10) = 9.65699, so there are 6 x 9.65699 = about 57.94 die rolls needed

March 28th, 2020 at 4:22:53 PM
permalink

Don: Thanks. I assumed each "roll" was a roll of six dice all at once. And yet when I re-read the question... I still think that's the case. :)

March 28th, 2020 at 4:26:29 PM
permalink

Quote:EdCollinsDon: Thanks. I assumed each "roll" was a roll of six dice all at once. And yet when I re-read the question... I still think that's the case. :)

“ You start with a fair 6-sided die and roll it six times, recording the results of each roll.”

?

The race is not always to the swift, nor the battle to the strong; but that is the way to bet.

March 28th, 2020 at 4:27:58 PM
permalink

Yea, and then after re-reading it again I realized I completely misread it.

Thanks.

Thanks.

March 28th, 2020 at 4:36:35 PM
permalink

There must be a trick/formula for this, especially to solve the extra credit problem of n sided die

I can only think of listing out the various combinations of the unfair die then doing a Markov chain with many states, which is basically brute forcing it IMO

I can only think of listing out the various combinations of the unfair die then doing a Markov chain with many states, which is basically brute forcing it IMO

It’s all about making that GTA

March 28th, 2020 at 9:06:17 PM
permalink

As usual, I only can find the answer by simulations, rolls required = 57.943

March 28th, 2020 at 10:18:30 PM
permalink

Quote:Ace2There must be a trick/formula for this, especially to solve the extra credit problem of n sided die

I can only think of listing out the various combinations of the unfair die then doing a Markov chain with many states, which is basically brute forcing it IMO

The best equation(but not that accurate), Rolls required = 1.955*N^2 - 2.085*N, for N sided die