rsactuary
Joined: Sep 6, 2014
• Posts: 1818
Thanks for this post from:
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?
Wizard
Joined: Oct 14, 2009
• Posts: 22916
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.
EdCollins
Joined: Oct 21, 2011
• Posts: 1289
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.
ThatDonGuy
Joined: Jun 22, 2011
• Posts: 4739
March 28th, 2020 at 4:14:53 PM permalink
Quote: EdCollins

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.

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

EdCollins
Joined: Oct 21, 2011
• Posts: 1289
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. :)
unJon
Joined: Jul 1, 2018
• Posts: 2485
March 28th, 2020 at 4:26:29 PM permalink
Quote: EdCollins

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. :)

“ 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.
EdCollins
Joined: Oct 21, 2011
• Posts: 1289
March 28th, 2020 at 4:27:58 PM permalink
Yea, and then after re-reading it again I realized I completely misread it.

Thanks.
Ace2

Joined: Oct 2, 2017
• Posts: 891
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
It’s all about making that GTA
ssho88
Joined: Oct 16, 2011
• Posts: 511
March 28th, 2020 at 9:06:17 PM permalink

As usual, I only can find the answer by simulations, rolls required = 57.943
ssho88
Joined: Oct 16, 2011
• Posts: 511
March 28th, 2020 at 10:18:30 PM permalink
Quote: Ace2

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

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