Poll

No votes (0%)
1 vote (16.66%)
1 vote (16.66%)
1 vote (16.66%)
1 vote (16.66%)
1 vote (16.66%)
1 vote (16.66%)
4 votes (66.66%)
1 vote (16.66%)
1 vote (16.66%)

6 members have voted

Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
March 20th, 2020 at 2:24:35 PM permalink
I know this one is similar to the Ace2 variant of the light bulb puzzle, but I'm finding what Ace2 brought to the table very interesting.

You have a single fair six-sided die. You keep rolling it until you've rolled each side at least twice.

Question 1: What is the average number of rolls needed?
Question 2: Put the solution in a closed form expression (warning -- difficult -- I think).

Usual rules apply. If you're already a member of the beer club and can't restrain yourself for 24 hours, feel free to PM me.

Last edited by: Wizard on Mar 20, 2020
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ssho88
ssho88
  • Threads: 53
  • Posts: 657
Joined: Oct 16, 2011
March 20th, 2020 at 5:50:15 PM permalink
I think you should change it to ..... until you've rolled each side AT LEAST twice
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
March 20th, 2020 at 8:24:25 PM permalink
Quote: ssho88

I think you should change it to ..... until you've rolled each side AT LEAST twice



Good point. I just made that edit. I think we need to let the 24-hour clock run out before the fun can begin.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
EdCollins
EdCollins
  • Threads: 20
  • Posts: 1739
Joined: Oct 21, 2011
March 20th, 2020 at 10:02:40 PM permalink
I'm not looking for a beer, but for Question 1, I think the average number of rolls needed is 28.165.
I have no idea regarding Question 2.
Suited89
Suited89
  • Threads: 9
  • Posts: 134
Joined: Dec 23, 2019
March 20th, 2020 at 10:24:10 PM permalink
If at least twice I estimated the puzzle as

28 + 1/6 as n*((2n+1)/n)^2 where n is 6 sides of the die.
some people need to reimagine their thinking
Klopp
Klopp
  • Threads: 7
  • Posts: 16
Joined: Mar 10, 2020
March 21st, 2020 at 3:27:31 AM permalink
I am not looking for a beer either, but I think the answer to question 1 is 24.134
ssho88
ssho88
  • Threads: 53
  • Posts: 657
Joined: Oct 16, 2011
March 21st, 2020 at 3:59:23 AM permalink
Quote: Klopp

I am not looking for a beer either, but I think the answer to question 1 is 24.134



Agreed. I got the same answer( through a not so intellectual method)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
March 21st, 2020 at 5:31:27 AM permalink
Quote: EdCollins

I'm not looking for a beer, but for Question 1, I think the average number of rolls needed is 28.165.
I have no idea regarding Question 2.



I disagree on question 1, but you're in the ballpark
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
March 21st, 2020 at 5:33:54 AM permalink
Quote: Suited89

If at least twice I estimated the puzzle as

28 + 1/6 as n*((2n+1)/n)^2 where n is 6 sides of the die.



Let's see, where's my calculator...

That comes out to 56.166666, which is way too many.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
March 21st, 2020 at 5:35:21 AM permalink
Quote: Klopp

I am not looking for a beer either, but I think the answer to question 1 is 24.134



I agree.

To get the beer, one must show his work. I'll award two beers for this one, one for each part.

Also, please put answers and solutions in spoiler tags next time.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
EdCollins
EdCollins
  • Threads: 20
  • Posts: 1739
Joined: Oct 21, 2011
March 21st, 2020 at 5:48:01 AM permalink
Whoops! Yea, my random dice were sometimes rolling zeroes... and I was counting that as a valid roll. LOL. I now come up with 24.1365
.
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
March 21st, 2020 at 2:25:59 PM permalink

Let E(A,B) be the expected number of rolls needed to have every number rolled at least twice given that A numbers have already been rolled at least twice and B numbers have been rolled exactly once (and the remaining (6 - A - B) have not been rolled at all)

E(6,0) = 0
At condition (A,B):
One of the A numbers that has been rolled at least twice will be rolled with probability A/6; the condition will remain at (A,B)
One of the B numbers that has been rolled exactly once will be rolled with probability B/6;
there is now one more "rolled at least twice" number and one fewer "rolled exactly once" number than before, so the condition is now (A+1, B-1)
One of the (6-A-B) numbers that has not been rolled will be rolled with probability (6-A-B)/6; the condition is now (A, B+1)

E(A,B) = A/6 E(A,B) + B/6 E(A+1,B-1) + (6-A-B)/6 E(A,B+1)
6 E(A,B) = A E(A,B) + B E(A+1,B-1) + (6-A-B) E(A,B+1)
(6-A) E(A,B) = B E(A+1,B-1) + (6-A-B) E(A,B+1)
E(A,B) = B/(6-A) E(A+1,B-1) + (6-A-B)/(6-A) E(A,B+1)
E(A,B) = B/(6-A) E(A+1,B-1) + (1 - B/(6-A)) E(A,B+1)

