During Friday evenings at Caltech, the Institute for Quantum Information and Matter runs a seminar series focusing on research talks geared towards a diverse audience whose common background is quantum mechanics (just that, nothing else…) But, the fun doesn’t end after the 45 minute talks are over. The seminar is followed by a mingling session on the brand new patio of East Bridge, the building where Richard Feynman delivered his famous lectures.

Grigori Perelman. Not a Russian middle-schooler anymore, but still pretty smart.

Last Friday, Aleksander Kubica (pronounced Koobitsa), a Polish graduate student in the Theory group of IQIM and a first prize winner of the 2009 European Union Contest for Young Scientists, decided to test our ingenuity by giving us a problem that Russian middle-schoolers are expected to solve. If you haven’t met any Russian middle-schoolers, well, let’s just say that you should think carefully before accepting a challenge that is geared towards their level of mathematical maturity. What was the challenge?

Problem 1: Show that: frac{1}{2}cdot frac{3}{4}cdot frac{5}{6}cdot frac{7}{8}cdot frac{9}{10}cdots frac{99}{100} < frac{1}{10}.

Four Caltech geniuses and myself spent over an hour trying to figure out the solution that a Russian middle-school student would give. Of course, the first thing we tried was using Stirling’s approximation after quickly showing that the product on the l.h.s. is equal to binom{100}{50} cdot 2^{-50}. We got a fantastic approximation to the product, frac{1}{sqrt{50pi}}, which is really close to frac{1}{12.5} (and as it turns out, really close to the actual product). That was the easy part. The hard part was proving that the error in Stirling’s approximation was small enough to keep us below the required frac{1}{10} bound. But, even if we had memorized the proof behind Stirling’s beautiful formula for the product of the first n consecutive numbers: n! sim (n/e)^n cdot sqrt{2pi n}, we still would have given a solution that was extremely complicated relative to the simplest (and most elegant) way of solving the above problem.

Can you find the two-line solution?

We could not, so Aleksander showed it to us. He barely escaped with his life… If you are a Russian middle-schooler (or, think you are smarter than one), I have a challenge for you that I can’t figure out myself.

Problem 2: Using elementary math, show that frac{1}{2}cdot frac{3}{4}cdot frac{5}{6}cdot frac{7}{8}cdot frac{9}{10}cdots frac{99}{100} < frac{1}{11}.

You could multiply the numbers together until you get below the frac{1}{11} bound and short of doing that, I doubt there is anything else you can do. But say that you are capable of somehow solving the above problem. Then, the impossible awaits you:

The God Challenge: Using elementary math, show that frac{1}{2}cdot frac{3}{4}cdot frac{5}{6}cdot frac{7}{8}cdot frac{9}{10}cdots frac{99}{100} < frac{1}{12}.

I will give $300 of my own money to the first person who solves The God Challenge without explicitly multiplying the original numbers. Good luck.

Fine print: I reserve the right to reject solutions that Paul Erdos would consider utterly inelegant.

[Update: 10 p.m., October 8th] The collective response to the God Challenge has been both brilliant and overwhelming. I will combine here the answers that have appeared in the comments so far, presenting a solution to the following super-precise version:

The Supergod Challenge: Using elementary math, show that frac{1}{2}cdot frac{3}{4}cdot frac{5}{6}cdot frac{7}{8}cdot frac{9}{10}cdots frac{99}{100} < frac{1}{12.5}

Solution [G. Kuperberg, A. Leverrier, L. Motl, and A. Ridgway]: The initial idea was to turn the problem upside down…

Let A = frac{1}{2}cdot frac{3}{4}cdot frac{5}{6}cdot frac{7}{8}cdot frac{9}{10}cdots frac{99}{100} and B = frac{2}{3}cdot frac{4}{5}cdot frac{6}{7}cdot frac{8}{9}cdot frac{10}{11}cdots frac{100}{101}. It is easy to see that A < B, noting that frac{n-1}{n} < frac{n}{n+1} Leftrightarrow (n-1)(n+1) < n^2 Leftrightarrow n^2-1 < n^2. Since each term in A is less than the corresponding term in B, it follows that A < B. But, we won’t even use that fact for the Supergod Challenge. Instead, we will take the following path: Telescoping cancellation in the product frac{1}{2}frac{2}{3}frac{3}{4}frac{4}{5}cdotsfrac{100}{101}, implies that:

Acdot B = frac{1}{101} Leftrightarrow A^2 (frac{B}{A}) = frac{1}{101} Leftrightarrow A^2 = frac{1}{101}cdot (frac{B}{A})^{-1}.

To prove that A < frac{2}{25}, it remains to show that frac{B}{A} > frac{25^2}{4cdot 101}, since then A^2 < frac{1}{101}cdot frac{4cdot 101}{25^2} = (frac{2}{25})^2. The next idea was to lower-bound frac{B}{A} by using repeatedly the simple inequality (1+a)(1+b) > 1+(a+b), for a,b > 0:

frac{B}{A} = (frac{2^2}{1cdot 3})(frac{4^2}{3cdot 5})(frac{6^2}{5cdot 7})cdots(frac{100^2}{99cdot 101}) = frac{4}{3} (1+frac{1}{3cdot 5})(1+frac{1}{5cdot 7}) cdots (1+frac{1}{99cdot 101})

implying, frac{B}{A} > frac{4}{3}(1+frac{1}{3cdot 5}+frac{1}{5cdot 7} +cdots +frac{1}{99cdot 101}).

At this point, it was noted that: frac{1}{3cdot 5}+frac{1}{5cdot 7} +cdots +frac{1}{99cdot 101} = frac{1}{2} [(frac{1}{3}-frac{1}{5})+(frac{1}{5}-frac{1}{7})+(frac{1}{7}-frac{1}{9})+cdots+(frac{1}{99}-frac{1}{101})] = frac{1}{2}(frac{1}{3}-frac{1}{101}) = frac{49}{3cdot 101}.

A simple telescoping (sum) argument does the trick! We are in the final stretch. If we can show that frac{4}{3} (1+frac{49}{3 cdot 101}) > frac{25^2}{4cdot 101}, then we are done!

But, frac{4}{3} (1+frac{49}{3cdot101}) > frac{25^2}{4cdot 101} Leftrightarrow 352 > frac{75^2}{4^2} = (18+frac{3}{4})^2. Keeping things as simple as possible, we evaluate (18+frac{3}{4})^2 using the formula (a+b)^2 = a^2+2ab+b^2, to get: (18+frac{3}{4})^2 = 324+27+frac{9}{16} < 352.

The end.

PS: There are some real gems in the comments section, like Greg Kuperberg’s recursive approximation to the product in the God Challenge given by binom{2m}{m} cdot 2^{-2m}, for any natural number m (in our case m=50), which Stirling’s formula approximates as frac{1}{sqrt{pi cdot m}}. Oh, and lest I forget, the $300 goes back into the pot for future challenges, since the initial winner, Anthony, requested this. If it was not clear by now, we do math because it delights our spirit. Of course, it helps that it also pays the bills.