Birthday problem without electronic aids in a nuclear winter The Birthday Problem is well known, with many related questions and answers on this site.
Most solutions somewhere make use of a statement equivalent to:
$\frac{365!}{342!365^{23}} < \frac 1 2$. The correctness of this statement is usually demonstrated by asserting (by use of a calculator, other electronic means, or log tables) that the left hand side is approximately 0.492703.
My question asks: "What would be the most efficient way of demonstrating the truth of the above statement using only pen and paper?"  Assume that all computers and tables of logarithms have been destroyed in a nuclear holocaust.
Clearly it would be possible (but painful) to do this following long-division in long-hand:
$$\frac{365\cdot 364 \cdot 363 \cdot \dots \cdot 343 } {365\cdot 365 \cdot 365 \cdot \dots \cdot 365}$$ but there must be better ways.
My first thought was to prove something simpler from which the result still follows.  For example, one can show easily with pen and paper that
$$\frac{365!}{342!365^{23}} = \prod_{k=0}^{22}\left(1-\frac k {365}\right)<\prod_{k=0}^{22}  e^{-\frac k {365}}= \exp\left({-\frac {253}{365}}\right).$$  It would therefore be sufficient to demonstrate that $\exp\left({-\frac {253}{365}}\right) < \frac 1 2$ (which is a true statement since $\exp\left({-\frac {253}{365}}\right) \approx 0.4999982478$). Equivalently it would be sufficient to show that $\frac{253}{365}>\ln 2$.  But these may not be the best ways of proceeding, and I have not managed to bring them to a satisfactory pen-and-paper conclusion.
 A: This isn't great but should be possible by hand.
Since
$$\ln(x)= \sum_{n=1}^\infty \frac{1}{n}\left(\frac{x-1}{x}\right)^n$$
we have
$$\ln(2)
 = \sum_{n=1}^\infty \frac{1}{n \cdot 2^n}
 = \sum_{n=1}^{15}\frac{1}{n \cdot 2^n} + \sum_{n=16}^\infty \frac{1}{n \cdot 2^n}$$
For the first fifteen term, you can do some tedious arithmetic to get
$$\sum_{n=1}^{15} \frac{1}{n \cdot 2^n} = \frac{31972079}{46126080} = 0.6931453745\overline{906870}$$
For the tail, you can approximate as follows:
$$\sum_{n=16}^\infty \frac{1}{n \cdot 2^n} < \frac{1}{16}\sum_{n=16}^\infty \frac{1}{2^n} = \frac{1}{524288} = 0.0000019073486328125$$
Adding these together you get
$$\ln(2) < 0.6931472819393199031\overline{870906} < 0.6\overline{93150684} = \frac{235}{365}$$

