## Sunday, July 15, 2012

### 53rd IMO: Problem 2

A solution was added at the end

The 53rd International Mathematical Olympiad is taking place in Mar del Plata, Argentina, the same country in which Prof Paul Frampton is still expecting to be freed. He's had a cold ten times in 2012 but already published 5 peer-reviewed papers. Check some words from Paul.

Mar del Plata

The kids have already solved the problems (a few days ago) and results will be announced today. (Update: The new results have been published. Korea incredibly won before China, U.S., Russia, Canada tied with Thailand, and Singapore. Czechia sucks at the 47th place, 3 stairs below our Slovak brothers; our best guy was again our Vietnamese Czech of Tachov, Mr Anh Dung Le, who got the only silver medal just like he did in 2011. After decades with USSR, USA, Romania, and others at the top, the dominance of East Asian mathematicians starts to be self-evident and can't be hidden even inside the Czech team.)

I was attending an international mathematical olympiad exactly 20 years ago – in Moscow – after I co-won the Czechoslovak round so it's fun to check what's shaking. By the way, I screwed one problem, was incorrectly graded another one, lost many other points for unclear reasons, so with 4 times 7 points, I only got a bronze medal.

Our team – the last federal Czechoslovak IMO team – was criticized for the 2nd-3rd tied worst result in the national history: 13th place. Unfortunately, one may check that except for 1993 when Czechia was 10th, the Czech team was much worse after the Velvet Divorce every single year, about 40th place in average.

At any rate, if you know these contests, there are 6 problems and you get 0-7 points for each of them. At the international level, they're divided to 2 days per 3 problems and everyone has 4 hours and 30 minutes to solve the triplet of problems.

You may download all IMO problems from 1959 to 2012 or get to a 2012 PDF file directly. The six problems were constructed by folks from Greece, Australia, Canada; South Africa, Czechia, Serbia.

I have found a page with all the solutions, too.

Let me offer you a problem with the shortest solution, problem 2, here:
Problem 2 (Angelo di Pasquale, Australia)

Let $$a_2,a_3,\dots,a_n$$ be positive real numbers that satisfy $$a_2\cdot a_3\cdots a_n=1$$. Prove that$(a_2+1)^2(a_3+1)^3\cdots (a_n+1)^n \gt n^n.$
It looks easy, right? And it's probably the easiest problem, indeed. I never liked inequalities much because they contained "too little information". And another bad aspect of such problems is that you may train yourself to certain "standardized methods" to prove such propositions so it's boring and not too creative. However, when the remaining problems look hard, you may also view it as an advantage. ;-)

Who can solve it? Apologies: MathJax doesn't work in the DISQUS comments.

Picture via Viktor Kožený

Solution

Let me try to describe the thinking "how you could systematically find out" how to do it, so that the solution doesn't look like a miracle sent from God.

You want to show that the product of objects such as $$(a_k+1)^k$$ over $$k$$ is greater than something that doesn't depend on the values of $$a_k$$ themselves. And the only extra thing you may use is that the product of $$a_k$$ over $$k$$ is equal to one.

