A professor - according to Reddit - asked their class how many people you’d need to have in a room to be absolutely certain two of them would have Social Security numbers ((any randomly-assigned number with at least four digits will do just as well)) ending in the same four digits (in the same order).

10001, obviously.

How about a probability of 99.9%? The students guessed 1,000, 8,000 and even 9,990. The true answer? 370.

That’s a slightly involved calculation, related to the Birthday Problem; one would need to compute the complementary product $\br{\frac{9999}{10000}\times\frac{9998}{10000}\times …}$ until you reached a number below 0.001.

Computation is boring. Let’s estimate!

Suppose you have a set of $n$ people. There are $m=\nCr{n}{2}$ possible matchings between them, each of which has a (not quite but almost independent) probability of $p$.

Then the probability of none of those matches being a hit is $\br{1-p}^m$, so we need to solve $\br{1-p}^m < 0.001$ for $m$ (which is a function of $n$).

Taking logs gives $m \ln(1-p) < -\ln(1000)$.

We know that for small $p$, $\ln(1-p)\approx -p$, and for all values of 1000, $\ln(1000) = 3\ln(10) \approx 6.9$.

Now we have $-mp < -6.9$ (ish), or $m > \frac{6.9}{p}$.

However, $m = \nCr{n}{2}$, which is roughly $\frac{n^2}{2}$.

This gives us $\frac{n^2}{2} > \frac{6.9}{p}$, or $n > \sqrt{\frac{13.8}{p}}$.

We know that $p = 10^{-4}$, so $n > 100 \sqrt{13.8}$.

Did someone call for a Ninja?

Whoosh

“The square root of 1369 is 37, so the square root of 1380 is about $37 + \frac{11}{74}$, or $37.15$. That means $\sqrt{13.8} \approx 3.715$.”

Whoosh

Back to our regularly scheduled programming

This gives us a final approximation of $n > 371.5$ - not far at all from the correct answer of 370.

The professor, I’m told, used a whole gamut of series and approximations to get an approximation of 375. I shall smile smugly in their general direction.