The Supergod challenge is the following problem: (use the minimalistic mobile template)
Using no calculators and no "uncertain" assumptions about inequalities, prove that\[We will soon switch to methods that (many?) Russian middle-schoolers are claimed to have mastered, but before we do so, let's try to solve it using the "powerful tools" one expects among professional physicists or mathematicians.
\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdot\frac{7}{8}\cdot \cdots \cdot \frac{99}{100} \lt 0.08.
\] The increasingly difficult problems "1", "2", and "God challenge" had \(1/10\), \(1/11\), and \(1/12\) on the right hand side. Each new task was almost 10% harder than the previous one. The improvement from God challenge to Supergod challenge was just 4% or so but this step was arguably the most technically challenging because, as the people who are allowed to use calculators know, the left hand side equals 0.0795892, just 0.5% away from the Supergod challenge!
If you feel technically strong, try to solve the Megagod challenge whose right hand side is 0.0796. ;-)
What are these methods? Well, the left hand side may also be written with many extra factors of \(2\) that cancel:\[
\frac{1/2}{2/2}\cdot\frac{3/2}{4/2}\cdot\frac{5/2}{6/2}\cdot\frac{7/2}{8/2}\cdot \cdots \cdot \frac{99/2}{100/2}
\] You see that the "big denominator" is nothing else than \(50!\), the product of integers between \(1\) and \(50\). Similarly, if you know the Gamma function, the "big numerator" is \((49.5)!\) times \((-0.5)!\) but \((-0.5)!=\sqrt{\pi}\), exactly.
To calculate the ratio of these factorials, we would need to use Stirling's approximation for the generalized factorial (valid for large arguments)\[
n!\approx \sqrt{2\pi n} \zav { \frac{n}{e} }^n
\] This is valid in the sense that the limit of the ratio of both sides for \(n\to\infty\) goes to one. With this approximation, the left hand side of the challenge is\[
\frac{49.5! }{50!\sqrt{\pi}}\approx \frac{49.5^{50}\sqrt{e}}{50^{50.5}\sqrt{\pi}}\approx 0.0795879.
\] This is really wonderfully close to the exact result \(0.0795892\) but we couldn't quite compute it this accurately without a calculator. Moreover, we would need to remember some boring messy formulae to be sure that the error of the figure is small enough to keep us below \(1/10\), \(1/11\), \(1/12\), or \(1/12.5\), the latter is the Supergod right hand side in a different form.
A somewhat easier calculation would involve the rewriting of the approximation above as\[
\frac{49.5^{50}\sqrt{e}}{50^{50.5}\sqrt{\pi}} = \zav{\frac{49.5}{50}}^{50}\sqrt{ \frac{e}{50\pi} }
\] The first factor looks like the limiting "many years of small interest rates" formula for the exponential,\[
\lim_{N\to\infty} \zav{ 1+\frac{x}{N} }^N = \exp(x)
\] and in this way, it produces nothing else than \(\exp(-1/2)\) which cancels against the \(\sqrt{e}\) factor in the second part of the expression. So the Supergod left hand side may be approximated by \(\sqrt{1/50\pi}\approx 0.0797885\) which is still wonderfully accurate. But we probably needed a calculator or Mathematica (although the square root of \(50\pi\) is not so bad: \(50\pi\gt 50\cdot 3.14 = 157\gt 156.25=12.5^2\)) and we would need extra messy discussions (well, yes, the maximum relative error of Stirling's basic formula for \(n!\) is \(\exp(1/12n)-1\) which is about \(1/600\) in our case, and most of it actually cancels between \(49.5\) and \(50\)) to prove that the error in our approximation doesn't spoil the inequalities, especially in the case of the hardest one.
One could make the accuracy even more stunning by using a more accurate version of the Stirling's formula, e.g. one that has \(\sqrt{2\pi(n+1/6)}\) instead of just \(\sqrt{2\pi n}\). For example, the exact ratio of these improved Stirling's approximations would yield \(0.0795892\): at least six significant figures would agree and maybe more. With those improvements, the computational difficulty would become even more inhuman, however.
Tatu, 30 minutes, English version: lyrics
Going to the Russian middle school for some explosive methods
So instead, let us use elementary maths. The easier challenges up to God were kind of independently solved by Anthony Leverrier and Alex Ridgway. My method probably overlaps in the spirit but I have found mine independently so I can't tell you whether the core is quite the same. Greg Kuperberg offered clarifying comments in all the situations.
First, note that the Stirling's discussion above featured the square root of \(\pi\), among other things. This suggests it's useful to square the formula to get rid of the square roots. We will immediately see another advantage of the squaring: the two copies of the integers may be divided to individual factors in a "split way". At any rate, let's square and invert the original Supergod inequality. After we conveniently divide the formula by \(101\) as well, the original inequality is equivalent to\[
\frac{2^2}{1\cdot 3}\cdot \frac{4^2}{3\cdot 5}\cdot \frac{6^2}{5\cdot 7}\cdot \cdots \cdot \frac{100^2}{99\cdot 101}\gt \frac{1}{101}\cdot 12.5^2
\] or, using a more explicit-integer-based notation,\[
\frac{4}{3} \cdot \frac{16}{15}\cdot \frac{36}{35}\cdot \cdots\cdot \frac{10,000}{9,999}\gt \frac{625}{404}.
\] Note that the left hand side is the product of 50 factors each of which is greater than one but they approach one rather quickly. We need to collect a "sufficient number of excesses over one" from these factors to surpass \(625/404\) on the right hand side.
If we just multiply \(4/3\cdot 16/15\cdot 36/35\), we get \(256/175\approx 1.463\) which is enough to surpass the God challenge threshold \(12^2/101\approx 1.426\) but isn't enough for the Supergod challenge threshold \(625/404\approx 1.547\). To get over the Supergod threshold by picking several initial factors and replacing others by one, we would need roughly ten factors – and the integers we would generate would be too large.
Clearly, we can't afford to completely ignore almost all the factors: we must treat them and include them "collectively" in some way. It turns out that it's enough to beat Supergod if we only keep \(4/3\) as a genuine multiplicative factor and we "linearize" all other factors by the inequality\[
(1+x_2)(1+x_3)\cdot \cdots \cdot (1+x_{50}) \gt 1+(x_2+x_3+\cdots x_{50}).
\] Even with this reduction defined by the linearization – we just neglect terms of second order and higher order in the "perturbations" \(x_i\) – it will be enough to beat Supergod. In our particular case, we have\[
\eq{
x_i &= \frac{1}{4i^2-1},\\
(x_2,x_3,\dots x_{50}) &= ( \frac{1}{15},\frac{1}{35},\cdots \frac{1}{9,999} ).
}
\] A funny and clever thing is that the sum of these 49 terms \(x_i\) may actually be computed analytically, using a simple formula. Greg Kuperberg reminded me that this sum is known as the telescoping sum (one displaying the telescoping cancellation). If we had all of them, we would get\[
\frac{1}{3}+\frac{1}{15}+\cdots \frac{1}{4n^2-1} = \frac{n}{2n+1}.
\] It's that simple. You may prove this formula by the mathematical induction. For \(n=1\), both sides give \(1/3\) and you may go from \(n-1\) to \(n\) because both sides jump by the last term of the left hand side. That's the telescoping calculation: it's helpful to compute five or four partial sums to see that the result is really simple. More imaginatively, the term in the sum may be rewritten as\[
\frac{1}{4n^2-1} = \frac{1}{4n-2} - \frac{1}{4n+2}
\] and in this difference form, we see that all the terms in the sum except for the first one, \(1/2\), and the last one, \(-1/(4n+2)\), cancel against their neighbors. The sum is therefore \(+1/2-1/(4n+2)=n/(2n+1)\).
For \(n=50\) which is our case, the right hand side above is \(50/101\). But we need to subtract \(x_1=1/3\) because we need to treat the first term multiplicatively, not to lose the largest "higher-order terms", so the sum \[
x_2+\cdots +x_{50} = \frac{50}{101} - \frac{1}{3} = \frac{49}{303}.
\] Now add the term \(1\) and multiply by \(4/3\) to see that\[
\frac{4}{3} \cdot \frac{16}{15}\cdot \frac{36}{35}\cdot \cdots\cdot \frac{10,000}{9,999}\gt \frac{4}{3} \zav{ 1+\frac{49}{303} }.
\] I suppose you're able to calculate that the result, the right hand side, is \(4/3\cdot 352/303=1,408/909\). The final step of the proof requires us to demonstrate that \(1,408/909\) is still greater (despite the modest generosity with which we reduced the left hand side) than the Supergod threshold \(625/404\). After we cancel \(101\) again, we need to show that\[
\frac{1,408}{9} \gt \frac{625}{4}
\] But if we multiply both sides by the denominators, it is equivalent to\[
4\cdot 1,408 = 5,632\gt 5,625 = 625\cdot 9
\] which is indeed the case (although it was a close call). QED. You may try to solve the Megagod challenge. A few tips how to improve the accuracy are mentioned at the Quantum Frontiers blog (mine and other people's tips). However, once your method needs a calculator, you are going in a direction that has no point: after all, using a calculator, you may calculate the exact value rather quickly. ;-)
0 comments:
Post a Comment