Here's why:
Suppose he was the Kth person in line. Then he wins if and only if the K-1 people ahead all have distinct birtdays AND his birthday matches one of theirs. Let
A = Fred's birthday matches one of the K-1 people ahead
B = those K-1 people all have different birthdays
Then
Prob(Fred wins) = 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.
Now if the first K-1 all have distinct birthdays, then assuming uniform distribution of birthdays among D days of the year, the K-th person has K-1 chances out of D to match, and D-K+1 chances not to match (which would produce K distinct birthdays). So
Q(K) = Q(K-1)*(D-K+1)/D = Q(K-1) - Q(K-1)*(K-1)/D
Q(K-1) - Q(K) = Q(K-1)*(K-1)/D = Q(K)*(K-1)/(D-K+1)
Now we want to maximize P(K), which means we need the greatest K such that P(K) - P(K-1) > 0. (Actually, as just given, this only guarantees a local maximum, but in fact if we investigate a bit farther we'll find that P(K) has only one maximum.) For convenience in calculation let's set K = I + 1. Then
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))
To find out where this is last positive (and next goes negative), solve
x/D - (x-1)/(D-x+1) = 0
Multiply by D*(D+1-x) both sides:
(D+1-x)*x - D*(x-1) = 0
Dx + x - x^2 - Dx + D = 0
x^2 - x - D = 0
x = (1 +/- sqrt(1 - 4*(-D)))/2 ... take the positive square root
= 0.5 + sqrt(D + 0.25)
Setting D=365 (finally deciding how many days in a year!),
desired I = x = 0.5 + sqrt(365.25) = 19.612 (approx).
The last integer I for which the new probability is greater then the old is therefore I=19, and so K = I+1 = 20.
...viola!
EPISODE XVILand of the giants, it is often called,
Where warriors and wizards play with wolves;
Its suns and stars get hot and cold,
Whether one is at home or on the road.
Fourteen tribes live in the west, we are told,
One less than those in the eastern world;
The weakest thirteen will give up and fold.
While the strongest continue their quest for gold.
The kings are powerful and the magic is bold,
Others can fly and are a site to behold;
But when the season is past and the story is told,
New stars are born and old tribes evolve.
What is the Land of the Giants?
Have fun witht his riddle. Good Luck!!!
