This article is from the Puzzles FAQ, by Chris Cole email@example.com and Matthew Daly firstname.lastname@example.org with numerous contributions by others.
At a movie theater, the manager announces that they will give a free ticket
to the first person in line whose birthday is the same as someone who has
already bought a ticket. You have the option of getting in line at any
time. Assuming that you don't know anyone else's birthday, that birthdays
are distributed randomly throughtout the year, etc., what position in line
gives you the greatest chance of being the first duplicate birthday?
Suppose you are the Kth person in line. Then you win if and only if the
K-1 people ahead all have distinct birtdays AND your birthday matches
one of theirs. Let
A = event that your birthday matches one of the K-1 people ahead
B = event that those K-1 people all have different birthdays
Prob(you win) = Prob(B) * Prob(A | B)
(Prob(A | B) is the conditional probability of A given that B occurred.)
Now let P(K) be the probability that the K-th person in line wins,
Q(K) the probability that the first K people all have distinct
birthdays (which occurs exactly when none of them wins). Then
P(1) + P(2) + ... + P(K-1) + P(K) = 1 - Q(K) P(1) + P(2) + ... + P(K-1) = 1 - Q(K-1) P(K) = Q(K-1) - Q(K) <--- this is what we want to maximize.
Q(I-1) - Q(I) = Q(I)*(I-1)/(D-I+1) Q(I) - Q(I+1) = Q(I)*I/D P(K) - P(K-1) = P(I+1) - P(I) = (Q(I) - Q(I+1)) - (Q(K-2) - Q(K-1)) = Q(I)*(I/D - (I-1)/(D-I+1))
x = (1 +/- sqrt(1 - 4*(-D)))/2 ... take the positive square root = 0.5 + sqrt(D + 0.25)