Maths Olympiad Prep

Library / /2 of 3

Algebra Difficulty 6.9 National olympiad Prove it South Korea

For an integer n3n \ge 3 and real numbers a1,,ana_1, \dots, a_n and b1,,bnb_1, \dots, b_n, show the following inequality.
i=1nai(bibi+3)3n8i=1n[(aiai+1)2+(bibi+1)2](an+1=a1 and bn+1=b1 for i=1,2,3) \sum_{i=1}^{n} a_i (b_i - b_{i+3}) \le \frac{3n}{8} \sum_{i=1}^{n} \left[ (a_i - a_{i+1})^2 + (b_i - b_{i+1})^2 \right] \\ (a_{n+1} = a_1 \text{ and } b_{n+1} = b_1 \text{ for } i = 1, 2, 3)

Solutions — 3

Solution 1

It suffices to prove the following.
i=1nai(bibi+1)n8i=1n[(aiai+1)2+(bibi+1)2] \sum_{i=1}^{n} a_i(b_i - b_{i+1}) \le \frac{n}{8} \sum_{i=1}^{n} \left[ (a_i - a_{i+1})^2 + (b_i - b_{i+1})^2 \right]
By replacing bib_i by bi+jb_{i+j} in the above equation and adding up for j=0,1,2j = 0, 1, 2, we can obtain our desired result. Let
R=12i=1n[(aiai+1)2+(bibi+1)2] \mathcal{R} = \frac{1}{2} \sum_{i=1}^{n} \left[ (a_i - a_{i+1})^2 + (b_i - b_{i+1})^2 \right]
and consider
Sj=i=1nai+j(bibi+1) S_j = \sum_{i=1}^{n} a_{i+j}(b_i - b_{i+1})
where jj is integer. (We consider any indices as modulo nn, so that ai+nk=aia_{i+nk} = a_i holds for every integers i,ki, k.) We can observe
SjSj+1=i=1n(ai+jai+j+1)(bibi+1)12i=1n((ai+jai+j+1)2+(bibi+1)2)=12(i=1n(ai+jai+j+1)2+i=1n(bibi+1)2)=R \begin{aligned} |S_j - S_{j+1}| &= \left| \sum_{i=1}^{n} (a_{i+j} - a_{i+j+1})(b_i - b_{i+1}) \right| \\ &\le \frac{1}{2} \sum_{i=1}^{n} \left( (a_{i+j} - a_{i+j+1})^2 + (b_i - b_{i+1})^2 \right) \\ &= \frac{1}{2} \left( \sum_{i=1}^{n} (a_{i+j} - a_{i+j+1})^2 + \sum_{i=1}^{n} (b_i - b_{i+1})^2 \right) \\ &= \mathcal{R} \end{aligned}
and obtain the following as its result:
S0SjjR. |S_0 - S_j| \le |j| \mathcal{R}.
Meanwhile we have
j=0n1Sj=i=1n(j=0n1ai+j)(bibi+1)=(j=0n1aj)(i=1n(bibi+1))=0 \sum_{j=0}^{n-1} S_j = \sum_{i=1}^{n} \left( \sum_{j=0}^{n-1} a_{i+j} \right) (b_i - b_{i+1}) = \left( \sum_{j=0}^{n-1} a_j \right) \left( \sum_{i=1}^{n} (b_i - b_{i+1}) \right) = 0
so for any n<k<n-n < k < n we have
nS0=j=k+1nk(S0Sj)j=k+1nkS0SjRj=k+1nkj. nS_0 = \sum_{j=-k+1}^{n-k} (S_0 - S_j) \le \sum_{j=-k+1}^{n-k} |S_0 - S_j| \le \mathcal{R} \sum_{j=-k+1}^{n-k} |j|.
If nn is even then we let k=n/2k = n/2 to obtain
nS0Rj=n/2+1n/2j=n24R nS_0 \le \mathcal{R} \sum_{j=-n/2+1}^{n/2} |j| = \frac{n^2}{4} \mathcal{R}
and if nn is odd then we let k=(n+1)/2k = (n + 1)/2 to obtain
nS0Rj=(n1)/2(n1)/2j=n214R<n24R. nS_0 \le \mathcal{R} \sum_{j=-(n-1)/2}^{(n-1)/2} |j| = \frac{n^2-1}{4} \mathcal{R} < \frac{n^2}{4} \mathcal{R}.
In any cases, we have
S0n4R=n8i=1n[(aiai+1)2+(bibi+1)2] S_0 \le \frac{n}{4} \mathcal{R} = \frac{n}{8} \sum_{i=1}^{n} \left[ (a_i - a_{i+1})^2 + (b_i - b_{i+1})^2 \right]
thus proving our inequality. \square

Solution 2

