[bonanova]

A favorite puzzle asks how many people must be in a room

for chance to favor there being two with the same birthday

only 23

We ask a slightly different question:

How many people must be in a room for chance to favor every

day on the calendar being the birthday of someone in the room?

For simplicity you can ignore leap years.

[Izzy]

8395?

Edited March 2, 2009 by Izzy

[Prof. Templeton]

749. If 23 are needed for one day, we can now discard two of those 23 with the same birthday, which leaves 21. Add in two more people for everyday remaining in the year. 21 + (2*364) = 749

[EventHorizon]

A favorite puzzle asks how many people must be in a room

for chance to favor there being two with the same birthday

only 23

We ask a slightly different question:

How many people must be in a room for chance to favor every

day on the calendar being the birthday of someone in the room?

For simplicity you can ignore leap years.

If you have one person in a room, there's a 100% (365/365) chance that he has a birthday not the same as that of another person in the room.

The average number of people you'd need to add to the room before you have another unique birthday is equal to the reciprocal of the probability that the next person would have a unique birthday. So for a coverage of 2 days, it would be 1 + 365/(365-1).

For a coverage of x days on average, you'd need \sum^{x-1}_{i=0} 365/(365-i) people.

So for a coverage of 365 days, that ends up as 2364.646.....so 2365.

Oh, and thanks for yet another amusing mental diversion.

Edited March 2, 2009 by EventHorizon

[Guest]

Ok, I'm not sure we all have the same understanding of the problem, so i'll state mine:

'How many people should be in a room for the "probability that every day of the year corresponds to the birthday of at least one person in that room" to be over 0.5 ?'

Let's say we have k people. The ways in which we can "arrange" these indistinct people in 365 birthdays is

C(k, 365 + k -1) = (364+k)! / (k! 364!)

(It is like putting k indistinct balls in 365 drawers. They are indistinct because we don't care if it's Mr. Ted or Mr. Tom who has his birthday on jan 1, as long as someone has it that day).

Now, our arrangement requires that at least each "drawer" contain one ball. Let's take 365 balls out of k (which is obviously greater than 365), and we're left with X = k-365 people to place however we want.

The number of working solutions is thus

C(k-365, k -1) = (k-1)! / [(k-365)! 364!] .

The problem asks that the ratio between those two be over 1/2:

(k-1)! / [(k-365)! 364!] * (k! 364!) / (364+k)! = (k-1)!k!/[(k-365)!(364+k)!] > 0.5

But then I'm kinda stuck... I can simpify it in a couple ways, but apart from brute force (with an arbitrary-precision library), I don't see a nice analytical solution.

[bonanova]

Yes. That's the meaning I intended.

[Guest]

(k-1)! / [(k-365)! 364!] * (k! 364!) / (364+k)! = (k-1)!k!/[(k-365)!(364+k)!] > 0.5

I get the same solution, but UInt64 is the largest integer type I know of, and it isn't nearly enough to compute an answer. Maybe somebody will be ambitious enough to define a suitable struct, but not me...

[Guest]

I get the same solution...

Which is incorrect, now that I think of it. Take a small number, say 10, of objects to distribute among n people. I find it hard to believe that you would need to gather 130 people for there to be an even chance of all 10 objects being chosen. Also, it doesn't agree with the probability of k objects being distributed among k people of k!/k^k by rather a lot...

[EventHorizon]

Something didn't seem right about my answer, so I thought I would run some numbers.

class birthdays
{
public static void main(String[] args)
{
int samples = 100000;
int tests = 30;
int days = 365;

Random rand = new Random();
HashSet myset = new HashSet((int)(1.5*days));
ArrayList dayslist = new ArrayList(days);
int[] amount = new int[samples];

for(int i = 0; i < days; i++) dayslist.add(new Integer(i));

int summedians = 0;
double summeans = 0;
for(int blah = 0; blah < tests; blah++)
{
int sum = 0;
for(int i = 0; i < samples; i++)
{
int people = 0;
for(int j = 0; j < days; j++) myset.add(dayslist.get(j));

while(!myset.isEmpty())
{
myset.remove(dayslist.get(rand.nextInt(days)));
people++;
}
sum += people;
amount[i] = people;
}
Arrays.sort(amount);
int median = amount[samples/2];
summedians += median;
summeans += (sum/(double)samples);

System.out.println("Median:\t"+ median + "\tMean:\t" + (sum/(double)samples));
}
System.out.println("Mean of medians:\t"+(summedians/(double)tests));
System.out.println("Mean of means:\t"+(summeans/(double)tests));
}
}

import java.util.*;

And the output was the following...

