How many people would you need in a group to make it likely that at least one member had a birthday on each of 365 days of the year?<p>Let's ignore leap years and define likely as >50% probability.
This is the coupon collector's problem.<p><a href="http://en.wikipedia.org/wiki/Coupon_collector%27s_problem" rel="nofollow">http://en.wikipedia.org/wiki/Coupon_collector%27s_problem</a><p>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".
I have no answer for you. I mean... the solution seems to be 2121 or 2122 (no, it isn't, see below) determined by brute force, but I don't know why.<p>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:<p><a href="http://projecteuler.net/" rel="nofollow">http://projecteuler.net/</a><p>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.
Brute force gives me about 2287/2288. Trying each number 1,000,000 times (distribute X balls in 365 bins, count number times all bins are filled) so it seems reliable, but maybe I have bug somewhere:<p>import java.util.Random;<p>public class Birthday {<p>private static Random rand = new Random(System.currentTimeMillis());<p>public static void main(String... args) {<p><pre><code> 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;
}
}</code></pre>
Here's my take:<p>Let n be the number of people needed.
Probability that a person's birthday is not today: 364/365<p>Prob. that no one's birthday is today: (364/365)^n<p>Prob. that someone's birthday is today: 1 - (364/365)^n<p>Prob. that someone's birthday covers every day: (1 - (364/365)^n)^365<p>Setting equal to 0.5 and solving, I get n==2284, which is close to metaphyze's brute force number.
Here's a link to the wikipedia entry on the birthday problem.<p><a href="http://en.wikipedia.org/wiki/Birthday_problem" rel="nofollow">http://en.wikipedia.org/wiki/Birthday_problem</a>
This solves the problem for you. <a href="http://en.wikipedia.org/wiki/Birthday_problem" rel="nofollow">http://en.wikipedia.org/wiki/Birthday_problem</a><p>23 people is a 50% chance, 57 is a 99% chance, 367 is 100% chance (including leap years).