17

There is a big line of people waiting outside a theater for buying tickets. The theater owner comes out and announces that the first person to have a birthday same as someone standing before him in the line gets a free ticket. Where will you stand to maximize your chance?

13 accepted

You should stand 20th in line.

The chance of you winning is the chance of none of the people before you winning AND you having a birthday the same as someone before you in line.

The calculations are easy if you realise that when you know nobody before you won, you know they all have different birthdays, so the probability that you have the same birthday as someone before you in line is then (k-1)/365. So:

Prob[person at place k wins] = (1-Prob[person at place <k wins])*(k-1)/365

In C++ code:

#include <iostream>

using namespace std;

int main()
{
   double sum = 0;

   int max_i = 0;
   double max_chance = 0;

   for (int i = 1; i < 365; ++i) {
      double chance = (1.0-sum)*(i-1)/365;
      cout << "Person " << i << " has " << chance*100 << "% chance." << endl;
      sum += chance;
      if (chance > max_chance) {
         max_chance = chance;
         max_i = i;
      }
   }

   cout << "Person " << max_i << " has the highest chance: " << max_chance*100 << "%." << endl;
   cout << "Sum of probabilities (should be 1): " << sum << endl;
}

This code tells me I should stand 20th in line, and I have 3.23199% chance of winning.

EDIT: Added one line to the code to print the total sum of probabilities. This should be 1, and it is 1 on my machine (Well, almost. There are some rounding errors).

12

I think the explicit probability function is:

q[n_] := (n n!) Binomial[365, n]/365^(n+1)   

enter image description here

N[Max[Table[q[n], {n, 100}]]]
0.0323199

N@q[19]
0.0323199

Which confirms that standing 20th in the row maximizes your probability

As for the cumulative probability function:

DiscretePlot[Sum[q[m], {m, 1, n}], {n, 100}]  

enter image description here

Edit

Now suppose we want to solve the problem for a year with any number of days. This could be used to solve the same kind of problem with "People whose birthday is on the same day of the week" or "People whose birthday is on the same Chinese calendar animal". Here you can see the optimal position in the queue, as a function of the number of days in a year:

enter image description here

0

The problem with standing last is that there might be people before you that already meet the criteria.

Answer: I stand in the position 58 of the line.

Check this out:

http://en.wikipedia.org/wiki/Birthday_problem

0

If there are m people and n possible birthdays then the probability that all m have different birthdays is approximately exp(-m^2/2n)