Puzzle – Birthday pairings

April 30, 2010 – 2:20 pm

Here’s two classic birthday puzzles:

How many people do you need in a room to have a better than 50% chance of finding at least one shared birthday among them?

Like a lot of these problems, it’s easier to first find the chances of the proposition not happening – that is of not finding a shared birthday.

For this problem, I like to imagine that I have a bunch of 365-card decks. I deal one card from each deck. What are the chances that I haven’t dealt the same card after after dealing from r decks? You can see that this is a good analogy for our problem. Looking back at the previous post on dealing a perfect hand may be a good primer for what follows.

The answer to our card analogy is to take the number of ways I can deal the cards (one from each deck) and get no duplicates divided by the total number of ways I can deal the cards. From the first deck, I have 365 ways to deal one card. From the second deck, I have 364 ways to deal one card and not have duplicates. From the third deck, there are 363 ways, and so on until I get to 365-r+1 ways. So the number of ways I can deal cards without duplicates is:

= 365 * 364 * … * (365-r+1)
= 365! / (365-r)!

Now lets work out how many ways there are to deal the cards without restrictions. The answer is simply:

= 365 ^ r

So now, the probability of not dealing any duplicate cards (and also the chances of not finding anyone with a shared birthday) is:

= (365! / (365-r)!) / 365 ^ r

I was a little stumped at how to solve this, except through some trial and error. Even then, 365! seems to make calculators, or even trusty google, blow up. We can use Sterling’s approximation to find that:

ln(365!) = 1792.33142
ln((365-22)!) = 1663.17935
ln((365-23)!) = 1657.34162

So for r=22, our probability of no shared birthdays:
= e ^ (1 792.33142 – 1 663.17935) / 365 ^ 22 = 0.524310203

For r=23:
= e ^ (1792.33142 – 1657.34162) / 365 ^ 23 = 0.492707724

Now remember that this is for finding no shared birthdays. To have at least 1 shared birthday, we need to subract from 1.

So for r=22, the chances of finding at least 1 shared birthday are:
= 1 – 0.524310203 = 0.475689797

For r=23, the chances are:
= 1 – 0.492707724 = 0.507292276

So you can see that it takes at least 23 people in a room to have a greater than 50/50 chance of finding a shared birthday.

By the way, to get the Stirling approximation of ln(365!) I typed the following into google:

365 * ln(365) – (365) + ln(365)/2 + ln (2*pi) / 2)

How many people do you need in a room with you to have a better than 50% chance of finding someone who shares your birthday?

This one’s a little simpler than the first. Again, it’s easier to first find the probability of no one having your birthday. Let’s imagine people walking in to a room where you are. The first person has a 364/365 chance of not having your birthday. And it’s the same for all subsequent people who walk into the room. So the chances of no one sharing your birthday after r people have walked in are:

= (364/365)^r

So the chance that at least one person shares your birthday is:

= 1 – (364/365) ^ r

Let’s find r when the equation is 1/2, representing the at least 50% chance we were looking for:

1/2 = 1 – (364/365) ^ r
(364/365) ^ r = 1/2
r * log (364/365) = log (1/2)
r = log (1/2) / log (364/365)
r = 252.651989

So you need to have at least 253 people with you in a room to have a better than 50/50 chance of finding someone sharing your birthday. It’s quite amazing how different this answer is to the answer for the first part.

  1. 2 Responses to “Puzzle – Birthday pairings”

  2. nice blog and amazing information and attractive..
    i am feeling well to be here..
    keep sharing good things with friends..
    Thanks for sharing..

    By kids birthday party games on Jun 24, 2011

  1. 1 Trackback(s)

  2. Aug 26, 2010: Rebrained! » Blog Archive » Birthday Simulations – Python

Post a Comment