50 states, 10 at a time
March 23rd, 2012 at 4:55:55 AM
permalink
NOTE: This is not a homework question!
I am the substitute teacher for a 5th grade (10 year olds) class today. The plans from the regular teacher says that for a morning activity, each student should write down 10 U.S. states and capitals. There are 21 students in the class.
I posed a challenge: Without peeking or helping each other, can the entire class come up with all 50 states?
In other words, when combining all 210 states, will each of the 50 individual states be represented on the list?
Mathematically, here is the problem:
What is the probability that 21 people, each randomly choosing 10 different items from a list of 50, will have all 50 distinct items picked among their collective lists?
I told the class I would try to figure out the probability myself, but that I would also pose the problem to "mathematical experts" on an Internet forum. If you have the time, and want to exercise your brain, I'd appreciate any input you have. I will report any answers you give at the end of today (or on Monday), and also let you know if they accomplished the feat.
I am the substitute teacher for a 5th grade (10 year olds) class today. The plans from the regular teacher says that for a morning activity, each student should write down 10 U.S. states and capitals. There are 21 students in the class.
I posed a challenge: Without peeking or helping each other, can the entire class come up with all 50 states?
In other words, when combining all 210 states, will each of the 50 individual states be represented on the list?
Mathematically, here is the problem:
What is the probability that 21 people, each randomly choosing 10 different items from a list of 50, will have all 50 distinct items picked among their collective lists?
I told the class I would try to figure out the probability myself, but that I would also pose the problem to "mathematical experts" on an Internet forum. If you have the time, and want to exercise your brain, I'd appreciate any input you have. I will report any answers you give at the end of today (or on Monday), and also let you know if they accomplished the feat.
-Dween!
March 23rd, 2012 at 5:03:44 AM
permalink
Quote: DweenMathematically, here is the problem:
What is the probability that 21 people, each randomly choosing 10 different items from a list of 50, will have all 50 distinct items picked among their collective lists?
I don't know the mathematical probability but I'm very excited to find out if they actually accomplish this.
1) Will they be working in any sort of groups, or completely independently?
2) Do they have to get the correct city for the state capitals for it to count for our example here? (like if somebody puts St Louis as the capital of Missouri, is that a count towards Missouri, or not?)
3) What state (or more importantly region) are you located?
My feeling is they will not accomplish this independently. However, knowing your region, I would make a small wager that anywhere from 20-35 states will be covered. In fact, knowing what state your school is in, I'd be willing to make a guess at the 20 most common answers that will appear, at least for states.
"One out of every four people are [morons]"- Kyle, South Park
March 23rd, 2012 at 5:06:38 AM
permalink
No, it's a "teacherwork" problem. LOL.Quote: DweenNOTE: This is not a homework question!
The math escapes me, but bear in mind that the math presented will be based upon complete randomness. That is not the case with this assignment. Your question to the students is biased by proximity. I.E. They are most likely to name the nearby states.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
March 23rd, 2012 at 5:39:57 AM
permalink
If they get it will depend a great deal on how you ask the question, and a few other things IMHO.
First, consider your home state and its neighbors will be picked more than a random sample would indicate.
Second, if there are some transplants in your class, their old states will get picked more often.
Third, states that students have traveled to will get picked more often. For 5th grade this means CA/FL as homes to Disney resort properties will be more visited than say UT/WY to name two.
If there is a map in the room, expect the larger-geographical states to be picked. As a side exercise, see how long it takes 2 adults to come up with all the states when no map is present. It is not as easy as you think.
Finally, are you telling them to "name 10 states" or "name 10 while trying to get them all as a group." Even 5th graders will have a few people pick the obscure ones to try and reach the group goal. If you make it 10 individual goals they will just pick 10.
As to the random probability, I will let the math-people here do it as they will get it right if 1/100 the time I can figure it out.
First, consider your home state and its neighbors will be picked more than a random sample would indicate.
Second, if there are some transplants in your class, their old states will get picked more often.
Third, states that students have traveled to will get picked more often. For 5th grade this means CA/FL as homes to Disney resort properties will be more visited than say UT/WY to name two.
If there is a map in the room, expect the larger-geographical states to be picked. As a side exercise, see how long it takes 2 adults to come up with all the states when no map is present. It is not as easy as you think.
Finally, are you telling them to "name 10 states" or "name 10 while trying to get them all as a group." Even 5th graders will have a few people pick the obscure ones to try and reach the group goal. If you make it 10 individual goals they will just pick 10.
As to the random probability, I will let the math-people here do it as they will get it right if 1/100 the time I can figure it out.
All animals are equal, but some are more equal than others
March 23rd, 2012 at 6:00:02 AM
permalink
As DJTeddyBear pointed out, there may be some bias among the students, such as always naming their own state or neighboring states. To eliminate the bias, let's rephrase the problem as follows:
What is the probability that 21 quick-pick lottery tickets, where each ticket contains 10 numbers from 1 to 50 inclusive (without repetition), will encompass all of the numbers from 1 to 50 at least once?
The answer appears to be approximately 28/45 = 0.622222222...
Does anyone know why?
What is the probability that 21 quick-pick lottery tickets, where each ticket contains 10 numbers from 1 to 50 inclusive (without repetition), will encompass all of the numbers from 1 to 50 at least once?
The answer appears to be approximately 28/45 = 0.622222222...
Does anyone know why?
March 23rd, 2012 at 6:30:12 AM
permalink
The are allowed to use a map. Some chose to do so, some did not.
I will accept "wrong" answers for the sake of this exercise. If the capital is incorrect, I will credit them with the state.
My school is located in Kentucky.
I gave instructions to work independently, to not look at other papers or discuss answers. Each person should come up with 10 on their own.
I also told them to try to come up with all 50 as a class, and not to out-think their fellow classmates.
So while the math will lead to a "random probability" answer, it is true that the minds of fifth graders in this exercise will not necessarily operate randomly.
I will accept "wrong" answers for the sake of this exercise. If the capital is incorrect, I will credit them with the state.
My school is located in Kentucky.
I gave instructions to work independently, to not look at other papers or discuss answers. Each person should come up with 10 on their own.
I also told them to try to come up with all 50 as a class, and not to out-think their fellow classmates.
So while the math will lead to a "random probability" answer, it is true that the minds of fifth graders in this exercise will not necessarily operate randomly.
-Dween!
March 23rd, 2012 at 6:40:18 AM
permalink
Quote: JBAs DJTeddyBear pointed out, there may be some bias among the students, such as always naming their own state or neighboring states. To eliminate the bias, let's rephrase the problem as follows:
What is the probability that 21 quick-pick lottery tickets, where each ticket contains 10 numbers from 1 to 50 inclusive (without repetition), will encompass all of the numbers from 1 to 50 at least once?
The answer appears to be approximately 28/45 = 0.622222222...
Does anyone know why?
e, the natural log comes into play doesn't it?
"Then you can admire the real gambler, who has neither eaten, slept, thought nor lived, he has so smarted under the scourge of his martingale, so suffered on the rack of his desire for a coup at trente-et-quarante" - Honore de Balzac, 1829
March 23rd, 2012 at 6:53:59 AM
permalink
Quote: thecesspite, the natural log comes into play doesn't it?
It does as a way to estimate the answer. The condition about each student picking 10 different names makes this more challenging. Let me get back to that and pose an alternative easy version of the problem, as follows.
Wizard partial credit version: Each box of cereal has one of 50 prizes inside. Each box has an equal chance of having each prize. You buy 210 boxes of cereal. What are the chances you will get all 50 prizes?
Here is my estimated answer.
It will take on average (50/50)+(50/49)+(50/48)+...+(50/2)+(50/1)=224.9602669 boxes to get all 50. The 50/50 is the number of boxes to get the first unique prize, 50/49 the second one, 50/48 the third, and so on.
Let's assume that this time to completion follows an exponential distribution. In other words, success could happen any time. Much like hitting a royal flush in video poker, success never becomes due. Waiting doesn't help, each moment (or bet) has the same chance of success. I know this is not exactly appropriate, because success hasn't happen in 49 or less trials. However, this is just an estimate.
The exponential distribution suggests that the probability of success within 210 units of time is 1-e^(210/224.96) = 60.68%.
If the original problem the odds will be higher, because each student must pick 10 different states. Thus JB's answer above seems reasonable to me, but I don't know why it is exactly 28/45, assuming that is correct, but am eager to see his solution (other than a simulation).
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 23rd, 2012 at 7:02:13 AM
permalink
Quote: WizardJB's answer above seems reasonable to me, but I don't know why it is exactly 28/45, assuming that is correct, but am eager to see his solution (other than a simulation).
Unfortunately, a simulation is my "solution" for now...
I can't help but think that there must be a simple Excel function or formula for this, using 3 input variables (10, 50, and 21 in this case). I have come across this type of problem before and wanted a solution for it, so I'm interested in discovering or learning the formula, if it exists (intuition tells me that it must!).
March 23rd, 2012 at 7:41:57 AM
permalink
Is the reason this is "partial" credit because this violates one of the premises of the original question?Quote: WizardWizard partial credit version: Each box of cereal has one of 50 prizes inside. Each box has an equal chance of having each prize. You buy 210 boxes of cereal. What are the chances you will get all 50 prizes?
To go with your cereal box analogy, your 210 boxes are all random. That's not the premise. You have to take 21 groups of 10 boxes. Within each group of ten, there will be no duplication. THEN the question is, within these 21 groups of 10, what are the cnaces of getting all 50 prizes?
Then again, this assumes that these fifth graders in that class are bright enough to each provide 10 different state names. Are any of the kids likely to have a repeat on their paper?
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
March 23rd, 2012 at 8:57:08 AM
permalink
Results!
The most common states picked were Florida, California, and Nevada.
Kentucky did not show up as often as I thought it would.
They missed Pennsylvania.
49/50, so close!
I am doing brute-force trials to determine the probability... I'll update on that when I can.
The most common states picked were Florida, California, and Nevada.
Kentucky did not show up as often as I thought it would.
They missed Pennsylvania.
49/50, so close!
I am doing brute-force trials to determine the probability... I'll update on that when I can.
-Dween!
March 23rd, 2012 at 9:48:49 AM
permalink
Quote: WizardIt does as a way to estimate the answer. The condition about each student picking 10 different names makes this more challenging. Let me get back to that and pose an alternative easy version of the problem, as follows.
Wizard partial credit version: Each box of cereal has one of 50 prizes inside. Each box has an equal chance of having each prize. You buy 210 boxes of cereal. What are the chances you will get all 50 prizes?
Here is my estimated answer.
It will take on average (50/50)+(50/49)+(50/48)+...+(50/2)+(50/1)=224.9602669 boxes to get all 50. The 50/50 is the number of boxes to get the first unique prize, 50/49 the second one, 50/48 the third, and so on.
That was the way to find a simple answer I had in mind when I posted about "e", but didn't want the effort of typing on my touch screen reader.
The 10 picks variant we have here is interesting, as it's also relates to the number of packs of hockey cards/baseball cards you might need to buy to get a full set (if they have all the same rarity) or even the number of packs to buy get all the commonest cards in a trading card game (as I think you can assume there's never duplicates inside a pack).
Here's one way of looking at this again
Select 10 cards from a deck of 52 playing cards. Then do the same from a different deck of 52 paying cards. What are the chances of at least 1 match?
Chance of no match :
1st card not matching = 42/52 (42 cards in my deck don't match, 52 to select from)
2nd card not matching = 41/51 (41 card in my deck don't match, only 51 left to select from)
...
10th card not matching = 33/43
=> No match = (33*34...*42)/(43*44*...*52) = 9.3% chance there's not at least one match.
=> For 50 states => 8.25% chance two students don't have a match between them (assuming picking at random)
Please check my work. I'm relatively surprised the chance of two hands of 10 cards having a match is so high. If it is right, looks like a good prop bet to me to try one day:) (I realize this is similar to the 25 people will probably have a birthday in common).
"Then you can admire the real gambler, who has neither eaten, slept, thought nor lived, he has so smarted under the scourge of his martingale, so suffered on the rack of his desire for a coup at trente-et-quarante" - Honore de Balzac, 1829
March 23rd, 2012 at 10:51:52 AM
permalink
Back to the original problem...
After a short 100 trials, it seems that the number of successful 50 state hit for 21 students/10 states each is in the 65-69% range. I do not have a formula yet, but I feel someone was on the right track with the deck of cards analogy.
After a short 100 trials, it seems that the number of successful 50 state hit for 21 students/10 states each is in the 65-69% range. I do not have a formula yet, but I feel someone was on the right track with the deck of cards analogy.
-Dween!
March 23rd, 2012 at 11:03:17 AM
permalink
Quote: DweenBack to the original problem...
After a short 100 trials, it seems that the number of successful 50 state hit for 21 students/10 states each is in the 65-69% range. I do not have a formula yet, but I feel someone was on the right track with the deck of cards analogy.
That is indeed a very small sample.
I am trying to work on a possible formula for the bigger picture. Namely, a function using the three input variables (let's call them x, y, and z). In the original problem:
x = 10
y = 50
z = 21
What I am doing is running a simulation for varying values of x, y, and z where all of the following criteria are true:
3 ≤ x ≤ 10
10 ≤ y ≤ 50
5 ≤ z ≤ 50
(x * z) ≥ y
There are 14,578 valid x,y,z combinations meeting this criteria. Next, what I'm attempting to do is figure out how the (simulated) probability relates to the three parameters.
It's not going to be quick though! About 400 million simulations are done, but split across the 14,578 rows that's an average of 27,439 trials per row, which is still a very small sample size.
When I estimated 28/45 as the solution for the original problem, it was based on a simulation of hundreds of millions of trials.
March 23rd, 2012 at 12:30:17 PM
permalink
Let's build the question bit by bit.
Assume a list size (L), number of players (P), and how many items each player chooses (C).
L = 2, P = 2, C = 1
Possibilities: AA, AB, BA, BB
Win: 2/4
Lose: 2/4
L = 2, P = 3, C = 1
Possibilities: AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB
Win: 6/8
Lose: 2/8
L = 3, P = 3, C = 1
Possibilities: AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC
Win: 6/27
Lose: 21/27
L = 3, P = 2, C = 2
Possibilities: AB.AB, AB.AC, AB.BC, AC.AB, AC.AC, AC.BC, BC.AB, BC.AC, BC.BC
Win: 6/9
Lose: 3/9
L = 3, P = 3, C = 2
Possibilities: AB.AB.AB, AB.AB.AC, AB.AB.BC, AB.AC.AB, AB.AC.AC, AB.AC.BC, AB.BC.AB, AB.BC.AC, AB.BC.BC, AC.AB.AB, AC.AB.AC, AC.AB.BC, AC.AC.AB, AC.AC.AC, AC.AC.BC, AC.BC.AB, AC.BC.AC, AC.BC.BC, BC.AB.AB, BC.AB.AC, BC.AB.BC, BC.AC.AB, BC.AC.AC, BC.AC.BC, BC.BC.AB, BC.BC.AC, BC.BC.BC
Win: 24/27
Lose: 3/27
Can a formula be derived for parts of it based on these low-level examples?
Assume a list size (L), number of players (P), and how many items each player chooses (C).
L = 2, P = 2, C = 1
Possibilities: AA, AB, BA, BB
Win: 2/4
Lose: 2/4
L = 2, P = 3, C = 1
Possibilities: AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB
Win: 6/8
Lose: 2/8
L = 3, P = 3, C = 1
Possibilities: AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC
Win: 6/27
Lose: 21/27
L = 3, P = 2, C = 2
Possibilities: AB.AB, AB.AC, AB.BC, AC.AB, AC.AC, AC.BC, BC.AB, BC.AC, BC.BC
Win: 6/9
Lose: 3/9
L = 3, P = 3, C = 2
Possibilities: AB.AB.AB, AB.AB.AC, AB.AB.BC, AB.AC.AB, AB.AC.AC, AB.AC.BC, AB.BC.AB, AB.BC.AC, AB.BC.BC, AC.AB.AB, AC.AB.AC, AC.AB.BC, AC.AC.AB, AC.AC.AC, AC.AC.BC, AC.BC.AB, AC.BC.AC, AC.BC.BC, BC.AB.AB, BC.AB.AC, BC.AB.BC, BC.AC.AB, BC.AC.AC, BC.AC.BC, BC.BC.AB, BC.BC.AC, BC.BC.BC
Win: 24/27
Lose: 3/27
Can a formula be derived for parts of it based on these low-level examples?
-Dween!
March 23rd, 2012 at 12:31:48 PM
permalink
I moved the geography-related posts to a new thread, in an effort to try to keep this thread math-related.
March 23rd, 2012 at 12:45:53 PM
permalink
Okay, I'm trying to pick apart what could be the formula for this. I think the following is a good start. I'm going to use my lottery example again, but if you wanted to fit it to the original problem, just replace "lottery ticket" with "student" and "[lottery] number" with "state".
Suppose you have 5 lottery tickets, each with 4 numbers from 1 to 20:
x = 4 (numbers per ticket)
y = 20 (lottery numbers to choose from)
z = 5 (tickets you have)
Now, if we were to encompass all 20 numbers once, we would need at least y/x = 20/4 = 5 tickets, which is exactly how many we have. So let's figure out the probability of our 5 tickets encompassing all 20 numbers:
The first ticket can contain any 4 of the 20 numbers = combin(20,4) = 4,845
The second ticket can contain any 4 of the 16 remaining numbers = combin(16,4) = 1,820
The third ticket can contain any 4 of the 12 remaining numbers = combin(12,4) = 495
The fourth ticket can contain any 4 of the 8 remaining numbers = combin(8,4) = 70
And the fifth ticket must contain the last 4 remaining numbers = combin(4,4) = 1
So, the number of ways that 5 tickets can cover all 20 numbers is 4845 * 1820 * 495 * 70 * 1 = 305,540,235,000
The total number of possible combinations per ticket is combin(20,4) = 4,845
There are 5 tickets, so there are 48455 = 2,669,739,621,799,528,125 possible permutations of 5 tickets (because some tickets could be identical)
Therefore the probability of 5 tickets encompassing all 20 numbers is 305,540,235,000/2,669,739,621,799,528,125 = 0.00000011444570568048569989102297526146 = 1 in 8,737,767.783
Does this sound correct so far? If so, the next step is to figure out how having more than the bare minimum number of tickets would affect the probability, and then figuring out how to accommodate numbers that aren't so nice and round (for example, x = 5, y = 31, z = 7).
Suppose you have 5 lottery tickets, each with 4 numbers from 1 to 20:
x = 4 (numbers per ticket)
y = 20 (lottery numbers to choose from)
z = 5 (tickets you have)
Now, if we were to encompass all 20 numbers once, we would need at least y/x = 20/4 = 5 tickets, which is exactly how many we have. So let's figure out the probability of our 5 tickets encompassing all 20 numbers:
The first ticket can contain any 4 of the 20 numbers = combin(20,4) = 4,845
The second ticket can contain any 4 of the 16 remaining numbers = combin(16,4) = 1,820
The third ticket can contain any 4 of the 12 remaining numbers = combin(12,4) = 495
The fourth ticket can contain any 4 of the 8 remaining numbers = combin(8,4) = 70
And the fifth ticket must contain the last 4 remaining numbers = combin(4,4) = 1
So, the number of ways that 5 tickets can cover all 20 numbers is 4845 * 1820 * 495 * 70 * 1 = 305,540,235,000
The total number of possible combinations per ticket is combin(20,4) = 4,845
There are 5 tickets, so there are 48455 = 2,669,739,621,799,528,125 possible permutations of 5 tickets (because some tickets could be identical)
Therefore the probability of 5 tickets encompassing all 20 numbers is 305,540,235,000/2,669,739,621,799,528,125 = 0.00000011444570568048569989102297526146 = 1 in 8,737,767.783
Does this sound correct so far? If so, the next step is to figure out how having more than the bare minimum number of tickets would affect the probability, and then figuring out how to accommodate numbers that aren't so nice and round (for example, x = 5, y = 31, z = 7).
March 23rd, 2012 at 1:41:11 PM
permalink
Haha, this brings back memories...the hardest class assigment I EVER had...
To pass 7th Grade History, we had to draw a map with ALL 50 states AND their capitals!
Well, sorta..
We had a map of the USA, AND the states were drawn out...but once you get up to the NewEngland area, it gets real fucking tough.
Stipulation..you COULD NOT MISS ONE..however, you could retake it as many times as needed (only once a week though, so I guess you technically got like 20 chances)
To tell you the truth, I cheated...I got SO close on one try (like I missed 4 and it was only their capitals that I missed up in the Tiny State area). that I just wrote down on my hand the capitals of the NE states (not the whole words of course)
TO THIS DAY, hardest thing I've ever had to do (and resulted that I HAD to cheat)
To pass 7th Grade History, we had to draw a map with ALL 50 states AND their capitals!
Well, sorta..
We had a map of the USA, AND the states were drawn out...but once you get up to the NewEngland area, it gets real fucking tough.
Stipulation..you COULD NOT MISS ONE..however, you could retake it as many times as needed (only once a week though, so I guess you technically got like 20 chances)
To tell you the truth, I cheated...I got SO close on one try (like I missed 4 and it was only their capitals that I missed up in the Tiny State area). that I just wrote down on my hand the capitals of the NE states (not the whole words of course)
TO THIS DAY, hardest thing I've ever had to do (and resulted that I HAD to cheat)
Gambling calls to me...like this ~> http://www.youtube.com/watch?v=4Nap37mNSmQ
March 23rd, 2012 at 2:46:46 PM
permalink
A quick attempt (probably wrong) on the original question
Combs of Child 1: comb(50,10)= 10.272.278.170
Combs of child 1 not chosing State 1 (S1): Comb(49,10)=8.217.822.536
Prob of child 1 not chosing S1:comb(49,10)/comb(50,10) = 20% The same as the simple 40/50
Prob of all childs not chosing S1: 20%^21 = 0,922337203685472%
Prob of all childs not chosing S1,S2...S50 : 0,922337203685472% x 50 = 46,12% io
There is though double counting in the above 46.12%. You cannot add up 0,922337203685472% 50 times because there are probs for S1 and S2 not chosen included in each. The same for S1 and S3 etc and for 3 states not included etc.
So, for 2 States
Combs for Child 1 not chosing S1 and S2: comb(48,10) = 6.540.715.896
Prob for Child 1 not chosing S1 and S2: comb(48,10)/comb(50,10)= 63,67%
Prob of all childs not chosing S1 and S2: 63,67%^21 = 0,00764062339284084%
Combs for chosing 2 states out of 50: comb(50,2) = 1225
Prob for all childs not chosing any 2 states: = 0,00764062339284084% x 1225 = 9.36%
3 States
Combs for Child 1 not chosing S1 and S2 and S3 : comb(47,10) = 5.178.066.751
Prob for Child 1 not chosing S1 and S2 and S3 : comb(47,10)/comb(50,10)= 50,41%
Prob of all childs not chosing S1 and S2 and S3: 50,41%^21 = 0,0000565611639236469%
Combs for chosing 3 states out of 50: comb(50,3) = 19600
Prob for all childs not chosing any 3 states: = 0,0000565611639236469% x 19600 = 1.11%
And continung for 4 states, 5 states etc the numbers get very small
So deducting from the 46.12% the above numbers gives:
46.12% - 9.36% - 1.11% - 0.09% etc = 35.56% for at least 1 state not appearing
So for all states appearing: 1 - 35.56% = 64.44%
My exact nymber on a spreadsheet shows: 64,4419690148693%
Combs of Child 1: comb(50,10)= 10.272.278.170
Combs of child 1 not chosing State 1 (S1): Comb(49,10)=8.217.822.536
Prob of child 1 not chosing S1:comb(49,10)/comb(50,10) = 20% The same as the simple 40/50
Prob of all childs not chosing S1: 20%^21 = 0,922337203685472%
Prob of all childs not chosing S1,S2...S50 : 0,922337203685472% x 50 = 46,12% io
There is though double counting in the above 46.12%. You cannot add up 0,922337203685472% 50 times because there are probs for S1 and S2 not chosen included in each. The same for S1 and S3 etc and for 3 states not included etc.
So, for 2 States
Combs for Child 1 not chosing S1 and S2: comb(48,10) = 6.540.715.896
Prob for Child 1 not chosing S1 and S2: comb(48,10)/comb(50,10)= 63,67%
Prob of all childs not chosing S1 and S2: 63,67%^21 = 0,00764062339284084%
Combs for chosing 2 states out of 50: comb(50,2) = 1225
Prob for all childs not chosing any 2 states: = 0,00764062339284084% x 1225 = 9.36%
3 States
Combs for Child 1 not chosing S1 and S2 and S3 : comb(47,10) = 5.178.066.751
Prob for Child 1 not chosing S1 and S2 and S3 : comb(47,10)/comb(50,10)= 50,41%
Prob of all childs not chosing S1 and S2 and S3: 50,41%^21 = 0,0000565611639236469%
Combs for chosing 3 states out of 50: comb(50,3) = 19600
Prob for all childs not chosing any 3 states: = 0,0000565611639236469% x 19600 = 1.11%
And continung for 4 states, 5 states etc the numbers get very small
So deducting from the 46.12% the above numbers gives:
46.12% - 9.36% - 1.11% - 0.09% etc = 35.56% for at least 1 state not appearing
So for all states appearing: 1 - 35.56% = 64.44%
My exact nymber on a spreadsheet shows: 64,4419690148693%
March 23rd, 2012 at 4:41:35 PM
permalink
Quote: DweenThe most common states picked were Florida, California, and Nevada.
Kentucky did not show up as often as I thought it would.
Okay given the conditions you presented, I suppose you would get close.
My Top states would have been-
Alabama, Alaska, Arizona, Arkansas, California, Colorado, Connecticut, Delaware, Florida and Georgia - The first ten states in "Fifty Nifty United States"
Then Kentucky and their "rival" states- Indiana, Tennessee, Ohio
Then the easiest to identify states: Florida (already covered), California (already covered), Maine, Texas and Louisiana.
I'm VERY surprised Nevada is on the list... there must be some gamblin' parents in those classes!
"One out of every four people are [morons]"- Kyle, South Park
March 23rd, 2012 at 5:23:03 PM
permalink
Yes, this is a geography post rather than a math one, but I am replying to Dween's post above.Quote: DweenResults!
The most common states picked were Florida, California, and Nevada.
Kentucky did not show up as often as I thought it would.
Could it be that they had some interest in states where the capital is not even close to being the biggest city? That could be triggered by knowing that Frankfort is their capital rather than Lexington or Louisville. Of course, if there were really strong interest in that aspect, surely they would have included Pennsylvania, but I am wondering whether states like Illinois, Washington, and New Mexico were frequently listed as one of the ten because of their less prominent capitals.
I remember playing some states and capitals games with my father when I was about that age, and he felt I had something of an advantage because I had never heard of a lot of the cities he was familiar with -- I wasn't at as much risk of guessing Seattle or Spokane.
March 23rd, 2012 at 5:34:01 PM
permalink
I have calculated something, dont know if its correct but gives me 28.76117% that all 50 states appear in 210 trials....
March 23rd, 2012 at 5:44:49 PM
permalink
Okay, I have unofficially given up on this. I spent nearly all day on it. It is far more complex than it seems. I don't think it's something that a few formulas can solve. A simulation is most likely the best way to approximate the result. So I stand behind my estimate of 62.2% as the approximate answer to the original problem.
———————————————————————————————————————————————————————————————
EDIT: I think I got it! Given the initial problem, 21 students picking 10 states of 50, here is my formula:
x = 10
y = 50
z = 21
x * (x + y) * z
p = ————————————
(x - 1) * y * (y - (y / x))
———————————————————————————————————————————————————————————————
EDIT: I think I got it! Given the initial problem, 21 students picking 10 states of 50, here is my formula:
x = 10
y = 50
z = 21
x * (x + y) * z
p = ————————————
(x - 1) * y * (y - (y / x))
(...and now I will run and hide before anyone figures me out...)
March 23rd, 2012 at 6:08:01 PM
permalink
Quote: TiltpoulI'm VERY surprised Nevada is on the list... there must be some gamblin' parents in those classes!
Nevada is right next to California, and it has more stuff than LV (Death Valley, Hoover Dam, etc). It's hard to miss. Unlike say Tennessee... anyone remember the trip from Road to Rupert?
What's surprising is that PA was left out. Didn't anyone think of Penn State?
Resist ANFO Boston PRISM Stormfront IRA Freedom CIA Obama
March 23rd, 2012 at 6:38:04 PM
permalink
Quote: JB... Given the initial problem, 21 students picking 10 states of 50, here is my formula:
x = 10
y = 50
z = 21
x * (x + y) * z
p = ————————————
(x - 1) * y * (y - (y / x))(...and now I will run and hide before anyone figures me out...)
I guess I have to question the validity of your equation. Suppose each student were only allowed to name one state, i.e., x=1. It would be impossible for the 21 students to name all 50 states, so apparently for that case p=0.
However, your equation (with x=1, y=50, and z=21) appears to lead to:
p = ∞/0 = ∞
Your answer of 0.6222... for x=10 may be right (I have no idea), but I don't think the equation holds in general.
March 23rd, 2012 at 6:42:26 PM
permalink
Quote: DocI guess I have to question the validity of your equation.
And you would be correct to do so. I came up with a formula that equaled 28/45 (the approximation of my simulator's result) using only the input values of 10, 21, and 50. This is what happens when you spend all day working on something without getting anywhere. :)
March 23rd, 2012 at 6:45:28 PM
permalink
I thought you were going to run and hide. ???
;-)
;-)
March 24th, 2012 at 9:47:24 AM
permalink
Excel and I get 62.2155940976711 % .
“Man Babes” #AxelFabulous
March 24th, 2012 at 10:35:35 AM
permalink
Well, after not trying at all to solve this yesterday, and after criticizing JB's fictitious equation last night, I decided to give it a quick go today. I have no idea what kind of calculation miplet did in Excel, but here is the formula I used:
p = {1 - [(50 - 10)/50]^21 }^50 = 0.629198473
There is some simple probability theory math behind that formula, but I'm not sure I did it correctly. If anyone is interested, I will describe my thinking if it's not obvious. I have to take a reserved attitude toward my solution if the math folks feel this is a complex problem, because I really approached it a simple way.
Edit: Well, maybe just never mind. If I expose this formula to the same challenge I posed to JB (that if x=1 instead of x=10 then p=0) then my formula fails too. It gives p = 8.6645E-24, which is pretty dang small but not zero.
p = {1 - [(50 - 10)/50]^21 }^50 = 0.629198473
There is some simple probability theory math behind that formula, but I'm not sure I did it correctly. If anyone is interested, I will describe my thinking if it's not obvious. I have to take a reserved attitude toward my solution if the math folks feel this is a complex problem, because I really approached it a simple way.
Edit: Well, maybe just never mind. If I expose this formula to the same challenge I posed to JB (that if x=1 instead of x=10 then p=0) then my formula fails too. It gives p = 8.6645E-24, which is pretty dang small but not zero.
March 24th, 2012 at 12:42:46 PM
permalink
Quote: mipletExcel and I get 62.2155940976711 % .
I believe miplet's solution is perfectly accurate (and not just because it's right around the 62.2% that my simulator came up with).
March 24th, 2012 at 1:00:05 PM
permalink
Quote: JBI believe miplet's solution is perfectly accurate (and not just because it's right around the 62.2% that my simulator came up with).
So, miplet or JB, what's the equation that gives the 62.21559%, and how did you come up with it?
March 24th, 2012 at 1:14:44 PM
permalink
Quote: DocSo, miplet or JB, what's the equation that gives the 62.21559%, and how did you come up with it?
E = mc²
Just kidding, if course. If miplet is willing to share, I will let him. It's not exactly an equation; it is more like 1,000 equations. But I believe he both approached and solved it correctly.
March 24th, 2012 at 1:22:38 PM
permalink
I'll just copy and paste the PM I sent JB. I assume that its ok with him.
I'm not very good at explaining things, but here it goes:
Student 1 picks 10 states.
We then determine the percent of time student 2 will pick between 0 and 10 new states.
0 new states is COMBIN(10,10)*COMBIN(40,0) / COMBIN(50,10)
1 new state is COMBIN(10,9)*COMBIN(40,1) / COMBIN(50,10)
2 new states is COMBIN(10,8)*COMBIN(40,2) / COMBIN(50,10)
...
9 new states is COMBIN(10,1)*COMBIN(40,9) / COMBIN(50,10)
10 new states is COMBIN(10,0)*COMBIN(40,10) / COMBIN(50,10)
We should now have a list of probabilities for 10 to 20 states after 2 students picked their states ( S2,10 to S2,20 )
To stay at 10 states after student 3 picks we multiply the probability of having 10 before by the probability of picking the same 10 states.
S2,10 * COMBIN(10,10)*COMBIN(40,0) / COMBIN(50,10) = S3,10
There are 2 ways to have 11 states after student 3 picks.
Have 10 before and 1 new
S2,10 * COMBIN(10,9)*COMBIN(40,1) / COMBIN(50,10)
and 11 before and 0 new.
S2,11 * COMBIN(11,0)*COMBIN(39,10) / COMBIN(50,10)
So S3,11 = S2,10 * COMBIN(10,9)*COMBIN(40,1) / COMBIN(50,10) + S2,11 * COMBIN(11,0)*COMBIN(39,10) / COMBIN(50,10)
There are 3 ways to have 12 states after student 3 picks.
Have 10 before and 2 new
S2,10 * COMBIN(10,8)*COMBIN(40,2) / COMBIN(50,10)
and 11 before and 1 new.
S2,11 * COMBIN(11,9)*COMBIN(39,1) / COMBIN(50,10)
and 12 before and 0 new.
S2,12 * COMBIN(12,10)*COMBIN(38,0) / COMBIN(50,10)
S3,13 = the sum of the above 3 numbers.
You repeat this process to find S3,14 to S3,20
I repeated this until I got to S21,50
I did a bunch of copying and pasting in Excel. I put it in google docs.
Any questions, just ask
I'm not very good at explaining things, but here it goes:
Student 1 picks 10 states.
We then determine the percent of time student 2 will pick between 0 and 10 new states.
0 new states is COMBIN(10,10)*COMBIN(40,0) / COMBIN(50,10)
1 new state is COMBIN(10,9)*COMBIN(40,1) / COMBIN(50,10)
2 new states is COMBIN(10,8)*COMBIN(40,2) / COMBIN(50,10)
...
9 new states is COMBIN(10,1)*COMBIN(40,9) / COMBIN(50,10)
10 new states is COMBIN(10,0)*COMBIN(40,10) / COMBIN(50,10)
We should now have a list of probabilities for 10 to 20 states after 2 students picked their states ( S2,10 to S2,20 )
To stay at 10 states after student 3 picks we multiply the probability of having 10 before by the probability of picking the same 10 states.
S2,10 * COMBIN(10,10)*COMBIN(40,0) / COMBIN(50,10) = S3,10
There are 2 ways to have 11 states after student 3 picks.
Have 10 before and 1 new
S2,10 * COMBIN(10,9)*COMBIN(40,1) / COMBIN(50,10)
and 11 before and 0 new.
S2,11 * COMBIN(11,0)*COMBIN(39,10) / COMBIN(50,10)
So S3,11 = S2,10 * COMBIN(10,9)*COMBIN(40,1) / COMBIN(50,10) + S2,11 * COMBIN(11,0)*COMBIN(39,10) / COMBIN(50,10)
There are 3 ways to have 12 states after student 3 picks.
Have 10 before and 2 new
S2,10 * COMBIN(10,8)*COMBIN(40,2) / COMBIN(50,10)
and 11 before and 1 new.
S2,11 * COMBIN(11,9)*COMBIN(39,1) / COMBIN(50,10)
and 12 before and 0 new.
S2,12 * COMBIN(12,10)*COMBIN(38,0) / COMBIN(50,10)
S3,13 = the sum of the above 3 numbers.
You repeat this process to find S3,14 to S3,20
I repeated this until I got to S21,50
I did a bunch of copying and pasting in Excel. I put it in google docs.
Any questions, just ask
“Man Babes” #AxelFabulous
March 24th, 2012 at 1:35:08 PM
permalink
Yeah, my technique was simpler and in error. It was off by 0.7042% for p. Just glad I didn't spend all day working on that problem.
March 24th, 2012 at 1:36:38 PM
permalink
Quote: DocJust glad I didn't spend all day working on that problem.
Hey hey hey now...
:)
March 25th, 2012 at 8:03:15 AM
permalink
For your reading pleasure: On the Number of i.i.d. Samples Required to Observe all of the Balls in an Urn. I'll let the more advanced mathematicians translate that into an equation.
“Man Babes” #AxelFabulous
March 30th, 2012 at 7:40:47 AM
permalink
Quote: TIMSPEEDHaha, this brings back memories...the hardest class assigment I EVER had...
To pass 7th Grade History, we had to draw a map with ALL 50 states AND their capitals!
Well, sorta..
We had a map of the USA, AND the states were drawn out...but once you get up to the NewEngland area, it gets real fucking tough.
Stipulation..you COULD NOT MISS ONE..however, you could retake it as many times as needed (only once a week though, so I guess you technically got like 20 chances)
To tell you the truth, I cheated...I got SO close on one try (like I missed 4 and it was only their capitals that I missed up in the Tiny State area). that I just wrote down on my hand the capitals of the NE states (not the whole words of course)
TO THIS DAY, hardest thing I've ever had to do (and resulted that I HAD to cheat)
I don't think I would've had any problem with this. We had a COUNTRY and capitals test in Social Studies. There were 120 countries or so with a map of the world, we had to identify each country and then it's capital. I got like a 98% and was in the top 3 out of about 130 kids. Within a few months I probably couldn't locate half of those countries, and probably couldn't name 30% of the capitals.
March 31st, 2012 at 12:57:33 PM
permalink
Off the top of my head, without looking on a map, it's Boston, MA; Providence, RI; Hartford, CT; Montpelier, VT; Concord, NT; Albany, NY; and Bangor, ME (or is it Portland?). Maine borders NH and MA; VT is between NY and NH. On the south of VT and NH is MA, CT is South of MA, and RI is nestled in the south east corner of CT with MA on the north.
Americans, in general are terrible for their geography.
Americans, in general are terrible for their geography.
-----
You want the truth! You can't handle the truth!
March 31st, 2012 at 1:14:01 PM
permalink
Quote: boymimboOff the top of my head, without looking on a map, it's Boston, MA; Providence, RI; Hartford, CT; Montpelier, VT; Concord, NT; Albany, NY; and Bangor, ME (or is it Portland?). Maine borders NH and MA; VT is between NY and NH. On the south of VT and NH is MA, CT is South of MA, and RI is nestled in the south east corner of CT with MA on the north.
Americans, in general are terrible for their geography.
If only you were American instead of Canadian, you would have proved your point. Maine does not abut Massachusetts, and its capital is neither of the cities that you mentioned. Of course, few Americans can name the Canadian provinces.
March 31st, 2012 at 1:22:40 PM
permalink
I was pretty close though! Augusta is the capital of Maine, and it only borders NH.
-----
You want the truth! You can't handle the truth!
March 31st, 2012 at 2:19:26 PM
permalink
Quote: DocIf only you were American instead of Canadian, you would have proved your point. Maine does not abut Massachusetts, and its capital is neither of the cities that you mentioned. Of course, few Americans can name the Canadian provinces.
Albert, British Columbia, Saskatchewan, Ontario, Quebec, Newfoundland, Prince Edward Island, Nova Scotia, & one in the middle. The problem is that I don't know how many there are, so I am not sure how many I am missing.
Northwest Territories, Yukon and Nunavit are territories.
Maine used to part of Mass. , but New Hampshire split the two territories.
March 31st, 2012 at 3:09:00 PM
permalink
I'll credit "Albert" as just a typo. Manitoba is the missing one in the middle, but there is also New Brunswick. I wasn't sure myself whether Nunavit was considered a province or a territory. And I'm not sure whether the name is Newfoundland or Newfoundland and Labrador.
You came a lot closer than I would expect most Americans to do.
You came a lot closer than I would expect most Americans to do.
March 31st, 2012 at 3:45:54 PM
permalink
Quote: DocI'll credit "Albert" as just a typo. Manitoba is the missing one in the middle, but there is also New Brunswick. I wasn't sure myself whether Nunavit was considered a province or a territory. And I'm not sure whether the name is Newfoundland or Newfoundland and Labrador.
You came a lot closer than I would expect most Americans to do.
The sad thing was that I didn't know many there are. That would have at least cued me to rack my brain a little more. And yes, it is Newfoundland and Labrador.
I know Canadians complain about how many Americans don't know the capital of Canada.
April 1st, 2012 at 11:31:07 AM
permalink
It's not really fair to compare American's knowledge of Canadian geography to Canada's knowledge of American geography. Like 90% of us live within a one hour's drive of the border, so we should know. As well, we consider American politics important. I'm just as likely to know the Premier's name of Alberta (I don't know) as much as the Governor of New Mexico (I also don't know).
The US States are, in order: Alabama, Alaska, Arizona, Arkansas, California, Colorado, Connecticut, Delaware, Florida, Georgia, Hawaii, Idaho, Illinois, Indiana, Iowa, Kansas, Kentucky, Louisiana, Maine, Maryland, Massechusetts, Michigan, Minnesota, Mississippi, Missouri, Montana, Nebraska, Nevada, New Jersey, New Mexico, New York, North Carolina, North Dakota, Ohio, Oklahoma, Oregon, Pennsylvania, Rhode Island, South Carolina, South Dakota, Tennessee, Texas, Utah, Vermont, Virginia, Washingon, West Virginia, Wisconsin, Wyoming.
I'm missing 1... New Hampshire. But not bad.
The US States are, in order: Alabama, Alaska, Arizona, Arkansas, California, Colorado, Connecticut, Delaware, Florida, Georgia, Hawaii, Idaho, Illinois, Indiana, Iowa, Kansas, Kentucky, Louisiana, Maine, Maryland, Massechusetts, Michigan, Minnesota, Mississippi, Missouri, Montana, Nebraska, Nevada, New Jersey, New Mexico, New York, North Carolina, North Dakota, Ohio, Oklahoma, Oregon, Pennsylvania, Rhode Island, South Carolina, South Dakota, Tennessee, Texas, Utah, Vermont, Virginia, Washingon, West Virginia, Wisconsin, Wyoming.
I'm missing 1... New Hampshire. But not bad.
-----
You want the truth! You can't handle the truth!
April 1st, 2012 at 12:05:00 PM
permalink
I doubt that I could name the 50 states in alphabetical order. When I try to name them, I always start with an extreme geographical point, such as Maine, and name them progressively north and south, working my way to the opposite coast. Sometimes I skip one, as boymimbo did, because they are not all nicely aligned in columns, but I can generally review my list and come up with the missing one pretty quickly.
I also am likely to make an error in naming the capitals, if I do it quickly. I mentioned earlier about the issue of naming largest cities rather than the correct capital, but if I review a list, I can generally recognize such an error.
On the other hand, I admitted some uncertainty in the name of one Canadian province and uncertainty as to one was a province or a territory. I have no confidence at all that I could name the capitals of the provinces; in fact, I am quite confident that I could not do that accurately on first or second try.
I suspect that most Americans would do poorly on a test of naming states and capitals and very poorly naming Canadian provinces, territories and capitals. And even naming the capital of Canada, as pacomartin pointed out. What was that movie in which John Candy led a band of Americans to invade the Canadian capital in Toronto? I think that was mentioned on this forum once before, and I am again forgetting the film title.
I also am likely to make an error in naming the capitals, if I do it quickly. I mentioned earlier about the issue of naming largest cities rather than the correct capital, but if I review a list, I can generally recognize such an error.
On the other hand, I admitted some uncertainty in the name of one Canadian province and uncertainty as to one was a province or a territory. I have no confidence at all that I could name the capitals of the provinces; in fact, I am quite confident that I could not do that accurately on first or second try.
I suspect that most Americans would do poorly on a test of naming states and capitals and very poorly naming Canadian provinces, territories and capitals. And even naming the capital of Canada, as pacomartin pointed out. What was that movie in which John Candy led a band of Americans to invade the Canadian capital in Toronto? I think that was mentioned on this forum once before, and I am again forgetting the film title.
April 1st, 2012 at 4:08:40 PM
permalink
i would be willing to bet that very few people can name the 54 countries in africa...
i would be impressed with 40 or more...
i would be impressed with 40 or more...
In a bet, there is a fool and a thief.
- Proverb.
April 1st, 2012 at 4:42:33 PM
permalink
When I was in 6th grade, we learned the countries of the world and their capitals, one continent at a time. After covering the world, I think that I knew all of them.
Unfortunately, even if I could remember them these 55 years later (I certainly cannot), that wouldn't do me much good in the challenge regarding Africa. It seems as if a substantial portion of the countries on that continent are different from what they were when I was in the 6th grade. There have been quite a few changes in eastern Europe, too, and a few in South America and Asia. Even one that I can think of in North America. I haven't even tried to keep up with all of it.
Unfortunately, even if I could remember them these 55 years later (I certainly cannot), that wouldn't do me much good in the challenge regarding Africa. It seems as if a substantial portion of the countries on that continent are different from what they were when I was in the 6th grade. There have been quite a few changes in eastern Europe, too, and a few in South America and Asia. Even one that I can think of in North America. I haven't even tried to keep up with all of it.
April 1st, 2012 at 7:42:47 PM
permalink
Quote: WongBoi would be willing to bet that very few people can name the 54 countries in africa...
i would be impressed with 40 or more...
Egypt
Libya
Tunisia
Morocco
Ghana
Liberia
Niger
Nigeria
Burkina Faso
Benin
Gambia
Chad
Namibia
South Africa
Rwanda
Mauritania
Zimbabwe
Seychelles
Botswana
Central African Republic
Sudan
Kenya
Uganda
Zaire
Mozambique
Ethiopia
Sierra Leone
Swaziland
---
Ow! Ow! My head hurts. Your right, I can't get over halfway.
How about the 27 countries in the EU? I think Mike S. got 26 of them.
April 1st, 2012 at 7:55:56 PM
permalink
I would have missed a bunch of those, but I would have offered several other names, without being sure whether there are still countries by those names:
Gold Coast
Ivory Cost
Algeria
Angola
Congo
Rhodesia
Eritrea
Somalia
running on empty myself
Gold Coast
Ivory Cost
Algeria
Angola
Congo
Rhodesia
Eritrea
Somalia
running on empty myself