We will show the following inequality as in the Solution 1.
i=1nai(bibi+1)n8i=1n[(aiai+1)2+(bibi+1)2] \sum_{i=1}^{n} a_i (b_i - b_{i+1}) \le \frac{n}{8} \sum_{i=1}^{n} \left[ (a_i - a_{i+1})^2 + (b_i - b_{i+1})^2 \right]
Let aˉ\bar{a} be the average of all aia_i. Then above is equivalent to:
i=1n(aiaˉ)(bibi+1)n8i=1n[(aiai+1)2+(bibi+1)2]. \sum_{i=1}^{n} (a_i - \bar{a})(b_i - b_{i+1}) \le \frac{n}{8} \sum_{i=1}^{n} \left[ (a_i - a_{i+1})^2 + (b_i - b_{i+1})^2 \right].
By noting the following (follows from AM-GM)
i=1n(aiaˉ)(bibi+1)2ni=1n(aiaˉ)2+n8i=1n(bibi+1)2 \sum_{i=1}^{n} (a_i - \bar{a})(b_i - b_{i+1}) \leq \frac{2}{n} \sum_{i=1}^{n} (a_i - \bar{a})^2 + \frac{n}{8} \sum_{i=1}^{n} (b_i - b_{i+1})^2
it suffices to prove
i=1n(aiaˉ)2n216i=1n(aiai+1)2. \sum_{i=1}^{n} (a_i - \bar{a})^2 \leq \frac{n^2}{16} \sum_{i=1}^{n} (a_i - a_{i+1})^2.
We let
M=maxaiminai M = \max a_i - \min a_i
and we will obtain bounds for both sides using MM.
Lemma 4. We have
i=1n(aiaˉ)2n4M2. \sum_{i=1}^{n} (a_i - \bar{a})^2 \leq \frac{n}{4} M^2.
Proof. Both sides of the equation are invariant under adding same constant to all aia_i, so it suffices to show when (maxai,minai)=(M/2,M/2)(\max a_i, \min a_i) = (M/2, -M/2). In that case, we can show:
i=1n(aiaˉ)2=i=1nai2naˉ2i=1nai2i=1n(M/2)2=n4M2. \sum_{i=1}^{n} (a_i - \bar{a})^2 = \sum_{i=1}^{n} a_i^2 - n\bar{a}^2 \leq \sum_{i=1}^{n} a_i^2 \leq \sum_{i=1}^{n} (M/2)^2 = \frac{n}{4} M^2.
Lemma 5. We have
i=1n(aiai+1)24nM2. \sum_{i=1}^{n} (a_i - a_{i+1})^2 \geq \frac{4}{n} M^2.
Proof. Let ai,aja_i, a_j be the maximum and minimum among a1,,ana_1, \dots, a_n respectively, and assume i<ji < j without loss of generality. Using the Cauchy-Schwarz inequality we have
M2=(l=ij1(alal+1))2(ji)l=ij1(alal+1)2 M^2 = \left( \sum_{l=i}^{j-1} (a_l - a_{l+1}) \right)^2 \leq (j-i) \sum_{l=i}^{j-1} (a_l - a_{l+1})^2
and similarly
M2=(l=jn+i1(alal+1))2(n+ij)l=jn+i1(alal+1)2. M^2 = \left( \sum_{l=j}^{n+i-1} (a_l - a_{l+1}) \right)^2 \leq (n+i-j) \sum_{l=j}^{n+i-1} (a_l - a_{l+1})^2.
Thus we have (the last part uses AM-HM)
l=1n(alal+1)2=l=ij1(alal+1)2+l=jn+i1(alal+1)2M2ji+M2n+ij4M2n. \begin{aligned} \sum_{l=1}^{n} (a_l - a_{l+1})^2 &= \sum_{l=i}^{j-1} (a_l - a_{l+1})^2 + \sum_{l=j}^{n+i-1} (a_l - a_{l+1})^2 \\ &\le \frac{M^2}{j-i} + \frac{M^2}{n+i-j} \\ &\le \frac{4M^2}{n}. \end{aligned}
Combining those two lemmas yield the desired result of
i=1n(aiaˉ)2nM24n216i=1n(aiai+1)2. \sum_{i=1}^{n} (a_i - \bar{a})^2 \le \frac{nM^2}{4} \le \frac{n^2}{16} \sum_{i=1}^{n} (a_i - a_{i+1})^2.

Solution 3

