Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

11–16 of 16 posts

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

#12

Post by metaphyze »

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  .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 = 0) {
			whichBin = rand.nextInt(bins.length);

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

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

		return total;

	}

}

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

#13

Post by [deleted] »

metaphyze wrote: post #12

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 fl…

[deleted]

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

#14

Post by metaphyze »

wnoise wrote: post #8

This is the coupon collector's 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".

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.

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

#15

Post by dded »

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.

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

#16

Post by jackgolding »

metaphyze wrote: post #12

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 fl…

Oh God that function
Post reply on HN