Last time, on my birthday, I asked a question, "if I ask people their birthdays at work, one at a time, then on average how many do I have to ask until I get someone having the same birthday as me?" The answer is 253.
A
similar but different question on birthday is "How many people do I
have to ask so that at least two people share a birthday, not
necessarily mine?"
The answer is 23, remarkably smaller. We can also re-ask this question in probabilistic way. This is the same as asking, "How many people should I ask so that the probability that at least two share a birthday is greater than 0.5?" Or let me even rephrase it again here too. "How many people should I ask so that the probability that no one shares a birthday is less than 0.5?"
When
the first person enters, the probability that their birthday is
different from that of anyone else present is 1, because nobody else is
present. That's 365/365.
When
the second person enters, their birthday has to be different, so there
are now only 364 choices out of 365. So that's 364/365.
So
the third person enters, the fourth person enters,...and the k-th
person enters. By the k-th person, we want to have the probability that
no one shares a birthday to be less than 0.5.
365/365 x 364/365 x 363/365 x ... x (365 - k + 1)/365 < 1/2
So we work out the question and get the smallest k to be 23.
QED.
No comments:
Post a Comment