At a movie theater, the whimsical manager announces that a free ticket will be given to the first person in line whose birthday is the same as someone in line who has already bought a ticket. You have the option of choosing any position in the line. Assuming that you don't know anyone else's birthday, and that birthdays are uniformly distributed throughout the year (365 days year), what position in line gives you the best chance of getting free ticket?

  • $\begingroup$ Direct calculation works....were you hoping for an elegant answer? $\endgroup$ – lulu May 29 '16 at 20:41

The probability, $p(n)$, of getting a free ticket when you are the $n_{th}$ person is line is:

(probability that none of the first $n−1$ people share birth dates) * (probability that you share birthday with one of the first $n−1$ people)

So, $p(n) = [1 *(\frac{364}{365})*(\frac{363}{365}) * ... *(\frac{(365−(n−2))}{365})] * [\frac{(n−1)}{365}]$,

Here, $0 <n \leq 365$.

Now the least $n$ such that $p(n) > p(n+1)$, or $\frac{p(n)}{p(n+1)} > 1$.

Now, $\frac{p(n)}{p(n+1)} = \frac{365}{(366−n)} * \frac{(n−1)}{n}$

$\implies 365n − 365 > 366n − n^2 $,

$\implies n^2 − n - 365 > 0$

$\implies (n - \frac{(1+\sqrt(1461)}{2})*(n - \frac{(1-\sqrt(1461)}{2}) > 0$

$\implies n = \frac{(1+\sqrt(1461)}{2} = 19.6115148536 $ ($\because n>0$)

$\implies n = 20$ (ceiling of computed value)

Hence the $20^{th}$ position maximizes the chances.

Note: See my first comment below if you don't want to solve quadratic equation using discriminant method.

| cite | improve this answer | |
  • $\begingroup$ Is there a quick way to solve $n^2-n-365$ $\endgroup$ – Gerry May 29 '16 at 20:59
  • 1
    $\begingroup$ So $n^2 - n >365$, $\implies (n - \frac 12)^2 -(\frac 12)^2 > 365$, $\implies (n - \frac 12)^2 > 365 + (\frac 12)^2$. Now reject the -ve part, $n - \frac 12 > \sqrt(365.25)$, $\implies n > 19.6115148536$ $\endgroup$ – Rahul May 29 '16 at 22:20

Let $p_n$ be the probability that the $n$th person in line wins, and let $q_n$ be the probability that the first $n$ persons have different birthdays. Then for a generic $n$ we have $$ p_{n+1} = q_n \frac{n}{365} \\ p_{n+2} = q_n \frac{365-n}{365} \frac{n+1}{365} $$ and therefore $$ \frac{p_{n+2}}{p_{n+1}} = \frac{(365-n)(n+1)}{365n} $$ This is larger than $1$ if and only if $$ (365-n)(n+1) > 365n $$ which rearranges as $$ n(n+1) < 365 $$ Initially the $p_n$s grow steadily, but eventually they start to fall steadily towards $0$. The last $n$ for which $n(n+1)<365$ is $18$, so the largest $p_n$ will be $p_{20}$.

| cite | improve this answer | |

Suppose you stand in slot $n$. In order for you to get the free ticket you need two things: first, that no duplicate has happened before your turn and second, that you are a duplicate.

The probability that there is no duplicate amongst the first $n-1$ is $$\frac {365!}{365^{n-1}\times (365-(n-1))!}$$

Given that no duplicate has occured amongst the first $n-1$, the probability that the $n^{th}$ is a duplicate is then $$\frac {n-1}{365}$$

The probability that the $n^{th}$ position is the winner is the product of these.

It is easy to compute these directly (at least with mechanical assistance) and we see that $n=20$ is optimal with $$p_{20}=\fbox {0.032319858}$$

For comparison, we have $p_{19}=0.032207108$ and $p_{21}=0.032249952$. But you have some room here...$p_{15}=0.029798808$ and $p_{25}=0.030355446$, say.

| cite | improve this answer | |
  • $\begingroup$ Can you elaborate on how you arrived at expression for probability of no duplicate amongst the first n-1 $\endgroup$ – Gerry May 29 '16 at 21:02
  • $\begingroup$ Sure: first one can be anything, hence $\frac {365}{365}$. Second can't match the first, so $\frac {364}{365}$ and so on down to $\frac {365-(n-1)+1}{365}$ and multiplying these gives my formula. Alternatively, think of this has the number of ordered choices of $n-1$ distinct things from a possible $365$ divided by the total number of ordered ways to choose $n-1$ things (possibly not distinct) from $365$. $\endgroup$ – lulu May 29 '16 at 21:08
  • $\begingroup$ Thanks @lulu. Is there a way to differentiate $$\frac {365!}{365^{n-1}\times (365-(n-1))!} * \frac{n-1}{365}$$ to analytically arrive at extremum rather than relying on mechanical assistance. Something like equate $$f'(n) = 0$$ to arrive at $n$. $\endgroup$ – Gerry May 29 '16 at 22:24
  • $\begingroup$ may be use gamma function notation to differentiate factorial part? $\endgroup$ – Rahul May 29 '16 at 22:30
  • $\begingroup$ Gamma function ought to work...but you'd still have to compare two values, so I doubt that it saves any time. Usually, in my experience, you want to know how the probabilities behave around the max anyway...so you'd want a bunch of values. $\endgroup$ – lulu May 29 '16 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.