5
$\begingroup$

I found the following problem in an number of places online:

John once bet a fellow gambler that two of the first thirty persons they met and spoke to would prove to have the same birthday. Strong in the thought that he had 365 days running for him, the second hustler was pleased to accept. Suspecting, not unnaturally, a frame-up, he was careful to approach total strangers and chance passers-by, who could not be known to John. He lost the bet on the twenty-eighth question, when a duplicate birthday turned up.

“To tell you the truth,” said John afterward, “on each of the last five guys we spoke to, the odds were already better than even money in my favor. I'll explain the mathematics to you some time.”

Why is this true? At what point did John's chance of filling his bet pass 25%? 50%? 75%? 90%? 99%? (For your calculations, assume there are only 365 unique birthdays.)

N.B. John's statement about "the last five guys" assumes they will talk to all thirty people, regardless of whether the bet condition has been met or not, and the "better than even money" refers to the chance he will win the bet on or before that person.

$\endgroup$
10
  • 1
    $\begingroup$ "on each of the last five guys we spoke to, the odds were better than even money in my favor." I don't think this is true. You would need 183 birthdays before this was true. The problem as a whole is sound though. $\endgroup$ May 30, 2014 at 19:08
  • $\begingroup$ @KendallFrey - not true. That was my initial reaction, but I can confirm that the probability passes 50% long before the 183rd person. $\endgroup$
    – Xynariz
    May 30, 2014 at 19:12
  • $\begingroup$ Not if you use the word 'each'. The probability of reaching one before 25 may be 50%, but the probability of getting a duplicate after 29 unique birthdays is 29/365. $\endgroup$ May 30, 2014 at 19:15
  • $\begingroup$ Close, but not quite. Have you seen kaine's answer? The chance that the bet will be fulfilled by the 29th person is much larger than $\frac{29}{365}$. $\endgroup$
    – Xynariz
    May 30, 2014 at 19:17
  • $\begingroup$ That's not at all what I said. I was referring to the chances of the bet being fulfilled on a specific person (which is what the question erroneously says). $\endgroup$ May 30, 2014 at 19:20

1 Answer 1

8
$\begingroup$

Probability two people have the same birthday: $\frac{1}{365}$

Probability that (if the first two of people don't have the same birthday) the third person is a duplicate: $\frac{2}{365}$

So the probability that by the third person, there is a duplicate is: $\frac{1}{365}+(1-\frac{1}{365})(\frac{2}{365})$

The probability that by the nth person they will have found a duplicate:

$P(n) = P(n-1)+(1-P(n-1))*\frac{n-1}{365}=\frac{n-1}{365}+P(n-1)\frac{366-n}{365}$

I don't feel like calculating this exactly by hand so:

$P(15) \approx .255$
$P(23) \approx .509$
$P(32) \approx .754$
$P(41) \approx .903$
$P(47) \approx .955$
$P(57) \approx .99$
$P(366) = 1$

These answers give the probability that he would win the bet by this turn. If, however, he were to say "Given that I have not yet won on turn $n-1$ the probability I will win on turn $n$ is greater than 50%" this does not occur so early. In this case, $P(n-1)=0$ so:

$P(n)=\frac{n-1}{365}$

In order for $P(n)>.5$ then

$n>183$.

$\endgroup$
4
  • $\begingroup$ This is the correct answer, with a nice formula to boot. $\endgroup$
    – Xynariz
    May 30, 2014 at 19:13
  • $\begingroup$ Thank you Kendall Frey for the OP's unintended second interpretation. $\endgroup$
    – kaine
    May 30, 2014 at 19:27
  • $\begingroup$ The question has been edited so that it is no longer ambiguous. $\endgroup$
    – Xynariz
    May 30, 2014 at 19:54
  • 1
    $\begingroup$ Further analysis can be had at wikipedia, where this problem has interesting implications for cryptographic hashing. $\endgroup$
    – phs
    May 30, 2014 at 20:28

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.