50 Challenging Problems in Probability [Part 31]: Birthday Pairings

Published in

Intuition

5 min readJun 23, 2024

Hi, I’ve recently developed an interest in problems related to probability. I came across this book “Fifty Challenging Problems in Probability with Solutions” by Frederick Mosteller. I thought it would be interesting to create a series discussing these captivating problems that might arise as interview questions. Each post will feature only 1 problem, making it a series with a total of 50 parts. Let’s dive in and activate our brain cells 🧠!

Problem:

What is the least number of persons required if the probability exceeds 1/2 that two or more of them have the same birthday?

(Year of birth need not match. You can ignore February 29 as a possible birthday. The other 365 days are equally likely birth dates.)

Solution:

We start by finding the probability that everyone has a different birthday. Let N be the number of people in total. The probability that no two have the same birthday is:

The number of ways everyone can have a different birthday is:

The total number of ways everyone can have a different birthday without restriction is:

Therefore, the probability that among N people, everyone has a different birthday is:

The probability that two or more of them have the same birthday is:

Let’s plot this probability for different N:

from math import factorial
import matplotlib.pyplot as plt

probs = []
for N in range(101):
    probs.append(1-(factorial(365)/(factorial(365-N)*365**N)))

plt.plot(range(101), probs)
plt.axhline(0.5, ls = 'dashed', c = 'r')
plt.grid(True)
plt.xlabel('N', fontsize=12)
plt.ylabel('Probability', fontsize=12)
plt.title('Probability that two or more of them have the same birthday')

It looks like when the probability exceeds 0.5 when N is between 21 and 25. Let’s verify this:

for N in range(21,26):
    prob = 1-(factorial(365)/(factorial(365-N)*365**N))
    print(f'N = {N} --> prob = {prob:.3f}')

# Outputs:
# N = 21 --> prob = 0.444
# N = 22 --> prob = 0.476
# N = 23 --> prob = 0.507
# N = 24 --> prob = 0.538
# N = 25 --> prob = 0.569

As we see, we need at least 23 people for the probability that two or more of them have the same birthday to exceed 1/2.

This result may surprise those who might guess the number to be around 183 (≈ 365/2). However, it’s important to consider that the birthday comparisons involve every possible pair of individuals. With 23 individuals, there are (23 × 22)/2 = 253 pairs to consider, which is significantly more than half the number of days in a year.

Bonus question: What is the least number of persons required if the probability exceeds 1/2 that two or more of them have either the same birthday or adjacent birthdays (December 31 is adjacent to January 1)?

Again, we start by finding the probability that no pair has either the same birthday or adjacent birthdays. Unlike the previous case, the number of valid birthdays decreases by 3 (instead of 1) for each subsequent person. Since we have less strict requirement, we know that the minimum number of persons for the probability that two or more of them have either the same birthday or adjacent birthdays to exceed 1/2 must be less than 23.

probs = []
for N in range(1, 24):
    valid_arrangements = 1  # Starts with 1 way to arrange 0 birthdays
    valid_days = 365
    for i in range(1, N + 1):
        valid_arrangements *= max(0, valid_days)
        valid_days -= 3  # Decrease the number of valid days by 3 for each new person
    probs.append(1-(valid_arrangements/(365**N)))

plt.plot(range(23), probs)
plt.axhline(0.5, ls = 'dashed', c = 'r')
plt.grid(True)
plt.xlabel('N', fontsize=12)
plt.ylabel('Probability', fontsize=12)
plt.title('Probability that two or more of them have the same/adjacent birthday')

for N in range(11,15):
    valid_arrangements = 1  # Starts with 1 way to arrange 0 birthdays
    valid_days = 365
    for i in range(1, N + 1):
        valid_arrangements *= max(0, valid_days)
        valid_days -= 3  # Decrease the number of valid days by 3 for each new person
    prob = 1-(valid_arrangements/(365**N))
    print(f'N = {N} --> prob = {prob:.3f}')

# Outputs:
# N = 11 --> prob = 0.372
# N = 12 --> prob = 0.429
# N = 13 --> prob = 0.485
# N = 14 --> prob = 0.540

As we see, we need at least 14 people for the probability that two or more of them have either the same birthday or adjacent birthdays to exceed 1/2.

And that’s all for this birthday 🎂 problem. Any feedback or questions are welcome! The code is available on my Github. Check out the other problems in this series:

Shelvia