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

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.

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

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

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".

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.