Author |
Topic: Throwing All Numbers From 2 to 12 (Read 1192 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Throwing All Numbers From 2 to 12
« on: Jul 11th, 2008, 7:35pm » |
 Quote  Modify
|
What is the expected number of times one must throw two dice before all numbers from 2 to 12 have appeared?
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Throwing All Numbers From 2 to 12
« Reply #1 on: Jul 12th, 2008, 4:44am » |
Quote Modify
|
You could use the 211x211 transition matrix to get the answer.
Hopefully there's an easier way, though.
|
| « Last Edit: Jul 12th, 2008, 4:44am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Throwing All Numbers From 2 to 12
« Reply #2 on: Jul 12th, 2008, 5:44am » |
Quote Modify
|
I get 769767316159/12574325400:
| hidden: | -36*Sum (-1)|S|/sum(S)
over all nonempty (multi-)subsets S of {1,2,3,4,5,6,5,4,3,2,1}. |
Can we evaluate this in polynomial time (in the number of faces)?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Throwing All Numbers From 2 to 12
« Reply #3 on: Jul 12th, 2008, 6:14am » |
Quote Modify
|
on Jul 12th, 2008, 5:44am, Eigenray wrote:| I get 769767316159/12574325400 |
|
I get a lower number in simulation: about 45. And as these things go, I'd almost suspect it's a nice round number.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Throwing All Numbers From 2 to 12
« Reply #4 on: Jul 12th, 2008, 7:30am » |
Quote Modify
|
My simulation agrees with my answer:
Code:int main () {
int got[11];
int i,t,n,g;
for(t=n=0; ; n++) {
for(i=0; i<11; i++) got[i]=0;
for(g=0; g<11; t++) {
i=rand()%6+rand()%6;
if(!got[i]) {
got[i]=1; g++;
}
}
printf("%f\n",1.*t/n);
}
} |
|
|
| « Last Edit: Jul 12th, 2008, 7:37am by Eigenray » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Throwing All Numbers From 2 to 12
« Reply #5 on: Jul 12th, 2008, 8:00am » |
Quote Modify
|
on Jul 12th, 2008, 6:14am, towr wrote:
I get a lower number in simulation: about 45. And as these things go, I'd almost suspect it's a nice round number.
|
|
But even with one die it is 14.7, not a very round number.
on Jul 12th, 2008, 7:30am, Eigenray wrote:| My simulation agrees with my answer: |
|
Then your simulation must be correct.  A few years ago, I chucked this to the piranhas on sci.math.
|
| « Last Edit: Jul 12th, 2008, 8:04am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Throwing All Numbers From 2 to 12
« Reply #6 on: Jul 12th, 2008, 8:46am » |
Quote Modify
|
I got my answer using inclusion-exclusion. Actually, that sum can be computed in O(n3) time with dynamic programming.
If E(n) is the expected number of throws for a pair of n-dice, it looks like E(n)/n2 converges to around 1.702955978958. What is this number?
What if we simplified it a bit: suppose the probability of rolling k is directly proportional to k, 1  k n. Show that the expected time E(n) to obtain all values from 1 through n satisfies
limit E(n)/n2 = 2 / 3 - 3. 
|
| « Last Edit: Jul 14th, 2008, 10:08am by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Throwing All Numbers From 2 to 12
« Reply #7 on: Jul 12th, 2008, 10:10am » |
Quote Modify
|
on Jul 12th, 2008, 8:00am, ThudanBlunder wrote:| But even with one die it is 14.7, not a very round number. |
|
Well, it's not too bad; at least it's a finite decimal.
on Jul 12th, 2008, 7:30am, Eigenray wrote:| My simulation agrees with my answer: |
|
Hmm  I'll have to think about what was wrong with mine then (I did it in javascript and ran it in the location-bar, so I don't actually have the code anymore). But it was exactly the same approach.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mattian
Senior Riddler
 
Gender:
Posts: 404
|
|
Re: Throwing All Numbers From 2 to 12
« Reply #8 on: Jul 23rd, 2008, 8:12am » |
Quote Modify
|
The answer to this could be useful in determining the worst case domain of the 100 prisoners/lightbulb problem.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print