8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you only want to prove $\frac{253}{365}>\ln(2)$ by hand, this should not be too difficult. Do you want to generalize this problem ? $\endgroup$ – Peter Nov 30 '17 at 10:42
  • $\begingroup$ I'm most interested in elegant demonstrations of the primary inequality $\frac{365!}{364! 365^{23}}<\frac 1 2$. The LHS of that is around 0.493, and is much further from 0.5 than exp(-253/365) which is 0.499998. I suspect therefore that there should be better solutions to the primary problem than the alternative log-based one I proposed. But I could be wrong in that assumption. $\endgroup$ – KesterKester Nov 30 '17 at 10:48
  • 1
    $\begingroup$ But, for the avoidance of doubt, if there is a really short/neat pen-and-paper proof that $\frac {253}{365} > \ln 2$ (I've thus far failed to generate one) that would certainly be a valid answer to this question. $\endgroup$ – KesterKester Nov 30 '17 at 11:43
  • 1
    $\begingroup$ @dbx : Indeed the full long division is not needed if the big fraction can be proved to be less than 1/2 ... if dividing, only the first ~3 decimal places of the division would be needed. You say "... is easy to see [that the big fraction is less than 1/2] directly from what you wrote." It's not obvious to me (without using a calculator) why $\frac{365\cdot 364 \cdot 363 \cdot \dots \cdot 343 } {365\cdot 365 \cdot 365 \cdot \dots \cdot 365}$ is less than 1/2 ... but if you think that it is, then please provide an illustration of why. It would answer my question! :) $\endgroup$ – KesterKester Nov 30 '17 at 14:16
  • 1
    $\begingroup$ Nope you're right, I have a bad habit of commenting too quickly on my phone! Sorry! $\endgroup$ – dbx Nov 30 '17 at 17:45
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for this. Am not 100% sure of the etiquette for when/whether I should click "accept" (by all means advise me!). My inclination would be to accept this if no-one else finds something better in, say, the next week. I hesitate because this answer, though valid and better than direct calculation of $\frac{365\cdot 364 \cdot 363 \cdot \dots \cdot 343 } {365\cdot 365 \cdot 365 \cdot \dots \cdot 365}$, still needs 15 products (n*2^n terms), then one one messy "putting over a common denominator" to get the $31972079/46126080$ fraction. It's good, but is it the "most efficient" ? $\endgroup$ – KesterKester Nov 30 '17 at 22:39
  • $\begingroup$ @KesterLester Don't worry about accepting it. It would be quite painful doing that by hand. It's probably an improvement, but still not very elegant. $\endgroup$ – Alexis Olson Nov 30 '17 at 22:58
  • $\begingroup$ I have decided to accept this answer since the thread has now gone quiet, and is unlikely to get more responses in future. In some ways I'd prefer to accept my own difference-of-two-squares approach below -- since it directly targets the initial question, not the ln(2) based idea -- but it doesn't seem right to accept my own answer, so I'll instead recognise the validity of the best remaining (and only fully rigorous) answer supplied. $\endgroup$ – KesterKester Dec 4 '17 at 15:02
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Alternatively one could prove that $\left(\frac{354}{365}\right)^{23}<\frac 1 2$ by proving that $\left(\frac{365}{354}\right)^{23}>2$. This can itself be shown from the first four terms of its binomial expansion: $$\left(1+\frac{11}{354}\right)^{23}>1+ {{23} \choose {1}} \left(\frac{11}{354}\right) + {{23} \choose {2}} \left(\frac{11}{354}\right)^2 + {{23} \choose {3}} \left(\frac{11}{354}\right)^3=\frac{89261015}{44361864}\approx 2.012>2. $$ $\endgroup$ – KesterKester Dec 1 '17 at 2:56
  • $\begingroup$ Presumably proving $\left(\frac{354}{365}\right)^{23}<\frac 1 2$ could also be done by proving that $\frac{354}{365}<\left(1- \frac 1 2\right)^{\frac 1 {23}}$ which might be easier still, since the expansion parameter in the binomial theorem would be $\frac 1 2$ rather than $\frac {11}{354}$ and so easier to work with, even if slower to converge. $\endgroup$ – KesterKester Dec 1 '17 at 13:16
0
$\begingroup$

[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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.