Maths Olympiad Prep

Library / /24 of 27

Algebra Difficulty 7.0 National olympiad, round 2 Prove it Brazil

Let a1,a2,,a2011a_1, a_2, \dots, a_{2011} be nonnegative reals with sum 20112\frac{2011}{2}. Prove that
cyc(anan+1)=(a1a2)(a2a3)(a2011a1)3316. \left| \prod_{cyc} (a_n - a_{n+1}) \right| = \left| (a_1 - a_2)(a_2 - a_3) \dots (a_{2011} - a_1) \right| \le \frac{3\sqrt{3}}{16}.

Solution

In what follows, indices are taken modulo 20112011 and E=cyc(anan+1)E = \left| \prod_{cyc} (a_n - a_{n+1}) \right|.

Lemma. If EE is maximum, for every i{1,2,,2011}i \in \{1, 2, \dots, 2011\}, one of the numbers ai1,ai,ai+1a_{i-1}, a_i, a_{i+1} is zero.

*Proof.* Suppose, by means of contradiction, that EE is maximum and there exists aia_i such that ai1,ai,ai+1a_{i-1}, a_i, a_{i+1} are all nonzero (that is, ai1aiai+1>0a_{i-1}a_i a_{i+1} > 0). Define A={aiai>0}A = \{a_i \mid a_i > 0\} and B={aiai1aiai+1>0}B = \{a_i \mid a_{i-1}a_i a_{i+1} > 0\}. Then BAB \subset A and BB \neq \emptyset. Let ak=minBa_k = \min B and consider ak1a_{k-1} and ak+1a_{k+1}. We have the following cases:

* ak<ak1a_k < a_{k-1} and ak<ak+1a_k < a_{k+1}. Let
ai={0,if ai=0 or i=kai+akA1,if ai>0 and ik a'_i = \begin{cases} 0, & \text{if } a_i = 0 \text{ or } i = k \\ a_i + \frac{a_k}{|A|-1}, & \text{if } a_i > 0 \text{ and } i \neq k \end{cases}
That is, we make aka_k be zero and distribute it among the remaining nonzero terms. So aiai+1|a_i - a_{i+1}| remains unchanged if ai,ai+1Aa_i, a_{i+1} \in A and k{i,i+1}k \notin \{i, i+1\}, or ai,ai+1Aa_i, a_{i+1} \notin A; increases from aiai+1=max{ai,ai+1}|a_i - a_{i+1}| = \max\{a_i, a_{i+1}\} to max{ai,ai+1}+akA1\max\{a_i, a_{i+1}\} + \frac{a_k}{|A|-1} if aiAa_i \notin A or ai+1Aa_{i+1} \notin A, but not both; increases from ak±1ak=ak±1ak|a_{k \pm 1} - a_k| = a_{k \pm 1} - a_k to ak±1+akA1a_{k \pm 1} + \frac{a_k}{|A|-1} if k{i,i+1}k \in \{i, i+1\}.

* ak1<ak<ak+1a_{k-1} < a_k < a_{k+1}. This means that ak1Ba_{k-1} \notin B, and akBa_k \in B, ak1>0a_{k-1} > 0, that is, ak1ABa_{k-1} \in A \setminus B, which means ak2=0a_{k-2} = 0. In this case, we exchange (ak1,ak)(a_{k-1}, a_k) for (ak1,ak)=(ak1+ak,0)(a'_{k-1}, a'_k) = (a_{k-1} + a_k, 0). Then aiai+1|a_i - a_{i+1}| remains unchanged for i{k2,k1,k}i \notin \{k-2, k-1, k\}; for i=k2i = k-2 increases from ak2ak1=ak1|a_{k-2} - a_{k-1}| = a_{k-1} to ak2ak1=ak1+ak|a_{k-2} - a'_{k-1}| = a_{k-1} + a_k; for i=k1i = k-1 increases from ak1ak=akak1|a_{k-1} - a_k| = a_k - a_{k-1} to ak1ak=ak1+ak|a'_{k-1} - a'_k| = a_{k-1} + a_k; for i=ki = k increases from akak+1=ak+1ak|a_k - a_{k+1}| = a_{k+1} - a_k to akak+1=ak+1|a'_{k} - a_{k+1}| = a_{k+1}.

* ak1>ak>ak+1a_{k-1} > a_k > a_{k+1}. Analogous to the previous case.

* ak>ak1a_k > a_{k-1} and ak>ak+1a_k > a_{k+1}. This means ak1,ak+1ABa_{k-1}, a_{k+1} \in A \setminus B, that is, ak2=ak+2=0a_{k-2} = a_{k+2} = 0. In this case, exchange (ak1,ak,ak+1)(a_{k-1}, a_k, a_{k+1}) for (ak1,ak,ak+1)=(ak1+ak/2,0,ak+1+ak/2)(a'_{k-1}, a'_k, a'_{k+1}) = (a_{k-1} + a_k/2, 0, a_{k+1} + a_k/2). All differences aiai+1|a_i - a_{i+1}| remain unchanged except if i{k2,k1,k,k+1}i \in \{k-2, k-1, k, k+1\}. The only change is (ak2ak1)(ak1ak)(akak+1)(ak+1ak+2)=ak1(akak1)(akak+1)ak+1|(a_{k-2}-a_{k-1})(a_{k-1}-a_k)(a_k-a_{k+1})(a_{k+1}-a_{k+2})| = a_{k-1}(a_k-a_{k-1})(a_k-a_{k+1})a_{k+1} to (ak2ak1)(ak1ak)(akak+1)(ak+1ak+2)=(ak1+ak/2)2(ak+1+ak/2)2|(a_{k-2}-a'_{k-1})(a'_{k-1}-a'_k)(a'_k-a'_{k+1})(a'_{k+1}-a_{k+2})| = (a_{k-1}+a_k/2)^2(a_{k+1}+a_k/2)^2. But
(ak1+ak/2)2(ak+1+ak/2)2=(ak1(ak1+ak)+ak2/4)(ak+1(ak+1+ak)+ak2/4)>ak1(ak+ak1)(ak+ak+1)ak+1>ak1(akak1)(akak+1)ak+1 \begin{aligned} & (a_{k-1} + a_k/2)^2 (a_{k+1} + a_k/2)^2 \\ & = (a_{k-1}(a_{k-1} + a_k) + a_k^2/4)(a_{k+1}(a_{k+1} + a_k) + a_k^2/4) \\ & > a_{k-1}(a_k + a_{k-1})(a_k + a_{k+1})a_{k+1} \\ & > a_{k-1}(a_k - a_{k-1})(a_k - a_{k+1})a_{k+1} \end{aligned}

Now we only have groups with one or two consecutive nonzero variables. For a group (0,ak,0)(0, a_k, 0), we obtain the product (ak1ak)(akak+1)=ak2|(a_{k-1} - a_k)(a_k - a_{k+1})| = a_k^2; for a group (0,ak,ak+1,0)(0, a_k, a_{k+1}, 0), we obtain (ak1ak)(akak+1)(ak+1ak+2)=akak+1ak+1ak|(a_{k-1} - a_k)(a_k - a_{k+1})(a_{k+1} - a_{k+2})| = a_k a_{k+1}|a_{k+1} - a_k|. Notice that the groups can be interchanged, such that we can suppose wlog that all groups with two nonzero variables are contiguous.

Lemma. If EE is maximum then there is exactly one group with two nonzero variables.
Suppose, that there are at least two groups of nonzero variables (0,a,b,0)(0, a, b, 0) and (0,c,d,0)(0, c, d, 0). By the above remark, we can suppose wlog that the groups are consecutive, that is, it's (0,a,b,0,c,d,0)(0, a, b, 0, c, d, 0). Exchange these variables for (0,a+b/2,0,(b+c)/2,0,d+c/2,0)(0, a + b/2, 0, (b+c)/2, 0, d + c/2, 0). The product abcd(ab)(cd)abcd|(a-b)(c-d)| is exchanged for (a+b/2)2((b+c)/2)2(d+c/2)2(a+b/2)^2((b+c)/2)^2(d+c/2)^2. But we already know that (a+b/2)2>aab(a+b/2)^2 > a|a-b|, (d+c/2)2>dcd(d+c/2)^2 > d|c-d| and, by AM-GM, ((b+c)/2)2bc((b+c)/2)^2 \ge bc. Multiplying everything yields the lemma.

Combining the two lemmas, we can suppose wlog that the nonzero variables are the ones with odd indices, that is, a1,a3,,a2011a_1, a_3, \dots, a_{2011}. In this case, we obtain the product a1a2011a1a2011a32a52a20092a_1 a_{2011} |a_1 - a_{2011}| a_3^2 a_5^2 \dots a_{2009}^2, and we can optimize it locally.
Let a1+a2011=sa_1 + a_{2011} = s and suppose wlog a1>a2011a_1 > a_{2011}. Let α,β\alpha, \beta be positive real numbers to be determined. By AM-GM,
a1a2011(a1a2011)=1αβ(αa1)(βa2011)(a1a2011)1αβ(αa1+βa2011+(a1a2011)3)3=1αβ((α+1)a1+(β1)a20113)3 \begin{aligned} a_1 a_{2011} (a_1 - a_{2011}) &= \frac{1}{\alpha\beta} (\alpha a_1) (\beta a_{2011}) (a_1 - a_{2011}) \\ &\le \frac{1}{\alpha\beta} \left( \frac{\alpha a_1 + \beta a_{2011} + (a_1 - a_{2011})}{3} \right)^3 \\ &= \frac{1}{\alpha\beta} \left( \frac{(\alpha + 1)a_1 + (\beta - 1)a_{2011}}{3} \right)^3 \end{aligned}
So we choose α\alpha and β\beta such that
* we obtain ss in the end, that is, α+1=β1βα=2\alpha + 1 = \beta - 1 \Leftrightarrow \beta - \alpha = 2;
* the equality can occur, that is, αa1=βa2011=a1a2011a2011=(1α)a1\alpha a_1 = \beta a_{2011} = a_1 - a_{2011} \Leftrightarrow a_{2011} = (1-\alpha)a_1 and a1=(β+1)a2011a_1 = (\beta+1)a_{2011}, that is, 1=(1α)(β+1)αβ=αβ=21 = (1-\alpha)(\beta+1) \Leftrightarrow -\alpha\beta = \alpha - \beta = -2.
Thus α-\alpha and β\beta are the roots of the quadratic t22t2=0t^2 - 2t - 2 = 0. Hence α=31\alpha = \sqrt{3} - 1 and β=1+3\beta = 1 + \sqrt{3}, and
a1a2011(a1a2011)1αβ((α+1)a1+(β1)a20113)3=12(3(a1+a2011)3)3=318s3 \begin{aligned} a_1 a_{2011} (a_1 - a_{2011}) &\le \frac{1}{\alpha\beta} \left( \frac{(\alpha + 1)a_1 + (\beta - 1)a_{2011}}{3} \right)^3 \\ &= \frac{1}{2} \left( \frac{\sqrt{3}(a_1 + a_{2011})}{3} \right)^3 = \frac{\sqrt{3}}{18} s^3 \end{aligned}

Now we optimize the rest. If a3+a5++a2009=20112sa_3 + a_5 + \dots + a_{2009} = \frac{2011}{2} - s,
a32a52a20092(a3+a5++a20091004)2008=(20112s1004)2008 a_3^2 a_5^2 \dots a_{2009}^2 \le \left( \frac{a_3 + a_5 + \dots + a_{2009}}{1004} \right)^{2008} = \left( \frac{\frac{2011}{2} - s}{1004} \right)^{2008}

\begin{align*}
E &= a_1 a_{2011} |a_1 - a_{2011}| a_3^2 a_5^2 \dots a_{2009}^2 \\
&\le \frac{\sqrt{3}}{18} s^3 \cdot \left(\frac{\frac{2011}{2}-s}{1004}\right)^{2008} = \frac{\sqrt{3}}{18\gamma^3} (\gamma s)^3 \left(\frac{\frac{2011}{2}-s}{1004}\right)^{2008} \\
&\le \frac{\sqrt{3}}{18\gamma^3} \left( \frac{3\gamma s + 2008 \cdot \frac{\frac{2011}{2}-s}{1004}}{2011} \right)^{2011} \\
&= \frac{\sqrt{3}}{18\gamma^3} \left( \frac{2011 + (3\gamma - 2)s}{2011} \right)^{2011}
\end{align*}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.