E(5,1) = 6
E(5,0) = 12
E(4,2) = 9
E(4,1) = 27 / 2
E(4,0) = 33 / 2
E(3,3) = 11
E(3,2) = 44 / 3
E(3,1) = 311 / 18
E(3,0) = 347 / 18
E(2,4) = 25 / 2
E(2,3) = 125 / 8
E(2,2) = 2,585 / 144
E(2,1) = 11,395 / 576
E(2,0) = 12,259 / 576
E(1,5) = 137 / 10
E(1,4) = 411 / 25
E(1,3) = 111,281 / 6,000
E(1,2) = 3,643,433 / 180,000
E(1,1) = 38,969,339 / 1,800,000
E(1,0) = 41,129,339 / 1,800,000
E(0,6) = 147 / 10
E(0,5) = 343 / 20
E(0,4) = 171,731 / 9,000
E(0,3) = 2,479,351 / 120,000
E(0,2) = 118,749,869 / 5,400,000
E(0,1) = 374,768,681 / 16,200,000
E(0,0) = 390,968,681 / 16,200,000 = 24.1338691975309
You can't get much more "closed form" than a rational number
Yes, that fraction is in lowest terms; the largest prime factor of 16,200,000 is 5, and 390,968,681 is not a multiple of 2, 3, or 5

Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
March 21st, 2020 at 4:41:06 PM permalink
Quote: EdCollins

Whoops! Yea, my random dice were sometimes rolling zeroes... and I was counting that as a valid roll. LOL. I now come up with 24.1365
.



I agree to four decimal places. I'd say a successful simulation. No beer though.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
March 21st, 2020 at 4:47:32 PM permalink
Quote: ThatDonGuy


Let E(A,B) be the expected number of rolls needed to have every number rolled at least twice given that A numbers have already been rolled at least twice and B numbers have been rolled exactly once (and the remaining (6 - A - B) have not been rolled at all)

E(6,0) = 0
At condition (A,B):
One of the A numbers that has been rolled at least twice will be rolled with probability A/6; the condition will remain at (A,B)
One of the B numbers that has been rolled exactly once will be rolled with probability B/6;
there is now one more "rolled at least twice" number and one fewer "rolled exactly once" number than before, so the condition is now (A+1, B-1)
One of the (6-A-B) numbers that has not been rolled will be rolled with probability (6-A-B)/6; the condition is now (A, B+1)

E(A,B) = A/6 E(A,B) + B/6 E(A+1,B-1) + (6-A-B)/6 E(A,B+1)
6 E(A,B) = A E(A,B) + B E(A+1,B-1) + (6-A-B) E(A,B+1)
(6-A) E(A,B) = B E(A+1,B-1) + (6-A-B) E(A,B+1)
E(A,B) = B/(6-A) E(A+1,B-1) + (6-A-B)/(6-A) E(A,B+1)
E(A,B) = B/(6-A) E(A+1,B-1) + (1 - B/(6-A)) E(A,B+1)

E(5,1) = 6
E(5,0) = 12
E(4,2) = 9
E(4,1) = 27 / 2
E(4,0) = 33 / 2
E(3,3) = 11
E(3,2) = 44 / 3
E(3,1) = 311 / 18
E(3,0) = 347 / 18
E(2,4) = 25 / 2
E(2,3) = 125 / 8
E(2,2) = 2,585 / 144
E(2,1) = 11,395 / 576
E(2,0) = 12,259 / 576
E(1,5) = 137 / 10
E(1,4) = 411 / 25
E(1,3) = 111,281 / 6,000
E(1,2) = 3,643,433 / 180,000
E(1,1) = 38,969,339 / 1,800,000
E(1,0) = 41,129,339 / 1,800,000
E(0,6) = 147 / 10
E(0,5) = 343 / 20
E(0,4) = 171,731 / 9,000
E(0,3) = 2,479,351 / 120,000
E(0,2) = 118,749,869 / 5,400,000
E(0,1) = 374,768,681 / 16,200,000
E(0,0) = 390,968,681 / 16,200,000 = 24.1338691975309
You can't get much more "closed form" than a rational number
Yes, that fraction is in lowest terms; the largest prime factor of 16,200,000 is 5, and 390,968,681 is not a multiple of 2, 3, or 5




I agree with the answer and a satisfactory solution. One more beer to you, sir.

