Brute force solution to a birthday riddle

At one point a long time ago, one of my college professors asked our class how many people it would take to put in a room before the probability that two of the people had the same birthday was greater than or equal to 50 percent, took guesses from a few of us students, and then told us the answer was 12. Coming from a professor, this had to be true.

That answer has not sat well with me lo these many years since my drinking days, so sitting here with nothing else to do, I decided to try a little Monte Carlo problem solving.

Here is my VS 2008 C# console application code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Birthdays
{
    class Program
    {
        static int numberOfRuns;
        static int[] numberOfPeople;
        static List<int> birthdays;
        static Random rand;
 
        static int GetABirthday()
        {
            int b;
            int maxDays = (rand.Next(1, 5) == 1) ? 367 : 366;
 
            b = rand.Next(1, maxDays);
 
            return b;
        }
 
        static void Main(string[] args)
        {
            rand = new Random();
 
            Console.WriteLine("Birthdays application");
 
            Console.Write("How many times would you like to run a birthday search? ");
            string s = Console.ReadLine();
            numberOfRuns = Convert.ToInt32(s);
 
            numberOfPeople = new int[367];
            for (int i = 0; i < 367; i++)
            {
                numberOfPeople[i] = 0;
            }
 
            Boolean leaveLoop;
            int b;
            int leapDayMatches = 0;
            int leapDayBirthdays = 0;
            int totalBirthdays = 0;
            for (int i = 1; i <= numberOfRuns; i++)
            {
                birthdays = new List<int>();
                leaveLoop = false;
                while (!leaveLoop)
                {
                    b = GetABirthday();
                    totalBirthdays++;
                    if (b == 366)
                    {
                        leapDayBirthdays++;
                    }
                    if (birthdays.Contains(b))
                    {
                        numberOfPeople[birthdays.Count() + 1]++;
                        leaveLoop = true;
                        if (b == 366)
                        {
                            leapDayMatches++;
                        }
                    }
                    else
                    {
                        birthdays.Add(b);
                    }
                }
            }
 
            Console.WriteLine();
            Console.WriteLine("Breakdown of number of people required:");
            int ctr = 0;
            for (int i = 2; i <= 366; i++)
            {
                if (numberOfPeople[i] != 0)
                {
                    ctr += numberOfPeople[i];
                    Console.WriteLine(string.Format("{0} people: {1} ({2:P})", i, 
                                        numberOfPeople[i], ctr * 1.0 / numberOfRuns));
                }
            }
            Console.WriteLine(string.Format("Total birthdays generated: {0}", 
                                                totalBirthdays));
            Console.WriteLine(string.Format("Leap day birthdays: {0}", 
                                                leapDayBirthdays));
            Console.WriteLine(string.Format("Leap day matches: {0}", 
                                                leapDayMatches));
            Console.WriteLine();
            Console.WriteLine("Strike any key to end the program");
            Console.ReadKey();
        }
    }
}

The answer yielded by the above code is 23, as any meaningful sample size plugged into the program above will demonstrate.

Of course, we did not have the internet back then, but now a quick Google search yields plenty of discussion of the theory and math behind the puzzle. If you are interested, click this link.

Leave a Reply