There is a long line of people waiting to see a new movie. They announce that the first person to have the same birthday as someone standing before them in the line gets to meet one of the actors in the movie.
What place in line would maximize your chances of winning? Assume birthdays are uniformly distributed through the year.
Solution
20th in line would maximize your chances
A bit of a brute force solution: inspect the probabilities starting from first place in line (either manually, using code, or using spreadsheet software). Let Pn be the probability that the nth in line wins:
- P1 = 0
- Because they have no one to share a birthday with
- P2 = 1 / 365 ≈ 0.00274
- P3 = (1 – P1 – P2) * (2 / 365) ≈ 0.00546
- First have to consider that #1 and 2 didn’t already win. Then multiply by 2 / 365 because now we know they must have distinct birthdays
- P4 = (1 – P1 – P2 – P3) * (3 / 365) ≈ 0.00815
- …
- P19 ≈ 0.3221
- P20 ≈ 0.3232
- P21 ≈ 0.3201
- …
You will notice that probabilities increase until 20th in line, and then decrease thereafter.
For a more elegant algebraic solution, you can check out the problem on Math StackExchange.
Thanks for your blog, nice to read. Do not stop.
By “standing before them,” do you mean standing DIRECTLY next to them (and before them), or ANYWHERE before them?
Don’t need to brute force it as much. You can calculate the probability that you win if you are nth in line p_n as: (n-1 choose 1) times 1/365*(364/365)*(363/365)*(363/365)…*(364-(n-3))/365. The point is that p_(n+1) = p_(n)*n*(364-(n-2))/365/(n-1) so you are interested in when the quantity n*(364-(n-2))/365/(n-1) is greater than or equal to 1 (and consequently when it is not), solving the equality gives precisely n>=19.
You’re right, and your approach is similar to one of the solutions I linked to on Math StackExchange.
I generally explain how I approached the puzzle, so in some cases like this, my solution isn’t the most elegant.