However, we may have a different understanding of what "closed form" means. I'm looking for a way to take the puzzle from a word problem to a math problem to solve. You might say that you did that with the division symbol, but there is no way somebody would understand how you got there with just that. What I'm thinking of a "closed form" for this problem, I could write on my hand with a sharpie and also expresses what's being asked in math terms.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
March 21st, 2020 at 5:40:09 PM permalink
Quote: Wizard


I agree with the answer and a satisfactory solution. One more beer to you, sir.

However, we may have a different understanding of what "closed form" means. I'm looking for a way to take the puzzle from a word problem to a math problem to solve. You might say that you did that with the division symbol, but there is no way somebody would understand how you got there with just that. What I'm thinking of a "closed form" for this problem, I could write on my hand with a sharpie and also expresses what's being asked in math terms.



I think what you really want is a general solution.

As for the beer, you can put the cost towards the bill at the next Spring Fling. I don't know why, but pretty much all beers taste the same to me - at last year's Spring Fling, I ordered the five-beer sampler at Triple 7 (High Roller Gold, Double Down Hefeweizen, Marker Pale Ale, Royal Red (ale), Black Chip Porter) and couldn't tell one from another.

gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
March 22nd, 2020 at 9:45:57 AM permalink
Quote: ThatDonGuy


Let E(A,B) be the expected number of rolls needed to have every number rolled at least twice given that A numbers have already been rolled at least twice and B numbers have been rolled exactly once (and the remaining (6 - A - B) have not been rolled at all)

E(6,0) = 0
At condition (A,B):
One of the A numbers that has been rolled at least twice will be rolled with probability A/6; the condition will remain at (A,B)
One of the B numbers that has been rolled exactly once will be rolled with probability B/6;
there is now one more "rolled at least twice" number and one fewer "rolled exactly once" number than before, so the condition is now (A+1, B-1)
One of the (6-A-B) numbers that has not been rolled will be rolled with probability (6-A-B)/6; the condition is now (A, B+1)

E(A,B) = A/6 E(A,B) + B/6 E(A+1,B-1) + (6-A-B)/6 E(A,B+1)
6 E(A,B) = A E(A,B) + B E(A+1,B-1) + (6-A-B) E(A,B+1)
(6-A) E(A,B) = B E(A+1,B-1) + (6-A-B) E(A,B+1)
E(A,B) = B/(6-A) E(A+1,B-1) + (6-A-B)/(6-A) E(A,B+1)
E(A,B) = B/(6-A) E(A+1,B-1) + (1 - B/(6-A)) E(A,B+1)

E(5,1) = 6
E(5,0) = 12
E(4,2) = 9
E(4,1) = 27 / 2
E(4,0) = 33 / 2



So, here is my question for ThatDonGuy

E(4,1) = 1/2 E(5,0) + 1/2 E(4,2)
but since e(5,0) = 12 and E(4,2) = 9

E(4,1) = 12/2+ 9/2 =21/2

So, why is E(4,1) =27/2 on your list?
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
March 22nd, 2020 at 12:54:03 PM permalink
Quote: gordonm888



So, here is my question for ThatDonGuy

E(4,1) = 1/2 E(5,0) + 1/2 E(4,2)
but since e(5,0) = 12 and E(4,2) = 9

E(4,1) = 12/2+ 9/2 =21/2

So, why is E(4,1) =27/2 on your list?


Because, OOPS, the listed formula isn't correct, although the answer did use the correct formula.

E(A,B) = A/6 E(A,B) + B/6 E(A+1,B-1) + (6-A-B)/6 E(A,B+1)
should be:
E(A,B) = 1 + A/6 E(A,B) + B/6 E(A+1,B-1) + (6-A-B)/6 E(A,B+1)
6 E(A,B) = 6 + A E(A,B) + B E(A+1,B-1) + (6-A-B) E(A,B+1)
(6-A) E(A,B) = 6 + B E(A+1,B-1) + (6-A-B) E(A,B+1)
E(A,B) = 6/(6-A) + B/(6-A) E(A+1,B-1) + (6-A-B)/(6-A) E(A,B+1)
E(A,B) = 6/(6-A) + B/(6-A) E(A+1,B-1) + (1 - B/(6-A)) E(A,B+1)

E(6,0) = 0
E(5,1) = 6/(6-5) + 1/5 x 0 + 4/5 x 0 = 6
E(5,0) = 6/(6-5) + 0 + 1 x E(5,1) = 6 + 6 = 12
E(4,2) = 6/(6-4) + 1 x E(5,1) + 0 = 3 + 6 = 9
E(4,1) = 6/(6-4) + 1/2 x E(5,0) + 1/2 x E(4,2) = 3 + 6 + 9/2 = 27/2

gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
March 22nd, 2020 at 5:41:53 PM permalink
Quote: ThatDonGuy

Quote: gordonm888



So, here is my question for ThatDonGuy

E(4,1) = 1/2 E(5,0) + 1/2 E(4,2)
but since e(5,0) = 12 and E(4,2) = 9

