No calculators allowed

Posted on October 7, 2012 by spiros

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{50\pi}}$ , 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{2\pi 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}\cdots\frac{100}{101}$ , implies that:

$A\cdot 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}{4\cdot 101},$ since then $A^2 < \frac{1}{101}\cdot \frac{4\cdot 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}{1\cdot 3})(\frac{4^2}{3\cdot 5})(\frac{6^2}{5\cdot 7})\cdots(\frac{100^2}{99\cdot 101}) = \frac{4}{3} (1+\frac{1}{3\cdot 5})(1+\frac{1}{5\cdot 7}) \cdots (1+\frac{1}{99\cdot 101})$

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

At this point, it was noted that: $\frac{1}{3\cdot 5}+\frac{1}{5\cdot 7} +\cdots +\frac{1}{99\cdot 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}{3\cdot 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}{4\cdot 101}$ , then we are done!

But, $\frac{4}{3} (1+\frac{49}{3\cdot101}) > \frac{25^2}{4\cdot 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.

33 thoughts on “No calculators allowed”

Anthony on October 8, 2012 at 5:30 am said:

Let’s call A and B the following products:
A = 1/2 . 3/4 … 99/100 (the one we want to estimate)
B = 2/3 . 4/5 … 100/101

By looking intensely at the expression of AB, one can convince himself (herself) that AB=1/101.

Since A and B are close to each other, it already tells us that A should not be too far from the square-root of 1/101, ie 1/10.

To get a better estimate, one should look at B/A:
B/A = 4/3 . 16/15 . 36/35… 100^2/(100^2-1) >= 4/3 . 16/15 . 36/35= 2304/1575.

Now, one can write
1/101 = AB = A^2 B/A > 2304/1575 A^2
that is, A^2 < 1575/(101*2304) = 1575/232704.

On the other hand, 1/12^2 = 1/144 = 1575/226800, which proves that A < 1/12.

Reply ↓
- spiros on October 8, 2012 at 9:26 am said:
  
  Dear Anthony, I am very impressed. I thought that it would take at least a day before someone figured out The God Challenge (the name was inspired by the equally important challenge of finding The God Particle…) Your answer came within 6 hours of this post’s appearance and is both short and elegant, yet it seems that you have a competitor in elegance and precision (see Alex’s answer a few comments below). Since you came up with the answer first, I am inclined to give you the full amount, though I find Alex’s answer more elegant (which I thought impossible after reading your answer first). Still, I have a feeling that neither of you is doing this for the money, so I am challenging both of you to a duel: The most elegant answer to the same question, but with 1/12 replaced by 2/25. At that level of precision, you will be challenging Stirling himself. I hope you accept. Either way, I plan to deposit the lion’s share to your bank account.
  The current record for precision is Alex’s 0.0820312 and your current answer is 0.0822694. Who will cross the 0.08 barrier first? Maybe a new contender?
  
  Reply ↓
  - Anthony on October 8, 2012 at 10:19 am said:
    
    Applying the same technique as above, one can indeed reach 2/25 but for this, one should consider the first 16 terms of the development of B/A. I guess this is not very elegant nor short anymore 😉
    And I really didn’t do it for the money. Please keep it for a future riddle!
    
    Reply ↓
    - spiros on October 8, 2012 at 10:21 am said:
      
      A gentleman and a scholar.
      
      Reply ↓
Alex Ridgway on October 8, 2012 at 7:42 am said:

Hi Spiros:

My answer is similar to the previous, except that I’ll declare mine more elegant due to having the largest integers be smaller… 🙂

Problem (1): show that x = (1/2)*(3/4)*(5/6)*(7/8)*…(99/100) < 1/10

Solution: let y = (2/3)*(4/5)*(6/7)*…*(100/101). Note that each factor of y is greater than the corresponding factor of x, so x < y, and therefore x*x < x*y. Rearranging factors a bit,
then cancelling, x*y = (1/2)*(2/3)*(3/4)*(4/5)*…(99/100)*(100/101) = 1/101 < 1/100. so x^2 < xy = 1/101 < 1/100, so x = sqrt(x^2) < sqrt(1/100) = 1/10: x (x’)^2; (x’)^2 < x'y' = 9/101 < 9/100, so x' < 3/10. So x = (35/128)*x' 21/256 > x, so x < 1/12.

Say hi to John Preskill for me… He was my dissertation advisor…

Reply ↓
- Alex Ridgway on October 8, 2012 at 7:50 am said:
  
  Hmmm, my comment was mangled.. Trying again.
  
  Problem (1): show that x = (1/2)*(3/4)*(5/6)*(7/8)*…(99/100) < 1/10
  
  Solution: let y = (2/3)*(4/5)*(6/7)*…*(100/101). Note that each factor of y is greater than the corresponding factor of x, so x < y, and therefore x*x < x*y. Rearranging factors a bit,
  then cancelling, x*y = (1/2)*(2/3)*(3/4)*(4/5)*…(99/100)*(100/101) = 1/101 < 1/100. so x^2 < xy = 1/101 < 1/100, so x = sqrt(x^2) < sqrt(1/100) = 1/10: x (x’)^2; (x’)^2 < x'y' = 9/101 < 9/100, so x' < 3/10. So x = (35/128)*x' 21/256 > x, so x < 1/12.
  
  Reply ↓
- Alex Ridgway on October 8, 2012 at 8:03 am said:
  
  OK, this is the last time I’d doing this — putting html stuff in for “greater than” and “less than”:
  
  Problem (1): show that x = (1/2)*(3/4)*(5/6)*(7/8)*…(99/100) < 1/10
  
  Solution: let y = (2/3)*(4/5)*(6/7)*…*(100/101). Note that each factor of y is greater than the corresponding factor of x, so x < y, and therefore x*x < x*y. Rearranging factors a bit,
  then cancelling, x*y = (1/2)*(2/3)*(3/4)*(4/5)*…(99/100)*(100/101) = 1/101 < 1/100. so x^2 < xy = 1/101 < 1/100, so x = sqrt(x^2) < sqrt(1/100) = 1/10: x < 1/10.
  
  Now, let’s improve this. There seems to be a tradeoff between how much multiplication one does and the accuracy of the approximation. To me it seems natural to take the first four terms out, so that we have 9 in the numerator of the remaining product, making the square root easy:
  
  x = (1/2)*(3/4)*(5/6)*(7/8)*(9/10)*…*(99/100) = (1/2)*(3/4)*(5/6)*(7/8)*x’=(35/128)*x’, where x’=(9/10)*(11/12)*…*(99/100). Use the same trick as before, except with x’: let y’=(10/11)*(12/13)*…*(100/101);
  then x’y’ = 9/101 > (x’)^2; (x’)^2 < x’y’ = 9/101 < 9/100, so x’ < 3/10. So x = (35/128)*x’ < (35/128)*(3/10) = 21/256. Note that 21*12 = 252, so (1/12) = 21/252 > 21/256 > x, so x < 1/12.
  
  Reply ↓
  - spiros on October 8, 2012 at 9:30 am said:
    
    Dear Alex, thank you for your answer. You are the current record holder for precision and elegance! But since Anthony posted his answer first (though he may be from Europe, where the time-difference may have played a small role, your answer built upon his) I am challenging both of you to a duel. See the details above, in my response to Anthony. Good luck! I am sure John will be watching this duel with palpable excitement.
    
    Reply ↓
Greg Kuperberg on October 8, 2012 at 11:07 am said:

Anthony’s trick can be repeated. The problem asks to bound the product from n=1 to 50 of (2n-1)/2n. Call this A_1. Let B_1 be the product of (2n)/(2n+1). Then A_1 < B_1, and A_1B_1 = 1/101.

Let

A_2 = A_1/B_1 = product of (2n+1)(2n-1)/(2n)^2 = (3/4)(15/16)…,

so that A_1^2 = A_2/101. Let

B_2 = product of (2n+2)(2n)/(2n+1)^2 = (8/9)(24/25)…,

so that A_2^2 < A_2B_2 = 51/101. Let

A_3 = A_2/B_2 = product of (2n+1)^3(2n-1)/(2n)^3/(2n+2) = (27/32)(125/128)…

Then A_3 < (27/32)(375/384) and

A_1^4 = 51 A_3/101^3 < 51⋅27⋅125/4096/101^3

and with some arithmetic with fractions one can check that the right side is less than (2/25)^4. (Also, the simpler relation A_1^4 < 51/101^3 already shows that A_1 < 1/11 and almost gets you to 1/12 by itself.)

In fact the idea can be repeated indefinitely. You can define A_k and B_k for any k and get more and more precise product expressions for (2m choose m)/4^m for large m.

Reply ↓
- Greg Kuperberg on October 8, 2012 at 11:16 am said:
  
  Not to mention that A_3 < 27/32 yields well better than A_1 < 1/12.
  
  Reply ↓
Luboš Motl on October 8, 2012 at 11:09 am said:

The inverted and squared God challenge inequality, divided by 101, is equivalent to

2^2/(1*3) * 4^2/(3*5) * 6^2/(5*7) * … * 100^2/(99*101) is greater than 144/101. I just split the squared odd numbers to the neighbors. Now, the left hand side is 4/3 * 16/15 * 36/35 * …, composed of factors exceeding 1 (but increasingly close to it). The first three are already enough to surpass God’s challenge as the next paragraph shows.

The product of the first two factors is already 4/3 * 16/15 which is greater than 4/3 * 17/16 = 17/12. This 17/12 multiplied by the third factor 36/35 is 51/35 = 153/105, and that’s still greater than 144/101 because from 144/101 to 153/105, the numerator jumps by 9/144 and the denominator jumps by 4/101. The former is clearly a greater relative increase, above 5% (actually over 6%), than the latter, below 5% (below 4%), so the inequality is proved.

My proof hasn’t used a greater integer than 153 so based on Alex’s criteria, my proof is more elegant than Alex’s proof with huge numbers such as 252 and 256. 😉

Reply ↓
- Lubos Motl on October 8, 2012 at 12:15 pm said:
  
  I noticed that Spiros also announced a Supergod challenge, to get below 0.08=2/25.
  
  Well, it’s just a modification and extension of my previous comment above, with some clever extra tricks. But if the proof below qualifies as the winner, I am actually a Gentleman who needs those $300 to fill some recent and ongoing excessive expenses related to health problems etc.
  
  The inverted and squared Supergod challenge inequality divided by 101 is
  
  2^2/(1*3) * 4^2/(3*5) * 6^2/(5*7) * … * 100^2/(99*101) is greater than 625/404. Sorry I need a huge number 625 from 25^2 and 404 from 2^2 * 101.
  
  It’s tight but the proof is straightforward. The left hand side is 4/3 * 16/15 * 36/35 * 64/63 * …. 10000/9999. Is it greater than 625/404? You bet. Just a little bit but it is greater.
  
  I only need to count the first factor, 4/3, as a full-fledged multiplicative factor. However, it is enough to treat the remaining factors from 16/15 to 10000/9999 using a “linearized” sub-estimate. What do I mean? I use another self-evident inequality
  
  16/15 * 36/35 * 64/63 * … * 10000/9999 is greater than 1 + 1/15 + 1/35 + 1/63 + … 1/9999.
  
  Why is this true? Just write 16/15 as (1+1/15) and similarly for the other factors on the left hand side, expand the product using the distributive law, and only pick the absolute and linear pieces in the “small perturbations” such as 1/15 up to 1/9999 i.e. ignore the second-order and higher-order terms in the “perturbations” of the terms 1.
  
  So I will reduce the left hand side if I write it as
  
  4/3 * ( 1 + 1/15 + 1/35 + 1/63 + … + 1/9999)
  
  However, even this reduced left hand side is still enough to beat the right hand side of the original preprocessed Supergod inequality, 625/404, by a tiny edge. To see that, we actually need to compute the sum 1/15+1/35+1/63+…+1/9999. Again, just to be sure, the denominators here are (4n^2-1) numbers for “n” between 2 and 50.
  
  However, it’s actually easy to analytically continue this sum of 49 terms (I am not including the term “1” among them in this discussion). Start with the first two terms:
  1/3*5 + 1/5*7 = 1/5 ( 1/3 + 1/7 ) = 1/5 * 2*5 / (3*7) = 2 / (3*7)
  
  Now, when you add 1/(7*9), you will get
  1/7 * (2/3 + 1/9) = 1/7 * 7/9 = 1/9.
  
  Now add 1/(9*11) to get
  1/9 (1 + 1/11) = 4 / (3 * 11)
  
  Now add 1/(11*13) to get
  1/11 ( 12 / 9 + 1 / 13 ) = 5 / (3 * 13)
  
  This should be enough to see the pattern and prove it by mathematical induction. When you sum the first K terms among my 49 terms, the sum is equal to K / (3*(2K+3)). All this extra complication with the numbers “3” is just due to my decision to explicitly remove the first natural term, 4/3, that I have to treat properly multiplicatively to get a sufficiently large lower bound on the left hand side.
  
  The proof by the mathematical induction is simple. For K=1, K/(3*(2K+3)) gives 1/15 indeed. And the difference of K/(3*(2K+3)) and (K – 1)/(3*(2 (K – 1) + 3)) is indeed 1 / ( (2K+2)^2 – 1 ), which is indeed the new term we are adding.
  
  To summarize, the sum
  
  1 / 15 + 1 / 35 + 1 / 63 + … + 1 / 9999 = 49 / 303, exactly!
  
  So what I need to prove is
  
  4/3 * (1 + 49/303) is greater than 625/404. Be sure I could do exercises to prove it without using numbers greater than 625. 😉 But let me take the shortcut and just compute, on top of my head, what are the fractions.
  
  4/3 * (1 + 49/303) = 4/3 * 352/303 = 1408/909. Now, the problem is to compare 1408/909 and 625/404. That’s the same comparison as 1408/9 and 625/4 because 101 appeared on both sides. In other words (inverted language again), I need to prove that 9/1408 is smaller than (0.08)^2 = 0.0064 again. That’s because I have really proved that the left hand side of the “truly original” product squared is smaller than 9/1408.
  
  That’s a subtle comparison without the calculator but we know how to compute such things even without a calculator. Let me tell you in advance that 9/1408 = 0.006392…; this sentence is not an official part of my solution.
  
  Well, I can prove 9/1408 is smaller than 0.0064 simply by proving that 1408*0.0064 is greater than 9. Here, 0.006*1408 = 8.448 (yes, I can multiply in my head) and 0.0004*1408 = 0.5632 (yes, we can). The sum of them is 8.448+0.5632 = 9.0112 which is indeed greater than 9. 😉 So 9/1408 is smaller than (0.08)^2 which proves the original Supergod challenge.
  
  If you were serious about the donation, my PayPal green piglet button is at the bottom of http://motls.blogspot.cz/?m=1
  
  Cheers
  LM
  
  Reply ↓
  - Greg Kuperberg on October 8, 2012 at 12:52 pm said:
    
    To compress this explanation: First,
    
    16/15 * 36/35 * … * 10000/9999 > 1 + 1/15 + 1/35 + … + 1/9999
    
    by repeated use of the inequality (1+a)(1+b) > 1+a+b when a and b are positive. Second,
    
    1/15 + 1/35 + … + 1/9999 = 1/6 – 1/202 = 49/303
    
    because the sum telescopes:
    
    2/15 + 2/35 + … + 2/9999 = (1/3-1/5) + (1/5-1/7) + … + (1/99-1/101)
    
    So one indeed obtains, in my notation,
    
    1/A_2 > 4/3 * 352/303 = 1408/909
    
    We know that A_1^2 = A_2/101, so we are left to establish the second inequality in
    
    A_2/101 < 9/1408 5625.
    
    The arithmetic is simpler than in my answer, but I wanted to make the point that there is an elementary way (using only telescoping products) to get faster and faster convergence.
    
    Reply ↓
    - Lubos Motl on October 8, 2012 at 1:01 pm said:
      
      Thanks for the compression, Greg, but if you are claiming that you have a method to prove the inequality with 0.08 using a systematic algorithm without a calculator, and it somewhat looks like you are claiming so, could you please show us how your method achieves this goal. instead of compressing other people’s algorithms? Thanks; I am really interested whether it’s usable.
      
      Reply ↓
      - Greg Kuperberg on October 8, 2012 at 1:22 pm said:
        
        That’s slightly more than what I am claiming. I am claiming in my other post that there is an algorithm, justified only by telescoping products, to get better and better inequalities. Whether it is really “without a calculator” is a judgment call. I allow myself pen and paper.
        
        To change notation slightly, for any positive integer m, we want a good upper bound for
        
        A(1,1) = \prod_{n=0}^{m-1} (2n+1)/(2n+2) = 1/2 * 3/4 * … * (2m-1)/(2m).
        
        Let
        
        A(1,j) = \prod_{n=0}^{m-1} (2n+j)/(2n+j+1),
        
        and recursively define
        
        A(k+1,j) = A(k,j)/A(k,j+1).
        
        Then T(k,j) = A(k,j)A(k,j+1) always telescopes and can be evaluated easily, and we also have
        
        A(k,j)^2 = T(k,j)A(k+1,j) and A(k,j) < 1
        
        for all positive k and j. Moreover we can always bound A(k,j) by its leading factors. (At least I think that this works; I am not checking everything carefully beyond A(3,j).)
        
        Reply ↓
        
        Lubos Motl on October 9, 2012 at 1:51 am said:
        
        Very interesting, Greg. Such tricks, if you could do them right, could perhaps lead to new ways to organize various perturbative expansions in quantum field theory etc., perhaps in a better converging way for larger couplings. I don’t know exactly which one and how but it “sounds so”. 😉
    - Greg Kuperberg on October 8, 2012 at 1:27 pm said:
      
      Also unfortunately WordPress mangled some of my reply at 12:52 pacific time, because it interpreted some of the inequality symbols as defining an HTML tag. And I can’t fix now.
      
      Reply ↓
  - spiros on October 8, 2012 at 3:41 pm said:
    
    Dear Lubos, your response is certainly worthy of the prize. Still, this has been an amazing collaborative process thus far (Anthony started it, Alex took it to the next level, you and Greg gave the best solutions to the Supergod challenge – I like your name of it – and Greg even reduced your inductive argument on the sum 1/15+1/35+1/63+…+1/9999 = 49/303 into a simple telescopic sum). I want to congratulate all of you for rising up to the challenge and finding brilliant ways to reach that kind of precision with very simple elementary math! I only have to add something myself to your proof that I think would make it even more elegant (though slightly): When comparing (4/3)*(352/303) to 25^2/404, you only need to show that 18.75^2 is less than 352, since $(4/3)*(352/303) > 25^2/404 \Leftrightarrow (4/3)*(352/3) > 25^2/4 \Leftrightarrow 4^2 \cdot 352 > 75^2 \Leftrightarrow 352 > 18.75^2$ . But $(18+3/4)^2 = 18^2+2\cdot18\cdot (3/4) + 9/16 = 324+27+9/16 < 352.$ Having said all that about collaboration, etc., and because your blog at http://motls.blogspot.com/ is a very valuable resource to the scientific community (we may have differing political views, but who cares about that) I will make a donation to your Paypal account. Thank you for sharing your knowledge with others and I hope you have a speedy recovery. As for the original $300, I will take Anthony’s advice and save it for a future challenge (maybe in $50 chunks, to be closer to Erdos’s practice of giving small sums for elegant solutions, after adjusting for inflation).
    
    Reply ↓
    - Lubos Motl on October 8, 2012 at 10:27 pm said:
      
      Thanks a lot for your generous bounty and thanks to everyone else who contributed to it – and to the fun of mathematical methods over here.
      
      I just checked in the morning that using the other method, i.e. by neglecting the factors beyond some of the first ones and setting them to one, one would have to go very very far, indeed. After all, the original ratio differs from 0.08 just by 0.516 percent, so even 400/399 * 324/323 = 1.00561 is needed. By ignoring both of these factors, we would already fail to get to 0.08. So one has to multiply the ratios at least through 324.323. Well, a more precise calculation shows that at least 16 factors would be needed, from 4/3 to 1024/1023. 😉
      
      It’s clear that one has to incorporate the “bulk of the factors”, despite their being close to one, in a collective way, and I chose the “telescopic sum (from product)” formula, thanks for the terminology, Greg and Spiros. A further improvement would be done by calculating a greater number of factors as the honest product and the rest as the telescopic sum.
      
      Using some calculators now, the original product is 0.0795892. Inverting, squaring, and dividing by 101 gives 1.56304. That’s the ultimate goal. The supergod threshold is 625/404 = 1.54703. My solution with 4/3 taken multiplicatively and the rest telescopically gives 1.54895, slightly above the supergod threshold, but still well below the exact value 1.56304. Adding 16/15 to the multiplicative method and the rest to the telescopic treatment would give 1.5574. Adding 36/35 as well gets us to 1.56011 and we would converge if we were moving more factors to the product…
      
      One could actually speed up the convergence by adding a telescopic-like formula for the second-order (and perhaps higher order) products as well…
      
      Reply ↓
Pingback: Ένα ωραίο μαθηματικό πρόβλημα « physicsgg
George Siopsis on October 9, 2012 at 7:14 am said:

Here is my response to the Grand Challenge:

THEOREM: Let x = a[1]*…*a[50], where a[n]=(2n-1)/(2n). Then x^2 < 1/b[k], where b[1]=101, b[2]=151, b[3]=1408/9, b[4]=35392/225, …

PROOF: Let A[n] = a*n+1. Then for 2<= a < 4, and for sufficiently large n, a[n]^2 < A[n-1]/A[n]. Choosing a so that this inequality turns into an equality for n=k, we obtain b[k] rather straightforwardly (and increasingly inelegantly as k increases).

For k=1,2,3,4,…, we have a=2,3,7/2,11/3,…, respectively.

COMMENT:The numbers b[k] approach 50*Pi.

Reply ↓
- Lubos Motl on October 9, 2012 at 7:40 am said:
  
  Dear George, it’s very nice but your comment about “straightforward but increasingly inelegant” calculation of b[k] reminds me of Fermat’s note that “unfortunately there’s not enough room in this margin for me to write the wonderful proof here”.
  
  Even more seriously, 1/sqrt(50.pi) isn’t the exact value of the product. The exact value is 0.0795892 while 1/sqrt(50.pi) is 0.0797885. So even if you calculate b[100,000], you will still have a 0.25% error in your estimate of the product! So depending on which inequality you want to prove (greater or smaller), you will either offer a wrong proof or a proof in the right direction that becomes too weak if the required precision is 0.25% or better. And note that already in the Supergod challenge, the required accuracy was about 0.5%, so your error doesn’t really allow you to get further.
  
  Reply ↓
  - George Siopsis on October 9, 2012 at 7:50 am said:
    
    Lubos, nice to talk to you again. I am tempting not to respond hoping to become famous, like Fermat. But since the chance of this happening is less than 0.25%, here is my response: k<50. If you want a better approximation to Pi, you need to go beyond N=50, by increasing N, and considering a[1]*…*a[N], instead.
    
    Reply ↓
    - Lubos Motl on October 12, 2012 at 10:38 pm said:
      
      Dear George, good to be interacting with you in a new, unusual setup. 😉 I understand your text. It just seems to me that the challenge was to calculate/estimate the product ratio up to 99-100, not pi. It’s a different task. There are many ways to calculate pi – or, equivalently, the ratio 1*3*5*…*(2n-1) / 2*4*6*…*2n, times sqrt(n), squared, inverted and so on, that are more effective.
      
      Reply ↓
Ludek on October 11, 2012 at 1:54 am said:

Before starting to solve it with prime factors, canceling and compute it exactly, one question: Is it allowed to cancel most of the numbers in nominator and denominator (of course by an algorithm)? And is it allowed to multiply the handful residual primes and make the division on peace of paper with pencil ? 🙂 L.

Reply ↓
- spiros on October 11, 2012 at 7:32 am said:
  
  I am intrigued. If the algorithm is elegant and elementary in nature, it would be great to see it at work. The current solution would work well even if we increased the number of fractions to 100, or 1000, from just 50. If your solution is scalable like that, it would be fantastic.
  
  Reply ↓
- Lubos Motl on October 11, 2012 at 8:19 am said:
  
  Dear Luďku, you will have a hard job. You could rather easily find out that the product of the odd numbers over the product of the even numbers may be cancelled to:
  
  {{3, 4}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {29, 1}, {31, 1}, {53,
  1}, {59, 1}, {61, 1}, {67, 1}, {71, 1}, {73, 1}, {79, 1}, {83,
  1}, {89, 1}, {97, 1}}
  
  divided by 2^97. Yes, what’s left in the denominator is just a power of two, the ninety-seventh one, because up to the powers of two, the product 2*4*…*50 is of course just the product 1*2*3*…*25. The odd numbers 1…25 cancel directly against some of the numerator while the even ones 2…24 reduced to 1…12 cancel against some other free factors in the numerator.
  
  But you effectively need to calculate 2^97 with a 0.5% error accuracy to solve the Supergod challenge. I predict that with a paper and pencil, you will give it up. Wanna take a bet? 😉 Note that no single power of the odd number may be approximated by a nearby integer, either, because even the change from 97 to 98 would always be more than a 0.5% error.
  
  Cheers
  LM
  
  Reply ↓
Steve on October 12, 2012 at 10:13 pm said:

Hi, it took me about 5 hours to stumble upon the two line proof. It goes like this, taking a few more lines of clumsy English.
Solution to P1
Take the first inequality and multiply both sides by 100. The RHS is 10. The LHS can be regrouped into 49 terms starting with 3/2 and ending with 99/98. Now multiply the inequality to be proved with this new one. The RHS is 1. Notice that the product on the LHS is (1X3/2X2)…{(((n)squared)-1)/n squared}…(97X99/98X98)X99/100 and every bracketed term is strictly less than 1. QED.

The solution to Problem 2 follows rather quickly: Start with the inequality to problem 1 and multiply both sides by 10/11. Obviously the LHS is the product of fifty terms less than 1/10 (<1/10) and 10/11. That means the LHS is (<1/11), and the inequality can be compactly represented as, (50 terms<1/11) < 1/11. Call this inequality A. Next, take the same 49 term rearrangement from above, where problem 1 was multiplied by 100; i.e., the RHS is 10. The LHS is 49 terms starting with 3/2 and ending with 99/98, as before. Now add 1 to both sides of the inequality. This new inequality looks like (49 terms) + 1 < 11. Call it inequality B. The penultimate step is to multiply the LHSs and multiply the RHSs. The inequality is preserved. The RHS of the product is now 1. The LHS looks like (10/11)X(50 terms<1/11)X[(49 terms) + 1], which expands to (10/11)X(50 terms<1/11)X(49 terms) + (10/11)X(50 terms<1/11). Now we have just proved in problem 1 that (50 terms)X(49 terms) is less than 1/10, so the LHS is strictly less than 1. QED.

I'll look at the god like problems later.

Reply ↓
- Steve on October 12, 2012 at 10:26 pm said:
  
  Sorry, the last line should read,
  
  Now we have just proved in problem 1 that (50 terms)X(49 terms) is less than 1, so the LHS is strictly less than 1, i.e., (<1)X10/11 + (<1/10)X 10/11. QED.
  
  Reply ↓
  - Steve on October 12, 2012 at 11:53 pm said:
    
    Sorry, but I used the same above reasoning to prove the relation works for 1/13, which is false, so there is an error in my reasoning. Oh well, another way to get at problem 1 is to square both sides of the inequality, then cyclicly shift one set of numerators to the right, so that the first term of this square on the LHS looks like (1/2)X(3/2), the second to last looks like 97X99/98×98, and the last term is 1X99/100X100. The RHS is 1/100. Now, since the first 49 terms are of the form [(n squared -1)/ n squared], they are all less than 1. The last term, 99/100X100 is less than 1/100, so that means the whole LHS is less than 1/100.
    
    Solution to problem 2. Using the same square we now want to prove it is less than 1/121. To do so, note that there is a LHS term in the middle that is 9X11/100 and the end terms are 1X3/4, and 99/100×100. Since all other LHS terms are less than 1, all we need to do is prove (99/100)X(99/10000)X(3/4) is less than 1/11X11. This is obviously true, since multiplying (99/100)X(99/10000)X(3/4) by 121 is 0.99X0.99X(363/400). Elegant enough?
    
    Reply ↓
    - Steve on October 13, 2012 at 12:18 am said:
      
      The god problem is similar. In this case, the square on the RHS is 1/144. If we multiply both sides by 144 there is a factor of the LHS 11X13/144 that cancels and we are left with 143. Now, (0.99)X(0.99)X (3X143/400) is not less than 1 but it is nearly so. It’s a bit less than 421/400. So all we have to do is to multiply one more factor at the left end, 3X5/16. 3x5X421/(16X400)=1263/1280. So it’s not as elegant, but it does not involve many calculations at all.
      
      Supergod problem. Still thinking.
      
      Reply ↓
      - Lubos Motl on October 13, 2012 at 5:26 am said:
        
        Dear Steve, I read and tried to understand your comments. .
        
        The first one is an obvious nonsense because you *assumed* the inequality you wanted to prove (rewritten in a different form but that changes nothing about the logic), and you used it to deduce the same inequality. It’s a circular reasoning proving nothing when the logic is fixed.
        
        I think that in your last comment, you are getting to a proof of the God problem that was written above by others, like me, although your wording may be too concise to understand and verify it’s indeed the case.
        
        Reply ↓
Lubos Motl on October 13, 2012 at 11:34 pm said:

Brian Valentine has a completely new approach to the problem at my blog:

http://motls.blogspot.cz/2012/10/supergod-challenge-proving-300.html?m=1#comment-681599194

He takes the logarithm, approximates the logarithms by a nice difference of square roots, uses one more inequality trick for these square roots, and gets extremely close to the right numbers in this way.

Reply ↓