So if there is a proof, it must probably show that each of the factors $$(a_k+1)^k$$ is greater than $$a_k$$ itself times factors that are independent of $$a_k$$ and that either cancel or conspire to give you whatever you need. So you want to prove something of the form$(a_k+1)^k \geq f(k)\cdot a_k.$ If you manage to prove that, you may just take the product of these inequalities over $$k$$ from $$2$$ to $$n$$ which will be$\eq{ \prod_{k=2}^n (a_k+1)^k &\geq \prod_{k=2}^n f(k)\cdot \prod_{k=2}^n a_k\\ \prod_{k=2}^n (a_k+1)^k &\geq \prod_{k=2}^n f(k) }$ To go from the first line to the second, I used the information that the product of $$a_k$$'s is equal to one. Now, for this template of the proof to produce what we were asked to produce, we need $\prod_{k=2}^n f(k) = n^n.$ This is a pretty simple result for a product of $$f(k)$$ over many values of $$k$$; you would expect a harder result resembling $$n!$$. Assuming that the inequality we are asked to prove is "tight" or "hard" enough, it seems likely that the factors $$f(k)$$ mostly cancel between the adjacent values of $$k$$ and $$k+1$$ and what is left is $$n^n$$. In other words, we may directly reverse engineer what $$f(k)$$ should be so that it has the right product. If we have$f(k) = \frac{k^k}{(k-1)^{(k-1)}},$ then the product of $$f(k)$$ from $$2$$ to $$n$$ will simply give us the last numerator, $$n^n$$, because the initial denominator is $$1^1=1$$ and makes no impact while all the interior numerators and denominators cancel. Fine. So we have verified that the template of our proof works. The last thing we need to prove is the inequality we sketched at the beginning but now we write the explicit conjectured value of $$f(k)$$, $(a_k+1)^k \geq \frac{k^k}{(k-1)^{(k-1)}}\cdot a_k.$ However, this can actually be proved, indeed. Take the $$k$$-th root of this inequality and divide it by $$k$$:$\frac{a_k+1}{k} \geq \sqrt[k]{\frac{a_k}{(k-1)^{(k-1)}}}$ The right hand side looks like the geometric average of numbers $$a_k$$, $$1/(k-1)$$, $$1/(k-1)$$, and so on, where $$1/(k-1)$$ is repeated $$(k-1)$$ times. Similar problems often boil down to the inequality between the arithmetic average and the geometric average and indeed, this one is no exception (the arithmetic average is greater, try it for $$1$$ and $$9$$). The left hand side is nothing else than the arithmetic average of the same list:${\rm LHS} = \frac{1}{k} \zav{a_k + \frac{1}{k-1} + \frac{1}{k-1} + \cdots + \frac{1}{k-1}}.$ So the last component of our proof has been completed; it's the inequality between the arithmetic and geometric average. Now, the whole proof works. Note that the inequality between the arithmetic and geometric average is strict if there are at least two entries in the list that differ. That's inevitable for $$k\gt 2$$, as you can check.

For example, for $$k=3$$, $$1/(k-1)=1/2$$ so some $$a_k$$'s would have to be equal to $$1/2$$. At least one other $$a_k$$ would have to be greater than one because the product of all of them equals one but then it couldn't be equal to $$1/(k-1)$$ for other values of $$k$$. It follows that the inequality can't be saturated for $$n\geq 3$$ but as you can check, the inequality is saturated for $$n=2$$ because the product condition forces us to have $$a_2=1$$ and the inequality reduces to $$(1+1)^2\geq 2^2$$ which can't be made strict because it is actually an equality.

#### 31 comments:

1. Testing MathJax in DISQUS comments:$\int dx \frac{\alpha+\beta z}{\gamma+\delta d} g(x)$

2. test: $a+b^2$

3. Just wondering - why the strange index starting from a_{2}? I shall take some time to think about this problem.

4. This shift somewhat prettifies the notation in the proof. ;-)

5. Hi Lubos

You have a typo, (a_n + n)^n should be (a_n + 1)^n

As a former IMO student (1996 - bronze), I will now check to see how rusty I am :) Thanks for posting this challenge

6. Also, the linked PDF of problems gives the stipulation as strictly greater than n^n

7. I'll be terrified if it's not a typo! ;)

8. Tx for the corrections. The inequality holds as a strict one but one version of the problem I saw had the non-strict inequality...

9. n=2, a2=1 gives (1+1)^2 > 2^2

I think the inequality is not strict.

10. Agreed, it's strict for n greater than two, however. ;-)

11. Can you trace your STEM (Science Technology Engineering Mathematics) interest back to the Commodore computer you had as a kid? Plus the STEM curriculum K-12 (Kindegarten to 12th grade)?

12. Let's see, straight algebra would say you have the original given n times when you do the multiplication plus a positive number greater than one, ignoring the exponents. So somehow you have to show that when you take into account the exponents, each time to you take them down a notch you add another n to the multiplication, which you do a total of n times, equals n to the n plus a positive number who cares what it is. Sorry, 70 year old brain and I was never in your class in the first place. Oh well. Spent ten seconds on problem.

