5 ms·

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

8 points by cleis 13y ago

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? Let's ignore leap years and define likely as >50% probability.

minussohn 13y ago
are you too stupid or too lazy to use a proper web search engine?
DanielStraight 13y ago
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. 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/ 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.
chaoticgeek 13y ago
This solves the problem for you. http://en.wikipedia.org/wiki/Birthday_problem 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).
- apourchet 13y ago
  His question isn't related to the 'Birthday Problem'. Read the whole post...
darkxanthos 13y ago
Here's a link to the wikipedia entry on the birthday problem. http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem
- DanielStraight 13y ago
  This isn't the birthday problem. OP is asking how many people to hit every possible birthday at least once. I thought Wikipedia might cover this on their birthday problem page, but they don't.
wnoise 13y ago
This is the coupon collector's problem. http://en.wikipedia.org/wiki/Coupon_collector%27s_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".
- brd 13y ago
  Well... you made my day complete. My brute force approach got me 2364.646, glad to know my math intuition isn't entirely broken. Thanks for the link!
- metaphyze 13y ago
  I don't think this is exactly the same as the proposed problem. What it's giving you is the expected value. This includes in its calculation the lower probability cases and the higher probability cases. For instance, there's a slim change of this happening when the number of employees is 365. It's been a while since I took probability, but I think the expected value is going to be larger than the minimum value needed to achieve a .5 probability if the probability graph is skewed, which in this case it is.
deleted 13y ago
[deleted]
deleted 13y ago
[deleted]
metaphyze 13y ago
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: 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; } }
- deleted 13y ago
  [deleted]
- jackgolding 13y ago
  Oh God that function
dded 13y ago
Here's my take: 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.

8 points by cleis 13y ago

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? Let's ignore leap years and define likely as >50% probability.

minussohn 13y ago

are you too stupid or too lazy to use a proper web search engine?

DanielStraight 13y ago

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

chaoticgeek 13y ago

This solves the problem for you. http://en.wikipedia.org/wiki/Birthday_problem 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).

apourchet 13y ago
His question isn't related to the 'Birthday Problem'. Read the whole post...

darkxanthos 13y ago

Here's a link to the wikipedia entry on the birthday problem. http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem

DanielStraight 13y ago
This isn't the birthday problem. OP is asking how many people to hit every possible birthday at least once. I thought Wikipedia might cover this on their birthday problem page, but they don't.

wnoise 13y ago

This is the coupon collector's problem. http://en.wikipedia.org/wiki/Coupon_collector%27s_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".

brd 13y ago
Well... you made my day complete. My brute force approach got me 2364.646, glad to know my math intuition isn't entirely broken. Thanks for the link!
metaphyze 13y ago
I don't think this is exactly the same as the proposed problem. What it's giving you is the expected value. This includes in its calculation the lower probability cases and the higher probability cases. For instance, there's a slim change of this happening when the number of employees is 365. It's been a while since I took probability, but I think the expected value is going to be larger than the minimum value needed to achieve a .5 probability if the probability graph is skewed, which in this case it is.

deleted 13y ago

[deleted]

deleted 13y ago

[deleted]

metaphyze 13y ago

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: 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; } }

deleted 13y ago
[deleted]
jackgolding 13y ago
Oh God that function

dded 13y ago

Here's my take: 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.