When the square-root rule undercounts by one

Question

A gym assigns each member a locker chosen uniformly at random from $100$ lockers, independently (two members can share).

What is the smallest number of members before two share a locker with probability greater than one half? Watch the approximation carefully here.

Accepted Answer

We want the smallest n with P(	ext{all distinct}) \le 	frac12, where P(	ext{all distinct}) = \frac{100}{100}\cdot\frac{99}{100}\cdots\frac{100-(n-1)}{100}. The quick rule n \approx 1.18\sqrt{d} gives 1.18\sqrt{100} = 11.8, suggesting 12. But when d is small the approximation is a bit optimistic, so we should check the exact product. - At n = 12: the product is 0.503, so a match happens with probability 0.497, still just under one half. - At n = 13: the product drops to 0.443, so a match happens with probability 0.557, over one half. So the true answer is n = 13, one more than the rule of t…

When the square-root rule undercounts by one

Your answer

Discussion

Learn the concepts

Related questions