13. I suppose you might also prove it by induction?

14. media inequality and some induction

15. This is entirely off topic, but you have to see who stopped by after I called him on the most asinine AGW comment of the week.

16. miracle sent by God

Exactly my thought last night as I considered the question of what I'd need to solve it in any reasonable amount of time.

For 10 years or more I've been following the IBM Research Center's "Ponder This" problem of the month. I've only gotten my name posted three times, and one of those was by brute-forcing with a computer. However, I'm proud of the fact that only once have I sent in a wrong answer. :-)

That the U.S. did so well in the Olympiad (3rd place) sort of surprises me, since the IBM list always seems to be heavy with relatively "non-American" nationalities.

Maybe we've lost track of the Olympiad. I recall seeing it in the news decades ago, but not recently, or not enough that I've noticed it. Somebody correct me if I'm wrong.

17. Hi Luboš,

It's false for n = 2. Strict equality holds in that case.

By the way, I haven't read your solution yet without having a go at the thing first, nor have I read any of the other comments here for the same reason. So I guess that '>' is a typo and should be '>='.

What are the chances I'm going to end up saying "Doh!"? :) I make so many silly errors these days.

18. Dear Smoking Frog, the success of the U.S. team shouldn't surprise you. Four of the six U.S. contestant are ethnic East Asian, one is ethnic Indian, and only one is European American, probably a relative of Patrick Swayze ;-), see

http://www.imo-official.org/team_r.aspx?code=USA&year=2012

19. Dear John, you're right but the strictness has been discussed in several discussions above as well as in my solution.

I am somewhat disappointed no one attempted to prove the thing - and comments about a trivial n=2 case are indeed very, very far from a solution.

20. I did a try this morning in the bus, back from Benasque, but I got distracted searching for a bound for the simple product \Pi (a_k-1); it is amusing because then the bound for the product of the problem series times its reverse happens to have a bound a lot better than the implied n^(2n).

As for the answer, I wonder if the readership of the blog would prefer to use calculus for the last part of the proof. The minimum of the function ((x+1)^k)/x is more familiar, as exercise, than the arguments from geometric and arithmetic averages.

Of course, it is possible also to go in the force brute calculus way from the start, minimizing the function (\Pi (x_k+1)^k) / \Pi x_k, which will automagically produce all the proof process. But it is more inelegant.

21. Dear Luboš,

I'm sorry to be a disappointment to you. That wasn't my intention. Just joining in the fun, that's all. I didn't want to read any further and catch any hints until I had a go at it myself. I'll try later, but I'm a lot older than you and my lust for this kind of thing, though once ungovernable, has long since abated. I never thought it would. Now THAT's a great disappointment, but only to me.

I deliberately waited until after I posted my previous comment before I downloaded the pdf and saw the condition, n >= 3. I think you ought to add it to your box where you state the problem to help others like me and prevent us tripping on our own boot laces.

Incidentally, and just so there's no misunderstanding, I'm a great admirer of yours. Politically you are far more than just a breath of fresh air. So much of academia is under the thumb of the cancerous left it's truly wonderful to come across a rarity like you who not only refuses point blank to bow to the hideous totalitarianism but goes straight for its throat. Excellent stuff. More power to you. Much much more. I want to see it utterly destroyed and freedom returned.

My very best wishes to you.

22. Ah, well, that explains it.

23. I haven't put pen to paper but initially thought it should be easy to see what the minimum for the left part is. That seems to have been a misjudgement.

24. What left part?

Calculus could be used at three leves, I think.

Pure Brute force, if you know
about Lagrange multipliers, try to find the minimum of

(a_2+1)^2(a_3+1)^3\cdots (a_n+1)^n

restricted with the condition

a_2\cdot a_3\cdots a_n -1 =0

Such solution exceeds the expectations,
and the method is usually learn when
you are 19-20 years old.