Well, that's still pretty bad, but I've already typed it, so might as well post.
A: I think I have a much better/simpler/more-direct approach to answering this question.  It's nothing to do with my previous $\ln 2$ related answer (see elsewhere in this thread) so I'm posting it separately.  
Here I try to show directly $$\frac{365!}{342!365^{23}} <\frac 1 2$$ using only a `difference of two squares' inequality: $a^2\ge a^2-b^2 = (a+b)(a-b)$. 
Here goes:
$$\begin{align}
\frac{365!}{342!365^{23}} &= \frac{365\cdot 364 \cdot 363 \cdot \dots \cdot 343 } {365^{23}}
\\
&= 
\frac{(354+11)\cdot (354+10) \cdot  \dots \cdot (354-10)\cdot(354-11) } {365^{23}}
\\
&= 
\frac{\left[(354^2-11^2)\cdot (354^2-10^2) \cdot  \dots \cdot (354^2-1^2)\right]\cdot(354-0) } {365^{23}}
\\
&<
\frac{\left[(354^2-0^2)\cdot (354^2-0^2) \cdot  \dots \cdot (354^2-0^2)\right]\cdot(354-0) } {365^{23}}
\\
&=
\left(\frac{354}{365}\right)^{23}.
\end{align}
$$
From here it is relatively easy to show (with only pen and paper) that $\left(\frac{354}{365}\right)^{23}\approx0.495<\frac 1 2$.  For example, abbreviating the value of $\frac{354}{365}$ by the symbol $\rho$, we could repeatedly square $\rho$ no more than four times, and then evaluate $\rho^{23}$ from the product $\rho^{1+2+4+16}=\rho^1 \rho^2 (\rho^2)^2 (((\rho^2)^2)^2)^2$.  This requires a total of seven multiplications (four taken while repeatedly squaring $\rho$, and then a further three multiplications to combine those results into the final answer).
A: [Declaration of interest: this answer is posted by (me) the author of the original question.  For the reasons set out below, I come to the conclusion that Alexis's answer is better, though, so won't be up-voting this post, but publish it in case it inspires anyone else.]
My line of enquiry relating to attempts to show that $\frac {253}{365}>\ln 2$ went as follows:
$$
\begin{align}\ln 2 &= \ln \left(\frac {4} 3 \cdot \frac 3 2\right)\\
&=\ln\left(1+\frac 1 3\right) + \ln\left(1+\frac 1 2\right)
\\
&= 
-\sum_{k=1}^{\infty} \frac {1} {(-3)^k k}
-\sum_{k=1}^{\infty} \frac {1} {(-2)^k k}.
\end{align}
$$
Since the series above have terms of alternating sign and decreasing magnitude, we know that truncation error obtained by summing each for a finite number of terms is bounded by the magnitude of the first omitted term.  How many terms would we need in order to calculate $\ln2 $ precisely enough for our purposes?  The number we are trying to establish the sign of is $\frac {253} { 365} - \ln 2\approx 3.5\times 10^{-6}$, so we need an accuracy better than that.    The $k=10$ term of the first sum and the $k=16$ term of the second sum have magnitudes whose total is less than $2.7\times 10^{-6}$. In order to demonstrate that $\frac {253}{365} > \ln 2$ it is therefore sufficient to establish that the quantity $X$, defined below, is positive:
$$
X=\frac {253} { 365} +\sum_{k=1}^{9} \frac {1} {(-3)^k k}
+\sum_{k=1}^{15} \frac {1} {(-2)^k k}.
$$ 
Tedious arithmetic could be used to deduce that
$X=\frac{1649344091}{1060426770923520}$ which is indeed positive. Alas, this arguably/maybe isn't an improvement on Alexis's answer in terms of cost:  my answer needs the computation of a fifteen term sum that has the same cost as a similar computation as Alexis's ... but my answer also need a nine-term sum to be computed, which his does not.
I considered using (10/7)(7/5) rather than (4/3)(3/2) to get a smaller limiting expansion factor (2/5 rather than 1/2) which would reduce the number of terms needed in the slower converging sum ... but the cost of having numerators that are no longer unit would probably be too high.
I rate Alexis's answer therefore as better than this one, at time of posting.
Nonetheless, I would comment that the reason both my answer and Alexis's are bad is that we both target the $\ln 2$ comparison with  $\frac {253}{365}$, which is a close run inequality (only just true), and so needs lots of precision and hence cost.  I still feel that a clever approach that attacks $\frac{365!}{342!365^{23}} < \frac 1 2$ directly could be much faster/better, since there is a lot more `slop' in that inequality.  It only needs order "per-cent" precision instead of "per-million".
== Note added later ==
I realise I could improve the above by using $\ln 2 = \ln\left(1+\frac 1 8\right) + 2 \ln\left(1+\frac 1 3\right)$ which would lead to the analogue of the quantity $X$ in my answer being instead $Y$ defined as:
$$
Y=\frac {253} { 365} +\sum_{k=1}^{5} \frac {1} {(-8)^k k}
+2 \sum_{k=1}^{10} \frac {1} {(-3)^k k}=\frac{55119469}{14831143649280}>0
$$
since this approximates $\frac {253}{365}-\ln 2$ to an accuracy bounded by $\frac 1 {6\times 8^6}+2 \frac 1 {11\times 3^{11}}\approx 1.7\times10^{-6}$ which is sufficient for this problem.