E(4,1) = 12/2+ 9/2 =21/2

So, why is E(4,1) =27/2 on your list?


Because, OOPS, the listed formula isn't correct, although the answer did use the correct formula.

E(A,B) = A/6 E(A,B) + B/6 E(A+1,B-1) + (6-A-B)/6 E(A,B+1)
should be:
E(A,B) = 1 + A/6 E(A,B) + B/6 E(A+1,B-1) + (6-A-B)/6 E(A,B+1)
6 E(A,B) = 6 + A E(A,B) + B E(A+1,B-1) + (6-A-B) E(A,B+1)
(6-A) E(A,B) = 6 + B E(A+1,B-1) + (6-A-B) E(A,B+1)
E(A,B) = 6/(6-A) + B/(6-A) E(A+1,B-1) + (6-A-B)/(6-A) E(A,B+1)
E(A,B) = 6/(6-A) + B/(6-A) E(A+1,B-1) + (1 - B/(6-A)) E(A,B+1)

E(6,0) = 0
E(5,1) = 6/(6-5) + 1/5 x 0 + 4/5 x 0 = 6
E(5,0) = 6/(6-5) + 0 + 1 x E(5,1) = 6 + 6 = 12
E(4,2) = 6/(6-4) + 1 x E(5,1) + 0 = 3 + 6 = 9
E(4,1) = 6/(6-4) + 1/2 x E(5,0) + 1/2 x E(4,2) = 3 + 6 + 9/2 = 27/2



Ah, yes, and I also see why that extra term must be in those expressions. Many thanks!
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
March 22nd, 2020 at 7:46:56 PM permalink
For each of ThatDonGuy's E(A,B) here are the prime factors of the numerators

Prime Factors of E(A,B) Numerator
E(6,0) = 0
E(5,1) = 2*3
E(5,0) = 2*2*3
E(4,2) = 3*3
E(4,1) = 3*3*3
E(4,0) = 3*11
E(3,3) = 11 (prime)
E(3,2) = 2*2*11
E(3,1) = 311 (prime)
E(3,0) = 347 (prime)
E(2,4) = 5*5
E(2,3) = 5*5*5
E(2,2) = 5*11*47
E(2,1) =5*43*53
E(2,0) = 13*23*41
E(1,5) = 137 (prime)
E(1,4) = 3*137
E(1,3) = 257*433
E(1,2) = 43*84,731
E(1,1) = 38,969,339 (prime)
E(1,0) = 41,129,339 (prime)
E(0,6) = 7*7*3
E(0,5) = 7*7*7
E(0,4) = 7*24533
E(0,3) = 7*354,193
E(0,2) = 7*16,964,267
E(0,1) = 7*101*113*4691
E(0,0) = 19*20,577,299

There are some interesting patterns here, although the data set is small.

For A even and B >0, E(A,B) denominator is divisible by (7-A)
For A even and A+B=5, E(A,B) denominator = (7-A)^3
The location of primes and some semiprimes is also intriguing:
Example: Denominator is prime when A=1,3 and B=0,1,(6-A).
Last edited by: gordonm888 on Mar 22, 2020
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
March 23rd, 2020 at 5:02:46 PM permalink
Here is how to solve the problem at hand using the Ace2 exponential distribution method.

For any given side, after x years, the probability it has not been rolled is exp(-x/6).

For any given side, after x years, the probability it has been rolled once is exp(-x/6) * (x/6), per the Poisson distribution.

For any given, after x years, the probability it has been rolled twice or more is 1- exp(-x/6)*(1 + x/6)

So, for all six faces, the answer can be expressed as:

Integral from 0 to infinity of 1- (1 - exp(-x/6)*(1 + x/6))^6 dx = apx. 24.1338692
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
March 23rd, 2020 at 8:30:42 PM permalink
Quote: Wizard

Here is how to solve the problem at hand using the Ace2 exponential distribution method.

For any given side, after x years, the probability it has not been rolled is exp(-x/6).

For any given side, after x years, the probability it has been rolled once is exp(-x/6) * (x/6), per the Poisson distribution.

For any given, after x years, the probability it has been rolled twice or more is 1- exp(-x/6)*(1 + x/6)

So, for all six faces, the answer can be expressed as:

Integral from 0 to infinity of 1- (1 - exp(-x/6)*(1 + x/6))^6 dx = apx. 24.1338692

And to reiterate why this works. If state A represents success, meaning all 6 faces have been rolled twice or more, then that state is described by: A = 1- exp(-x/6)*(1 + x/6). You are integrating (1 - A) which sums the probability of not being in state A over all time. That sum is the expected value for A to occur, a useful property common to geometric and exponential distributions.
It’s all about making that GTA
  • Jump to: