Buyers before two share a collectible card

Question

A vending machine dispenses a collectible card chosen uniformly at random from $500$ distinct designs, independently for each buyer.

What is the smallest number of buyers before two of them are more likely than not to hold the same design?

Accepted Answer

We want the smallest n with P(	ext{all distinct}) \le 	frac12. Each of the \binom{n}{2} pairs of buyers matches with probability 1/500, and the chance of no match is close to P(	ext{all distinct}) \approx e^{-\binom{n}{2}/500}. Set this equal to 	frac12: \frac{\binom{n}{2}}{500} \approx \ln 2 = 0.693 \implies \binom{n}{2} \approx 347 \implies n \approx 27. The exact product confirms it: at n = 26 the match probability is about 0.48, and at n = 27 it is about 0.51. So n = 27 buyers. The rule of thumb n \approx 1.18\sqrt{d} gives 1.18\sqrt{500} \approx 26.3, rounding up to 27. Takeaway. Wit…

Buyers before two share a collectible card

Your answer

Discussion

Learn the concepts

Related questions