Brute force with some insight,
you could know about partial
derivatives only and then to try
to find the minimum
(a_2+1)^2(a_3+1)^3\cdots (a_n+1)^n
\ over a_2\cdot a_3\cdots a_n
using effectively the fact that the product is equal to zero.

Insight, guessing and not so brute: you could argue following Lubos solution but use calculus only to get the minimum of a single term (a_k+1)^k \over a_k

25. that is my solution too...

26. (sorry by some obvious typos and fast mistakes here, obviously "product is equal to one", "levels", etc.

27. I will dispute your claim that Asians are more inherently talented at mathematics---the arguably most prestigious math competition in the world is the William Lowell Putnam exam---since 1938, there have been approx 153 non-Asian winners (fellows=top five) and 13 Asian---(Yes, the entrants are from US and Canadian universities, but many top Asian students go to these universities as undergrads. Note that Feynman won in 1938. Eoin Whitney won twice, 1948,49 (his son was my main competition in high school :)) The Asian(and Indian) culture is much more supportive of mathematical achievement than N. American is (or most European). Most of the active high level mathematicians today are not Asian (Terence Tao excepted and a few others).

28. Come on, Gordon, you surely know what's the right explanation for the non-Asian historical Putnam data, right? Before 1965 when Lyndon Johnson allowed them to immigrate under some conditions, Asians represented only 0.5 percent of the population.

http://www.japanmattersforamerica.org/2011/04/2010census_asians_in_america/

This did affect the composition of the students as well. They just didn't exist so how could they be winning Putnam all the time? Today, there are 17.3 Asians in America which is just 6 percent but they already have 4 out of 6 or 5 out of 6 - if you count the Indian guy - i.e. 67% or 83% in the U.S. math olympic team.

The math-loaded average IQ of Asians is by 15 points - one whole standard deviation - above the Caucasians so you're bound to see the effect and we do see the effect. The apparent "support" for such things in Asia is really a consequence, not a reason, of the ability gap.

29. By cultural, I simply mean that, for example, Russia dominated quite a few of the Olympiads when the Communists were trying to show that their system was superior---the reason for this was not an inherent superiority of the Russian mind. They identified young math geniuses and placed them in special schools and math camps under the Svengali tutelage of coaches who constantly had them competing against each other and in competitions. Read Masha Gessen's book, "Perfect Rigor" about Grigory Perelman. The Chinese do the same, and also the work ethic and loss of face for a family for not succeeding is a prime motivator. The Gaussian for math scores may be shifted to the right for Asians cf NA/Europeans, but I think the outliers to the extreme right would show no advantage. In North America, a similar math genius would likely be left "free range" unless he/(she, to not be flamed by Lisa R) was lucky enough to go to say, the Bronx High School of Science (Weinberg, Glashow) or Stuyvestant school (Brian Greene, Lisa R).

30. Dear Gordon, they may have been trying but you can't really overcome the biological parameters in this way.

The U.S. only began to compete in the 1970s. It had no real infrastructure for this contest, no gulags to torture the talented kids, and so on, but it had almost the same results in the 1970s and 1980s as the USSR, just check the numbers at

http://www.imo-official.org/results.aspx

31. To be sure, I am not a "nurture" vs genes promoter. But, genes have an extended phenotype...nurture can trigger latent genetic traits and does---epigenetics is taking off.
I do know that the Putnam in its earlier years certainly wasn't fair of me to use because there were few Asians in the US at universities. However, go to wiki and look up active 21st century mathematicians and see what % of Asians there are...
Also, while there are loads of published papers by Chinese U's, the quality is suspect and currently resulting in an attempted cleansing of plagiarism etc.
You are grossly undersestimating the effect of Confucianism, Tiger moms, and an aggressively competitive and specialized education system on very smart students. Not everyone is a Newton (or, say, a Simon Norton). I don't know about the Czech education system, but imo, ours at the primary and secondary level is so degraded that smart students are damaged and deterred unless they are exceptionally driven.