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.