Median: 2284 Mean: 2363.10243
Median: 2285 Mean: 2365.47104
Median: 2286 Mean: 2363.10352
Median: 2290 Mean: 2366.28145
Median: 2288 Mean: 2364.20396
Median: 2286 Mean: 2362.70582
Median: 2284 Mean: 2362.48123
Median: 2288 Mean: 2367.22836
Median: 2290 Mean: 2367.82558
Median: 2287 Mean: 2364.76775
Median: 2287 Mean: 2366.34486
Median: 2286 Mean: 2363.3707
Median: 2285 Mean: 2362.26175
Median: 2289 Mean: 2368.13559
Median: 2288 Mean: 2364.88628
Median: 2288 Mean: 2365.32214
Median: 2285 Mean: 2364.72983
Median: 2288 Mean: 2363.59692
Median: 2290 Mean: 2368.02351
Median: 2285 Mean: 2364.36295
Median: 2287 Mean: 2364.94598
Median: 2288 Mean: 2366.76404
Median: 2291 Mean: 2367.42208
Median: 2288 Mean: 2364.20179
Median: 2289 Mean: 2366.35936
Median: 2287 Mean: 2365.07976
Median: 2291 Mean: 2365.9666
Median: 2285 Mean: 2361.45806
Median: 2287 Mean: 2363.96604
Mean of medians: 2287.3
Mean of means: 2365.0509443333335

Median: 2287    Mean:   2367.15895

So I accurately predicted the mean for the number of people, but the median seems to make more sense for the answer to the problem. I decided to check the probabilities for these two numbers.

class birthdays
{
public static void main(String[] args)
{
int samples = 1000000;
int days = 365;

Random rand = new Random();
HashSet myset = new HashSet((int)(1.5*days));
ArrayList dayslist = new ArrayList(days);

for(int i = 0; i < days; i++) dayslist.add(new Integer(i));

int[] maxpeople = {2288,2365};
for(int k = 0; k < maxpeople.length; k++)
{
int wins = 0;
for(int i = 0; i < samples; i++)
{
int people = 0;
for(int j = 0; j < days; j++) myset.add(dayslist.get(j));
while(people++<maxpeople[k]) myset.remove(dayslist.get(rand.nextInt(days)));
if (myset.isEmpty()) wins++;
}
System.out.println("Probability for " + maxpeople[k] + " people:\t"+(wins/(double)samples));
}
}
}

import java.util.*;

This results in the output:

Probability for 2288 people: 0.501548

Probability for 2365 people: 0.573149

So my solution was the average number of people you'd need to have every day covered, but not the number of people to have a 50% chance of complete coverage.

It looks like there's still some work to be done on this problem.

[Guest]

Which is incorrect, now that I think of it. Take a small number, say 10, of objects to distribute among n people. I find it hard to believe that you would need to gather 130 people for there to be an even chance of all 10 objects being chosen. Also, it doesn't agree with the probability of k objects being distributed among k people of k!/k^k by rather a lot...

I thought about it a bit, and it does seem correct tbh.

With 2 drawers, you need 3 objects.

With 3 drawers, you already need 8 objects (easy to enumerate, and fits the formula).

With 4, you need 18 (took me a bit longer to enumerate, but I did and it still fits).

So i'm not surprised that it reaches 130 for 10 drawers. But then I'd expect the number to be pretty huge for 365 drawers.

[Guest]

So i'm not surprised that it reaches 130 for 10 drawers. But then I'd expect the number to be pretty huge for 365 drawers.

191677

[EventHorizon]

191677

Way too high. From my java code (posted a little earlier) I have some numbers on this. We now just need a good equation to find them. Of course, if you find a problem in my code let me know. I'm pretty sure it works though.

For 365 days it takes about 2288 people to reach 50% chance of complete coverage.

For 10 days it takes about 27 people to reach 50% chance of complete coverage (not 130).

Here's some data for 10 days. With the given number of people, I chose random birthdays. If it had complete coverage I counted it as a success, and checked the percentage after one million such trials.

Probability for 26 people: 0.478598

Probability for 27 people: 0.519286

Probability for 28 people: 0.557708

Just for information....here's some data on 4 days (which you said you needed 18).

Probability for 18 people: 0.977578

Probability for 5 people: 0.233602

Probability for 6 people: 0.380887

Probability for 7 people: 0.511769

Probability for 8 people: 0.622904

Probability for 9 people: 0.711121

So with 7 people it reaches 50% chance of complete coverage.

[Guest]

From my java code (posted a little earlier) I have some numbers on this. We now just need a good equation to find them. Of course, if you find a problem in my code let me know.

I don't think so. I did a quick simulation as well (without looking at your code) and came up with 2,292.

191677

I find it hard to believe that between, say, San Bernandino CA and Rochester NY, odds favor that somebody celebrates a birthday every day of the year in only one of them...

I think there is a problem in the way you are enumerating cases. If there are two "drawers", I only need two objects before I have a 50% chance of putting one in each. They can either be both in one drawer, both in the other, or there are two ways to put one in each.

[Guest]

I think there is a problem in the way you are enumerating cases. If there are two "drawers", I only need two objects before I have a 50% chance of putting one in each. They can either be both in one drawer, both in the other, or there are two ways to put one in each.

Mmh, good point. Turns out the "arrangement of balls in drawers" model doesn't quite fit the problem because the arrangements are not equiprobable.

Meh.