Ask HN: A random maths problem we started discussing at work

http://en.wikipedia.org/wiki/Coupon_collector%27s_problem

The formula in the article (1/2 + n*gamma + n log n) gives 2365 for the expected number, but this is different than "at least 50% chance".

But, it's worth noting that if this interests you, Project Euler almost certainly will as well and is worth checking it out if you don't already know about it:

http://projecteuler.net/

EDIT: So if you're wondering why I got a different brute force result from other users, it's because I had a stupid bug. I was looking at the ratio of meeting the criteria to the ratio of not meeting it, not the ratio of meeting it to total.

import java.util.Random;

public class Birthday {

private static Random rand = new Random(System.currentTimeMillis());

public static void main(String... args) {

		final int n = 365;
		boolean[] bins = new boolean[n];

		final float maxNumberOfAttempts = 1000000;
		for (int numberOfBalls = 2285; numberOfBalls <= 2400; ++numberOfBalls) {

			int attempts = 0;
			int numberOfTimesAllBinsFilled = 0;

			while (attempts < maxNumberOfAttempts) {
				if (distribute_X_Balls_in_N_bins_randomly_and_return_the_number_of_filled_bins(
						numberOfBalls, bins) == n) {
					numberOfTimesAllBinsFilled++;
				}
				++attempts;
			}

			float prob = numberOfTimesAllBinsFilled / maxNumberOfAttempts;
			System.out.println((prob > .5 ? "PASSED:" : "FAILED:") + numberOfBalls + ":" + prob);

		}
	}

	public static int distribute_X_Balls_in_N_bins_randomly_and_return_the_number_of_filled_bins(
			int x, boolean[] bins) {
		for (int inx = 0; inx < bins.length; ++inx) {
			bins[inx] = false;
		}

		int whichBin = 0;
		int total = 0;

		while (--x >= 0) {
			whichBin = rand.nextInt(bins.length);

			if (!bins[whichBin]) {
				bins[whichBin] = true;
				++total;

                                if (total == bins.length) {
					return total;
				}
			}
		}

		return total;

	}

}

Let n be the number of people needed. Probability that a person's birthday is not today: 364/365

Prob. that no one's birthday is today: (364/365)^n

Prob. that someone's birthday is today: 1 - (364/365)^n

Prob. that someone's birthday covers every day: (1 - (364/365)^n)^365

Setting equal to 0.5 and solving, I get n==2284, which is close to metaphyze's brute force number.

http://en.wikipedia.org/wiki/Birthday_problem

23 people is a 50% chance, 57 is a 99% chance, 367 is 100% chance (including leap years).