The birthday paradox itself is well known. I am only interested in a small aspect here:
The number of pairings in the original problem is
$${23 \choose 2} = \frac{23 \cdot 22}{2}=253$$
Another version is the same-birthday-as-you problem. It turns out that you need also at least $253$ people to get over $50%$ probability.
$$1 - \left( \frac{364}{365} \right)^{253}=1-0.499$$
I am interesting in this double occurrence of $253$:
- Wikipedia states it is not a coincidence
- Ian Stewart states in an Scientific American article that it is a coincidence
My question
Who is right and why?
Addendum
Just for the sake of completeness after receiving the great answers below (for which I am very grateful): In the meantime I had also contacted Ian Stewart on the matter and he too acknowledges the connection. He told me that in fact one of his readers wrote in
soon after the article was published to point it out.
The first problem: $23$ comes as the answer to "the smallest integer $n$ such that $n!\binom{365}{n} / {365^n} < \frac12$". Then the $253$ comes as $\binom{23}{2}$.
The second problem: $253$ comes as the answer to "the smallest integer $m$ such that $\left(\frac{364}{365}\right)^m < \frac12$."
So the first $253$ is necessarily a number of the form $\binom{n}{2}$ (a triangular number), while the second $253$ can be any integer whatsoever. In that sense, it is a coincidence that they happen to be exactly equal (that the answer to the second problem happens to be a triangular number).
On the other hand, it is not a coincidence that they are approximately equal. We can see this by approximating the first problem (the classical birthday problem) as follows. If there are $n$ people, there are $\binom{n}{2}$ pairs. For a given pair, the probability that they don't have their birthday in common is $\frac{364}{365}$. If we treat all these $\binom{n}{2}$ pairs as independent (this is the approximation) then the probability that all birthdays are distinct is simply got by multiplying $\frac{364}{365}$ those many times, thus we want the smallest $n$ such that $\left(\frac{364}{365}\right)^{\binom{n}{2}} < \frac12$. Equivalently, $253$ is the answer to "the smallest $\binom{n}{2}$ such that $\left(\frac{364}{365}\right)^{\binom{n}{2}} < \frac12$." This is an approximation to the exact problem, but not a very far off one.
Conclusion: Ian Stewart more or less makes a mistake, when he writes
It is not at all a coincidence that the answer to "(approximately) the smallest $\binom{n}{2}$ such that $\left(\frac{364}{365}\right)^{\binom{n}{2}} < \frac12$", and the answer to "the smallest integer $m$ such that $\left(\frac{364}{365}\right)^m < \frac12$" happen to be approximately equal.
For concreteness, here for various values $d$ in place of $365$ are the actual values $\binom{n}{2}$ (where $n = n(d)$ is the answer to the first problem) and $m$ (where $m = m(d)$ is the answer to the second problem). Note that around $d = 365$ the second column $\binom{n}{2}$ varies slowly, being sometimes less and sometimes more than the third column $m$, because it can only take values like $\binom{22}{2} = 231$, $\binom{23}{2} = 253$, $\binom{24}{2} = 276$, etc., while the third column can also take values in between.
$$ \begin{array}{r|r|r} d & \binom{n}{2} & m \\ \hline 50 & 36 & 35 \\ 100 & 78 & 69 \\ 200 & 136 & 139 \\ 250 & 171 & 173 \\ 300 & 210 & 208 \\ 330 & 231 & 229 \\ 340 & 231 & 236 \\ 350 & 253 & 243 \\ 360 & 253 & 250 \\ 363 & 253 & 252 \\ 364 & 253 & 252 \\ \hline 365 & 253 & 253 \\ \hline 366 & 253 & 254 \\ 367 & 253 & 255 \\ 370 & 253 & 257 \\ 380 & 276 & 264 \\ 390 & 276 & 270 \\ 400 & 276 & 277 \\ 500 & 351 & 347 \\ 600 & 435 & 416 \\ 800 & 561 & 555 \\ 1000 & 703 & 693 \\ 2000 & 1378 & 1386 \\ 5000 & 3486 & 3466 \\ 10000 & 7021 & 6932 \\ 20000 & 13861 & 13863 \\ 50000 & 34716 & 34658 \\ 100000 & 69378 & 69315 \end{array} $$
Values of $d$ upto $1000$ for which the two numbers coincide (like they do with $d = 365$) are many: 4, 8, 9, 14, 21, 22, 30, 40, 51, 52, 64, 65, 79, 95, 112, 113, 131, 151, 173, 196, 220, 221, 246, 247, 274, 303, 333, 365, 398, 432, 433, 468, 469, 506, 545, 585, 586, 627, 628, 670, 671, 715, 716, 761, 762, 809, 858, 908, 909, 960, 961. These are also precisely the values of $d$ for which $m$ happens to be a triangular number. Actually, it can be proved with some effort using the known bounds on $n$ that this is always true in general.