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.
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: .
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 . We got a fantastic approximation to the product, , which is really close to (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 bound. But, even if we had memorized the proof behind Stirling’s beautiful formula for the product of the first consecutive numbers: , 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 .
You could multiply the numbers together until you get below the 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 .
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
Solution [G. Kuperberg, A. Leverrier, L. Motl, and A. Ridgway]: The initial idea was to turn the problem upside down…
Let and It is easy to see that , noting that . Since each term in is less than the corresponding term in , it follows that . But, we won’t even use that fact for the Supergod Challenge. Instead, we will take the following path: Telescoping cancellation in the product , implies that:
To prove that , it remains to show that since then The next idea was to lower-bound by using repeatedly the simple inequality for :
At this point, it was noted that:
A simple telescoping (sum) argument does the trick! We are in the final stretch. If we can show that , then we are done!
But, Keeping things as simple as possible, we evaluate using the formula , to get:
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 for any natural number (in our case which Stirling’s formula approximates as 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.