Author |
Topic: Birthday Paradox [variant] (Read 1105 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Birthday Paradox [variant]
« on: Apr 21st, 2003, 10:55am » |
 Quote  Modify
|
The so-called Birthday Paradox puzzle asks how many people need there be in a room so that the probability of two (or more) people sharing the same birthday is at least 1/2. Most people - including myself - are surprised to learn that the answer is 23, assuming a uniform distribution of birthdays, 365 days in a year, etc. [It is much less surprising when one considers the number of comparisons of birthdays. 23C2 = 253. Note that 253/365 ~ loge2].
VARIANT: Let there be 2 classrooms, each containing n people.
What is the minimum value of n such that the probability of at least one person in EITHER classroom sharing the same birthday with at least one person in the OTHER classroom is more than 1/2?
[I have put this in Medium, happy in the knowledge that I have never seen anybody complain,
"Hey, dude. This belongs in Hard!"] 
|
| « Last Edit: Apr 24th, 2003, 3:52pm by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
redPEPPER
Full Member
Posts: 160
|
|
Re: Birthday Paradox (variant)
« Reply #1 on: Apr 23rd, 2003, 3:31pm » |
Quote Modify
|
Hey dude, this belongs in Easy!
Either that, or I'm oversimplifying.
The probability P1 that a person "a" in class A doesn't share a birthday with a person "b" in class B is obviously 364/365. b just needs to be born on any of the 364 days that aren't a's birthday.
The probability P2(n) that a person "a" in class A doesn't share a birthday with n persons b1, b2,... bn in class B is (P1)n. Each person of class B needs to be born on another day than a's birthday.
The probability P3(n) that n persons a1, a2,... an in class A don't share a birthday with n persons b1, b2,... bn in class B is (P2(n))n. Each person of class A needs to comply to P2(n).
so P3(n) = ((364/365)n)n
The probability P4(n) that a person in class A shares a birthday with a person in class B is 1 - P3. We're looking for a n such that P4(n) > 0.5, or P3(n) < 0.5.
I have n = 16 as a very close answer: P4(16) = 50.457%)
I expected this to be simpler than the original riddle but I didn't really expect the answer to be lower.
But I could be wrong.
|
| « Last Edit: Apr 23rd, 2003, 3:40pm by redPEPPER » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Birthday Paradox (variant)
« Reply #2 on: Apr 24th, 2003, 9:09am » |
Quote Modify
|
Quote:
Assume n = 366. Obviously, they can't all have different birthdays.
Yet your formula produces a non-zero probability.
|
| « Last Edit: Apr 24th, 2003, 5:24pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
visitor
Guest
|
|
Re: Birthday Paradox (variant)
« Reply #3 on: Apr 24th, 2003, 12:41pm » |
Quote Modify
 Remove
|
Everyone in the first classroom certainly could have a different birthday from everyone in the second classroom no matter how large the classes are, because as your question is stated only a match from one room to the other counts, not matched birthdays within a room. So you could have a thousand in one room all born in the summer and a thousand in the other room all born in the winter (not likely if the rooms are random, but possible).
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Birthday Paradox [variant]
« Reply #4 on: Apr 24th, 2003, 6:39pm » |
Quote Modify
|
Yeah, I got my wires crossed there. I was disagreeing with the following:
Quote:
The probability P3(n) that n persons a1, a2,... an in class A don't share a birthday with n persons b1, b2,... bn in class B is (P2(n))n.
|
|
I think the above claims that P3(n) = [P2(n)]^n = [P1(n)]^n2
But
The probability that person 'a1" in class A does not share a birthday with any person "bn" in class B
and
the probability that person 'a2" in class A does not share a birthday with any person "bn" in class B
are not independent. So we can't just multiply them.
A simple example: let A(1), A(2), B(1), and B(2) each toss a fair coin (p = 1/2).
The probability that A(1) doesn't share the same result as either B(1) or B(2) is (1/2)2 = 1/4. Similarly for A(2).
But the probability that neither A(1) nor A(2) share the same result as either B(1) or B(2) is not (1/4)2 = 1/16,
but 1/8.
That is to say, there are only 2 outcomes out of 16 where this happens:
(A(1), A(2), B(1), B(2)) = (H,H,T,T) and (T,T,H,H).
|
| « Last Edit: Apr 29th, 2003, 8:11pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print