Author |
Topic: Birthday gathering (Read 2072 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Birthday gathering
« on: Oct 19th, 2002, 6:36pm » |
 Quote  Modify
|
What is the minimum number of people that must be gathered in a room for there to be at least an even chance that all 365 birthdays are represented? Assume birthdays are randomly distributed throughout a 365 day year; i.e., ignore leap years.
Nick
|
| « Last Edit: Oct 23rd, 2003, 8:12pm by Icarus » |
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
Jeremy
Newbie
Gender:
Posts: 25
|
|
Re: NEW PUZZLE: Birthday gathering
« Reply #1 on: Oct 21st, 2002, 6:47am » |
Quote Modify
|
I'm pretty sure this is the answer:
The chance of a single person having any birthday on one of the 365 days: 1/1
the chance person number 2 has a birthday on the first person's birthday : 1/365
chance person number 3 has a birthday on one of the other 2 birthdays : 3/365
etc.
1/365+2/365+3/365+4/365... +x/365 >= .5
or
(1+2+3+4... +x)/365 >= .5
or
x(x+1)/730 >= .5
what 2 consecutive numbers will be closest to 365?
19*20... so 20 people in a room will work.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PUZZLE: Birthday gathering
« Reply #2 on: Oct 21st, 2002, 11:18am » |
Quote Modify
|
The answer can't be less than 365. Are you answering the more usual question, which is "how many people must be in a room before there is better than an even chance that at least two have the same birthday?" The answer to that is close to what you give.
Probability that no two among n people share a birthday =
(probability that first person doesn't share a birthday with 0 others before) *
(probability that second person doesn't share a birthday with 1 others before) *
... *
(probability that nth person doesn't share a birthday with n-1 others before) =
365/365 * 364/365 * ... * (365-n+1)/365
The question is when does this become < 0.5, and it does so first at n=23.
I have an answer to the original question but I haven't thought it through so much yet... 2366.
|
|
IP Logged |
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: NEW PUZZLE: Birthday gathering
« Reply #3 on: Oct 21st, 2002, 3:54pm » |
Quote Modify
|
I sketched out the probability distribution for up to 4 people by hand, and man is it ugly. So, onward to the trusty VB compiler. Using the following program, I get this answer: 2287. There may some rounding error involved, especially because we're dealing with figures like (365!)/(365^365). I'd be very interested if there's an elegant way to solve this by hand.
Dim g(365, 3000) As Double
g(1, 1) = 1
For i As Integer = 2 To 3000
g(1, i) = g(1, i - 1) / 365.0
For j As Integer = 2 To 365
g(j, i) = (g(j, i - 1) * j / 365.0) + (g(j - 1, i - 1) * (366 - j) / 365.0)
Next
If g(365, i) >= 0.5 Then Stop
Next
Stop
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NEW PUZZLE: Birthday gathering
« Reply #4 on: Oct 21st, 2002, 5:05pm » |
Quote Modify
|
Regarding Jeremy's response, there may have been some confusion since I recently posted the Birthday Paradox in the medium section, as opposed to Birthday Gathering. Regarding an elegant way of solving this problem, we can do a standard balls and bins analysis, with 365 bins and N balls. Determine the value of N such that the probability all bins are filled is 50%.
First let's define our event space. Let E be the event that all 365 bins are filled. E can be written as the intersection of events Ei for i Î {1, 2, ... , 365}, where Ei is the event that the ith bin contains at least one ball. Now we want an equation for Pr(E) in terms of N. Then we can set Pr(E) = 0.5 and solve for N.
If all the events Ei are independent, then
Pr(E) = Pr(E1) · Pr(E2) · ... · Pr(E365)
since the probability of the intersection of independent events is the product of the probabilities of each of the events. Then this would be a simple calculation. Since the balls are assumed to be independent and identically distributed among the bins,
Pr(E) = Pr(E1)365
= 1 - Pr(E1c)
= 1 - (364/365)N.
Reasoning: The probability that at least one ball falls into bin 1 is equivalent to 1 minus the probability of the complementary event, which is that no balls fall into bin 1. If no balls fall into bin 1, all the balls must fall in a different bin. The probability that one ball goes into a different bin is 364/365, since there are 364 other bins.)
But unfortunately the events aren't independent, and if you solve the above equation for N, you get N = 252.652 which doesn't make sense since when N < 365, Pr(E) = 0. To prove they are not independent, consider what happens if we know that E1 through E364 are all false, and N is greater than 0. Then we can say that E365 is true with probability 1, since the balls have to go somewhere. Whenever we have to compute the probability of interesection or union of many events that depend on each other in some nasty way, we can either: 1) look at a complementary event that may be easier to analyze, and/or 2) use the generalized inclusion-exclusion principle. In the following analysis I'll use a little bit of both. Here's the part about complementary events:
Pr(E) = Pr( Ç Ei) = 1 - Pr(E1c È E2c È ... È E365c)
Reasoning: The probability that all bins are filled is equal to 1 minus the probability of the complementary event, which is that at least one bin is not filled. So bin 1 might not be filled, OR bin 2 might not be filled, OR maybe they are both not filled, etc. The clause of unions shown above expresses these thoughts. Also note that it is easier to think about the probability of Eic instead of Ei. The probability that no balls fall into bin i is simply 1 - (364/365)N. So we can use some parts of the naive analysis that incorrectly assumed independence of events.
All that's left is to apply the inclusion-exclusion formula to that clause of unions, set Pr(E) to 0.5, and solve for N. The cafeteria is closing soon though, so I'll let someone else do that  You should see a summation symbol and an alternating sign term.
P.S. So how did I get those math operators? Check out the "suggestions, help, and faq" forum.
|
| « Last Edit: Oct 21st, 2002, 11:31pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Uwe Dippel
Guest
|
|
Re: NEW PUZZLE: Birthday gathering
« Reply #5 on: Jan 10th, 2003, 8:51am » |
Quote Modify
 Remove
|
As far as I know, this is wrong.
But: I'm sooo curious, why.
It sounds pretty much logically correct when I read the chain of arguments. And the result is pretty close to what it is supposed to be.
Can someone point out the mistake ??
|
|
IP Logged |
|
|
|
udippel
Newbie
Posts: 30
|
|
Re: NEW PUZZLE: Birthday gathering
« Reply #6 on: Jan 10th, 2003, 9:01am » |
Quote Modify
|
Ooops, this was supposed to be further up at Jeremy's post and now I don't have the right to remove or change it. Something to be worked on here ... !
Jeremy convinced me and I want to know what is wrong in his chain !
|
|
IP Logged |
|
|
|
redPEPPER
Full Member
Posts: 160
|
|
Re: NEW PUZZLE: Birthday gathering
« Reply #7 on: Jan 10th, 2003, 1:52pm » |
Quote Modify
|
Okay, let's see what's wrong with Jeremy's logic.
on Oct 21st, 2002, 6:47am, Jeremy wrote:| The chance of a single person having any birthday on one of the 365 days: 1/1 |
|
Correct. You can note that this 1/1 will not be used in the equation below. A first clue that there might be a problem.
Quote:| the chance person number 2 has a birthday on the first person's birthday : 1/365 |
|
Correct.
Quote:chance person number 3 has a birthday on one of the other 2 birthdays : 3/365
etc. |
|
Two mistakes here.
First, Jeremy wrote 3/365 instead of 2/365 which is what I assume he means, as seen in the equations below.
Second, the probability is 2/365 only if number 2 has a different birthday than number 1. That is, if the previous statement (1/365) doesn't happen.
Quote:| 1/365+2/365+3/365+4/365... +x/365 >= .5 |
|
Well, this is where he loses us. I don't know exactly what this equation is supposed to represent.
1/365 is the probability that the first two birthdays are concurrent. What is 1/365 + 2/365? It looks like it could be the probability that the first two are concurrent, or the third with one of the first two in case the first two are different. But then it should be 1/365 + (1-1/365) * 2/365.
It gets uglier when you add a fourth person, as the probability to have a common birthday with the three previous ones is 3/365 only if the previous ones don't have a day in common already. The equation would be something like 1/365 + (1-1/365) * 2/365 + (1-1/365-((1-1/365) * 2/365)) * 3/365
And that's only 4 people. Not only does this get ugly, but it calculates the probability that two people share a birthday, which is not the question. And can be much more easily calculated by combining the probabilities where people don't share a birthday instead of the probabilities they do, as S. Owen showed.
|
|
IP Logged |
|
|
|
kenny
Newbie
Posts: 12
|
|
Re: NEW PUZZLE: Birthday gathering
« Reply #8 on: Jan 14th, 2003, 7:55am » |
Quote Modify
|
Here's an approximation, using "the law of big numbers."
First, if you have N people, then the expected number who have birthdays on Jan 1 is "mu" = N/365. The probability that none of them has a birthday on Jan. 1 is e^(-mu). Thus, the probability that at least one has a birthday that day is 1 - e^(-mu). This comes from the Poisson distribution, which is an approximation, but it's a very good approximation.
I then assume assume that the probability that at least one person has a birthday on Jan. 2 is independent of the probability that at least one person has a birthday on Jan. 1. This assumption is patently false, but when the number of people becomes large, it becomes a good approximation.
We then see that the probability that all 365 possible dates are hit is
(1 - e^(-mu))^365. We want that to be greater or equal to 1/2. A bit of math (and more approximation) shows that mu >= ln(365 / ln(2)) which is 6.266. Thus, the number of people N = mu * 365 = 2287, which is the same number that Garzahd got!
This approach works because the number of dates is fairly large. If we tried the same for "one person born in each month", it wouldn't be very accurate. If we tried for "one person born in each hour of each day", it would be even more accurate.
-- Ken
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print