Brain Teasers
Birthday Line
Probability
Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.Probability
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 throughout the year, etc., what position in line gives you the greatest chance of being the first duplicate birthday?
Answer
You should try to be the 20th person in line.Suppose you are the Kth person in line. Then you win if and only if the K-1 people ahead all have distinct birthdays 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
Then
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.
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 than the old is therefore I=19, and so K = I+1 = 20.
Computing your chances of actually winning is slightly harder, unless you do it numerically by computer. The recursions you need have already been given.
Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
You must have worked REALLY, REALLY hard. Your excellent at this.
Mar 25, 2003
This is something!!!
OH MY!
uh....right.
This teaser should be called...
HEADACHE IN A BOX!!!!!!!!!!!!!!!!!!
HEADACHE IN A BOX!!!!!!!!!!!!!!!!!!
r u a genius?
i remember hearing about the birthday phenomenon but didnt quite understand it (i was sleeping in math class at the time) but it was quite interesting and i think this is a "practical" application of the numbers. nicely done and quite interesting.
That was my next guess...
I really loved it, I got the answer using difference equations.
Anyway, what if someone had a twin brother! wouldn't be better to stand second in line with the brother standing first;)
Anyway, what if someone had a twin brother! wouldn't be better to stand second in line with the brother standing first;)
wow, that would be annoying to type all of that, but the probibility works out all right, good teaser
Good problem
Classic probability question. Another way of saying it: With as few as 20 random people in a room, the chance of two having the same birthday > 50%.
That's not saying quite the same thing - that's just saying that the probability that either you or someone ahead of you will win is > 50%, but it doesn't necessarily mean you have the best chance.
Great teaser. i'm in AP Statistics in my high school, its my favorite class, this was an interesting problem
What if there is only two people at the movies? You can't figure probability with no numbers to start with!
uhhh.... what what what what??? Holy cow, I definitely didn't get this one!! !!!!!
One Word - WOW.
ver clever. and by the way...u must have a lot off free time on ur hands
Great problem!
I'm surprised given how long this problem has been posted that nobody bothered to give the probability of winning the free ticket, which is approximately 3.0628%. 19th place in line is almost as good at 3.0608%. This is a pain to calculate recursively by hand but very easy using a spreadsheet.
At 20 people the probability that two people have the same birthday is approximately 41.1% and the cumulative probability that someone in line before you wins the ticket is approximately 36.67%.
Also, the point at which the probability of two people having the same birthday exceeds 50% is with 23 people, not 20.
I'm surprised given how long this problem has been posted that nobody bothered to give the probability of winning the free ticket, which is approximately 3.0628%. 19th place in line is almost as good at 3.0608%. This is a pain to calculate recursively by hand but very easy using a spreadsheet.
At 20 people the probability that two people have the same birthday is approximately 41.1% and the cumulative probability that someone in line before you wins the ticket is approximately 36.67%.
Also, the point at which the probability of two people having the same birthday exceeds 50% is with 23 people, not 20.
May 12, 2009
Unfortunately, the author's long-winded answer is completely WRONG.
The correct answer is approx. 23.3 Rounded to the nearest whole number, the correct answer is 23.
As the previous posting correctly stated, the point at which the probability of two people having the same birthday exceeds 50% is with 23 people, not 20, and not 19.
The correct answer is approx. 23.3 Rounded to the nearest whole number, the correct answer is 23.
As the previous posting correctly stated, the point at which the probability of two people having the same birthday exceeds 50% is with 23 people, not 20, and not 19.
Janeys-
The answer given for the teaser is correct. You need to take into consideration the CUMULATIVE probability that someone in front of you wins the ticket before you get to the front.
The fact that at 23 people there is a better than 50% chance that two have the same birthday isn't really relevant to the problem. I just included that in my previous comment as a point of interest.
The answer given for the teaser is correct. You need to take into consideration the CUMULATIVE probability that someone in front of you wins the ticket before you get to the front.
The fact that at 23 people there is a better than 50% chance that two have the same birthday isn't really relevant to the problem. I just included that in my previous comment as a point of interest.
i would think the last person in line at any time where position P < or = 20.
I know this is old but it took me only a few minutes to solve and my solution is quite different, so I thought I might as well post it. In my opinion the answer given is convoluted.
Let p(k) be the probability that the first duplicate bday is at person k+1 in the line, i.e. the first k people have all different bdays and the bday of person k+1 matches one of the previous k bdays. No need for any conditional probabilities (why the Bayes equation in the answer?) since all events are independent and p(k) can be expressed directly:
p(k) = 365/365 * 364/365 * ... * (365 - k + 1)/365 * k/365
(easily verifiable thoruhg simulation for those who doubt it)
It says that the 1st person can have any bday (365/365), the 2nd person has a different bday than the 1st (364/365), and so on, and person k+1 has one of the first k bdays (k/365).
We just need to maximize p(k) as a function of k, that's it. It is easy to show it has only one maxima. The current form is ugly but we can do a trick, that is to find an equivalent, continuous function. We can write p(k) as:
p(k) = k/365^(k+1) * product_of k {from 365-k+1 to 365}
Taking the natural log:
ln(p(k)) = ln(k/365^(k+1)) + sum ln(k) {from 365-k+1 to 365}
The sum of discrete logs can be approximated by an integral of the continuous log function given that the terms in the sum are large (whoever knows of Sterling's factorial approx proof is already familiar) and so we can consider the continuous function q(x):
q(x) = ln(x/365^(x+1)) + integral ln(x) dx {from 365-x+1 to 365}
using parts:
q(x) = ln(x/365^(x+1)) + 365 ln 365 + (366-x) ln(366-x) - x + 1
Differentiating, and equating to zero, we get:
1/x = ln (365 / (366-x)) ... or ... exp(1/x) = 365/(366-x)
This has a unique solution since exp(1/x) is decreasing on [1,365] while 1/(366-x) is increasing on [1,365]. This is computed numerically to give x = 19.3676 so then our k+1 = 20, which is the solution.
Let p(k) be the probability that the first duplicate bday is at person k+1 in the line, i.e. the first k people have all different bdays and the bday of person k+1 matches one of the previous k bdays. No need for any conditional probabilities (why the Bayes equation in the answer?) since all events are independent and p(k) can be expressed directly:
p(k) = 365/365 * 364/365 * ... * (365 - k + 1)/365 * k/365
(easily verifiable thoruhg simulation for those who doubt it)
It says that the 1st person can have any bday (365/365), the 2nd person has a different bday than the 1st (364/365), and so on, and person k+1 has one of the first k bdays (k/365).
We just need to maximize p(k) as a function of k, that's it. It is easy to show it has only one maxima. The current form is ugly but we can do a trick, that is to find an equivalent, continuous function. We can write p(k) as:
p(k) = k/365^(k+1) * product_of k {from 365-k+1 to 365}
Taking the natural log:
ln(p(k)) = ln(k/365^(k+1)) + sum ln(k) {from 365-k+1 to 365}
The sum of discrete logs can be approximated by an integral of the continuous log function given that the terms in the sum are large (whoever knows of Sterling's factorial approx proof is already familiar) and so we can consider the continuous function q(x):
q(x) = ln(x/365^(x+1)) + integral ln(x) dx {from 365-x+1 to 365}
using parts:
q(x) = ln(x/365^(x+1)) + 365 ln 365 + (366-x) ln(366-x) - x + 1
Differentiating, and equating to zero, we get:
1/x = ln (365 / (366-x)) ... or ... exp(1/x) = 365/(366-x)
This has a unique solution since exp(1/x) is decreasing on [1,365] while 1/(366-x) is increasing on [1,365]. This is computed numerically to give x = 19.3676 so then our k+1 = 20, which is the solution.
The chance of person n in line winning is the chance that person 2 has a different birthday from all his predecessors times the chance that person 3 has a different birthday from all his predecessors times ... times the chance that person (n-1) has a different birthday from all his predecessors times the chance that person n has the SAME birthday as one of his predecessors.
The chance of person n in line winning is the chance of person (n-1) in line winning divided by the chance of person (n-1) having the SAME birthday as one of his predecessors times the chance of person (n-1) having a different birthday as all of his predecessors times the chance that person n has the SAME birthday as one of his predecessors.
In formula:
P(n)/P(n-1) = D/(n-2) (D-(n-2))/D (n-1)/D = (n-1)/(n-2) (D-n+2)/D
When this ratio becomes smaller than 1 we should not move farther along the line.
(n-1)/(n-2) (D-n+2)/D =
(n-1)/(n-2) (1 - (n-2)/D) =
(n-1)/(n-2) - (n-1)/D =
(n-2+1)/(n-2) - (n-1)/D =
1 + 1/(n-2) - (n-1)/D
Having isolated the 1, we need to determine when the remainder is zero.
1/(n-2) - (n-1)/D = 0
1/(n-2) = (n-1)/D
D = (n-2)(n-1)
Now since D is something like 365 or 365.25, we
try n=21:
(21-2)(21-1)=19*20=380, too high so try n=20:
18*19=360-18=342, so the zero we are looking for happens somewhere between 20 and 21, so from person 20 to person 21 is the first time that chance to win gets smaller instead of greater. So you should try to be person 20.
The chance of person n in line winning is the chance of person (n-1) in line winning divided by the chance of person (n-1) having the SAME birthday as one of his predecessors times the chance of person (n-1) having a different birthday as all of his predecessors times the chance that person n has the SAME birthday as one of his predecessors.
In formula:
P(n)/P(n-1) = D/(n-2) (D-(n-2))/D (n-1)/D = (n-1)/(n-2) (D-n+2)/D
When this ratio becomes smaller than 1 we should not move farther along the line.
(n-1)/(n-2) (D-n+2)/D =
(n-1)/(n-2) (1 - (n-2)/D) =
(n-1)/(n-2) - (n-1)/D =
(n-2+1)/(n-2) - (n-1)/D =
1 + 1/(n-2) - (n-1)/D
Having isolated the 1, we need to determine when the remainder is zero.
1/(n-2) - (n-1)/D = 0
1/(n-2) = (n-1)/D
D = (n-2)(n-1)
Now since D is something like 365 or 365.25, we
try n=21:
(21-2)(21-1)=19*20=380, too high so try n=20:
18*19=360-18=342, so the zero we are looking for happens somewhere between 20 and 21, so from person 20 to person 21 is the first time that chance to win gets smaller instead of greater. So you should try to be person 20.
I found the answer using 'bc'. For anyone interested, my little bc program is available at https://pastebin.com/kMgwFBdx
I want to be 4th. I will pay the guy in the 3rd position half the amount of a ticket to say that his birthday is October 24. Assuming that hasn't been claimed yet, no one is going to check his ID to be sure. When they get to me I will show my ID, win the prize.
To post a comment, please create an account and sign in.
Follow Braingle!