We note that if n=3n = 3 then the left hand side (of our original inequality) becomes zero so our problem holds obviously. In this solution, we will prove the following inequality of the Solution 1 for n4n \ge 4.
i=1nai(bibi+1)n8i=1n[(aiai+1)2+(bibi+1)2] \sum_{i=1}^{n} a_i (b_i - b_{i+1}) \le \frac{n}{8} \sum_{i=1}^{n} [(a_i - a_{i+1})^2 + (b_i - b_{i+1})^2]
We will consider sum of the following two inequalities.
i=1n(aiai+1)(bibi+1)12i=1n[(aiai+1)2+(bibi+1)2]i=1n(ai+ai+1)(bibi+1)cot(π/n)2i=1n[(aiai+1)2+(bibi+1)2] \begin{aligned} \sum_{i=1}^{n} (a_i - a_{i+1})(b_i - b_{i+1}) &\le \frac{1}{2} \sum_{i=1}^{n} [(a_i - a_{i+1})^2 + (b_i - b_{i+1})^2] \\ \sum_{i=1}^{n} (a_i + a_{i+1})(b_i - b_{i+1}) &\le \frac{\cot(\pi/n)}{2} \sum_{i=1}^{n} [(a_i - a_{i+1})^2 + (b_i - b_{i+1})^2] \end{aligned}
The first one follows easily from AM-GM. For the second one, we consider a nn-gon whose vertices have coordinates (ai,bi)(a_i, b_i). Then we can interpret its the left hand and righthand sides as two times its (signed) area and the sum of squares of its sides respectively. By considering the isoperimetric inequality for nn-gon and Cauchy-Schwarz inequality, one can show their ratio is maximized for regular nn-gon, so it suffices to check equality holds for regular nn-gon case.
Summing those two gives
i=1n2ai(bibi+1)(12+cot(π/n)2)i=1n[(aiai+1)2+(bibi+1)2] \sum_{i=1}^{n} 2a_i(b_i - b_{i+1}) \le \left(\frac{1}{2} + \frac{\cot(\pi/n)}{2}\right) \sum_{i=1}^{n} \left[(a_i - a_{i+1})^2 + (b_i - b_{i+1})^2\right]
so it suffices to show
12+cot(π/n)2n4 \frac{1}{2} + \frac{\cot(\pi/n)}{2} \le \frac{n}{4}
for n4n \ge 4. When n6n \ge 6, we use cot(x)=(tan(x))1<1/x\cot(x) = (\tan(x))^{-1} < 1/x and π>3\pi > 3 to show
12+n2π<12+n6n4. \frac{1}{2} + \frac{n}{2\pi} < \frac{1}{2} + \frac{n}{6} \le \frac{n}{4}.
For n=4n = 4 and n=5n = 5, we can prove it by explicitly calculating cot(π/n)\cot(\pi/n). (cot(π/4)=1\cot(\pi/4) = 1, cot(π/5)=1+25\cot(\pi/5) = \sqrt{1 + \frac{2}{\sqrt{5}}})

Remark. The 'optimal constant' for this inequality can be given as
Cop=(1+2cos(2π/n))4sin(π/n) C_{op} = \frac{(1 + 2 \cos(2\pi/n))}{4 \sin(\pi/n)}
instead of 3n/83n/8. Consider a vector space V={(x1,,xn):xi=0}V = \{(x_1, \dots, x_n) : \sum x_i = 0\} and an operator TT on VV defined as T((xi))=(xi+1)T((x_i)) = (x_{i+1}). Then our inequality can be expressed as follows. (The absolute value denotes the ordinary Euclidean length induced from VRnV \le \mathbb{R}^n)
a,(1T3)bC((1T)a2+(1T)b2) \langle a, (1 - T^3)b \rangle \le C (|(1 - T)a|^2 + |(1 - T)b|^2)
The operator TT on VV is orthogonal, and it can be diagonalized by complex orthogonal basis vk=(ζnkj)j=1,,nv_k = (\zeta_n^{kj})_{j=1, \dots, n} (1k<n1 \le k < n) as Tvk=ζnkvkTv_k = \zeta_n^k v_k (ζn=exp(2πi/n)\zeta_n = \exp(2\pi i/n)). Thus 1T1-T is invertible, and we can express the above inequality as follows. (u=(1T)a,v=(1T)bu = (1-T)a, v = (1-T)b)
(1T)1u,(1+T+T2)v=u,(1T)1(1+T+T2)vC(u2+v2) \langle (1 - T)^{-1}u, (1 + T + T^2)v \rangle = \langle u, (1 - T)^{-1}(1 + T + T^2)v \rangle \le C (|u|^2 + |v|^2)
One can see that CC can be given as the operator norm of S=(1T)1(1+T+T2)S = (1-T)^{-1}(1+T+T^2). As SS is normal operator, its operator norm is given as maximum of absolute value of its eigenvalues (1ζnk)1(1+ζnk+ζn2k)|(1-\zeta_n^k)^{-1}(1+\zeta_n^k+\zeta_n^{2k})|. One can observe that this obtains maximum CopC_{op} when k=1k=1 or k=n1k=n-1. \square

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.