I am such a nerd

I saw a reference to "the birthday problem" today (if you have n people in a room, what are the odds that at least two of them have the same birthday?), and the Wikipedia page didn't make much sense to me, so I worked at it until I solved it on my own. My answer is formulated differently than Wiki's, but setting it equal to .5, I get the right answer -- if you have 23 or more people in the same room, odds are at least 50-50 that two will have the same birthday. If you have 22 or fewer, the odds are that they all have different birthdays.

Since I wasted a lot of time, I figured I'd share my reasoning. Here's my solution:

1 - [( 364 / 365 ) ^ (( n ( n - 1 )) / 2 )]

Here's my method, as well as I can explain it. Whenever you're trying to figure out the odds of a group of people matching once or more, it's easier to find the odds of no one matching and subtract it from 1. With any two people, the odds of them not matching is 364/365.

So (1 - 364/365) is the answer when there are only two people in the room. When there are three people in the room, there are three possible matches -- AB, AC and BC -- so then the answer is 1- [(364 / 365) ^ 3]. Four people, six matches (AB AC AD BC BD CD), 1 - [(364 / 365) ^ 6]. For each new match, you have to multiply by 364/365 again, because each match reduces the odds that no one's shared a birthday yet.

When counting up the total matches, think of it as matching the first person in the room with everyone else, then matching the second person with everyone except the first person, with whom he's already been matched, and so on. Look back at the combinations for four people -- A is matched to B, C and D; then B still has to match with C and D; then C has to be matched with D. Our answer will be 1 - [(364/365) ^ total matches]

The biggest problem is converting the exponent into a formula. I looked at it like this: Using the matching idea, you multiply by 364/365 (n - 1) times (the first person in a group of four needs to be matched with three people), and then (n - 2) times, and so on, until (n - whatever) reaches 1. This looks like (364 / 365) ^ (n - 1) * (364 / 365) ^ (n - 2), etc.

When you're multiplying the same number with different exponents, you add the exponents. For example, (2 ^ 3) * (2 ^ 4) = 2 ^ 7. So to find the exponent, we have to summarize (n - 1) + (n - 2) + (n - 3) ...

The first question is how many "n"s we'll have once we've added all the terms. When n = 2, there's only 1, in (n - 1). (In this case, n - 2 = 0, so there's no point in adding 0.) And when n = 3, there are two "n"s, (n - 1) + (n - 2). In the formula, there is always one fewer "n"s than n's value. From this we get n(n - 1).

What I found most difficult was figuring out how to make the subtracted numbers add up. When n = 2, we subtract 1. When n = 3, we subtract 3 -- (n - 1) + (n - 2). Here's the table:

n   Subtracted number
2   1
3   3
4   6
5   10
6   15

Basically, you start out subtracting 1, and then you always subtract 1 more than you did last time. Formula-wise, and annoyingly enough, this is a repeat of the previous problem, (n - 1) + (n - 2), etc. I didn't really know where to go from here, so I decided to take a closer look at the way I starting solving the problem last time -- with the "n"s. Recall that answer was n(n - 1). I figured that this formula must be adjusted in some way to calculate the subtracted number based on n, so I wrote it out:

n   n(n - 1)
2   2
3   6
4   12
5   20
6   30

Not sure how you'd discover this algebraically, but visually it's easy to see that n(n - 1) / 2 equals the subtracted number in the exponent. And of course, this is subtracted from n(n - 1), and any number minus half of itself equals half of itself. So the exponent is n(n - 1) / 2.

To set the formula equal to .5, multiply it out and use logarithms (just type, for example, "log .5" in a Google search) and the quadratic formula .