The Birthday Problem is a fascinating probability question that seems counterintuitive at first. It asks: how many people do you need to have in a room before the probability of at least two people sharing the same birthday becomes greater than 50%?

Intuitively, you might guess that you would need a very large number of people for this to happen. After all, there are 365 possible birthdays (ignoring leap years for simplicity). However, the answer is surprisingly low: only 23 people are needed!

Here's why:

Imagine placing 23 people in a room. For each person, we consider their birthday as a random event (like a coin flip). There are 365 equally likely outcomes for each person's birthday.

Now, let's calculate the probability that no two people share a birthday. The first person can have any of the 365 birthdays. The second person can have any of the remaining 364 birthdays (since someone else already took the first day). This continues until the 23rd person, who only has 343 birthdays left to choose from (because 22 other people have already chosen birthdays).

So, the probability of no shared birthdays seems pretty high: 365 * 364 * ... * 343. But this isn't quite right. Why? Because the order in which we choose the birthdays doesn't matter. If John has a birthday on July 1st and Mary has a birthday on July 1st, it's the same scenario as Mary having a birthday on July 1st and John having a birthday on July 1st.

To account for this overcounting, we need to divide the probability we calculated above by the number of ways to order 23 people. This number is 23!, or 23 factorial (23 x 22 x 21 x ... x 1).

When we do the math, we find that the probability of no shared birthdays in a room of 23 people is actually quite low: around 0.507. This means the probability of at least two shared birthdays is 1 — 0.507 = 0.493, or about 49.3%.

So, the Birthday Problem demonstrates how probability can be surprising, even for seemingly simple events like coin flips. It highlights the importance of careful analysis and consideration of all factors when dealing with random events.

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;

const int DAYS_IN_YEAR = 365;

bool has_shared_birthday(const vector<int>& birthdays) {
  // Sort the birthdays for efficient comparison
  vector<int> sorted_birthdays = birthdays;
  sort(sorted_birthdays.begin(), sorted_birthdays.end());

  // Check for duplicates
  for (int i = 1; i < sorted_birthdays.size(); ++i) {
    if (sorted_birthdays[i] == sorted_birthdays[i - 1]) {
      return true; // Shared birthday found
    }
  }

  return false; 
}

int main() {
  const int NUM_PEOPLE = 23; 
  const int NUM_SIMULATIONS = 10000; 

  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> dis(1, DAYS_IN_YEAR);

  int shared_birthdays_count = 0;

  for (int i = 0; i < NUM_SIMULATIONS; ++i) {
    vector<int> birthdays;
    for (int j = 0; j < NUM_PEOPLE; ++j) {
      birthdays.push_back(dis(gen));
    }

    if (has_shared_birthday(birthdays)) {
      shared_birthdays_count++;
    }
  }

  double probability = static_cast<double>(shared_birthdays_count) / NUM_SIMULATIONS;
  cout << "Probability of shared birthdays in " << NUM_PEOPLE 
       << " people: " << probability << endl;

  return 0;
}