Maths Olympiad Prep

Library / /3 of 3

Algebra Difficulty 8.2 Shortlist Prove it South Korea

Find the smallest positive real number p(1)p (\le 1) such that the inequality
i=12024xi(y2025iy2024i)1p \sum_{i=1}^{2024} x_i (y_{2025-i} - y_{2024-i}) \ge 1 - p
holds for all real numbers 0x1x2x202410 \le x_1 \le x_2 \le \dots \le x_{2024} \le 1 and 0=y0y1y2y202410 = y_0 \le y_1 \le y_2 \le \dots \le y_{2024} \le 1 satisfying
i=12024xi=i=12024yi=2024p. \sum_{i=1}^{2024} x_i = \sum_{i=1}^{2024} y_i = 2024p.

Solution

If x1=x2==x2024=y1=y2==y2024=px_1 = x_2 = \dots = x_{2024} = y_1 = y_2 = \dots = y_{2024} = p, then p21pp^2 \ge 1-p, that is, p1+52p \ge \frac{1+\sqrt{5}}{2}. So, pp must be at least 1+52\frac{1+\sqrt{5}}{2}. We prove that the condition holds for p=1+52p = \frac{1+\sqrt{5}}{2}, which implies that the answer is 1+52\frac{1+\sqrt{5}}{2}.
Let p=1+52p = \frac{1+\sqrt{5}}{2}, and let
S={(x1,,x2024)0x1x20241,x1+x2++x2024=2024p}. S = \{(x_1, \dots, x_{2024}) \mid 0 \le x_1 \le \dots \le x_{2024} \le 1, x_1 + x_2 + \dots + x_{2024} = 2024p\}.
For X=(x1,x2,,x2024)X = (x_1, x_2, \dots, x_{2024}), Y=(y1,y2,,y2024)SY = (y_1, y_2, \dots, y_{2024}) \in S, we regard x0=y0=0x_0 = y_0 = 0 for convenience, and let
f(X,Y)=i=12024xi(y2025iy2024i)=x1(y2024y2023)+x2(y2023y2022)++x2023(y2y1)+x2024y1. f(X, Y) = \sum_{i=1}^{2024} x_i (y_{2025-i} - y_{2024-i}) \\ = x_1(y_{2024} - y_{2023}) + x_2(y_{2023} - y_{2022}) + \dots + x_{2023}(y_2 - y_1) + x_{2024}y_1.
Since f(X,Y)=y1(x2024x2023)+y2(x2023x2022)++y2023(x2x1)+y2024x1f(X, Y) = y_1(x_{2024} - x_{2023}) + y_2(x_{2023} - x_{2022}) + \dots + y_{2023}(x_2 - x_1) + y_{2024}x_1, f(X,Y)f(X, Y) is symmetric with regard to XX and YY. If x1=x2==xk1=a1x_1 = x_2 = \dots = x_{k_1} = a_1, xk1+1==xk1+k2=a2x_{k_1+1} = \dots = x_{k_1+k_2} = a_2, ,\dots, xk1+k2++km1+1==xn=amx_{k_1+k_2+\dots+k_{m-1}+1} = \dots = x_n = a_m for 0a1<a2<<am10 \le a_1 < a_2 < \dots < a_m \le 1, we denote XX by (a1k1,a2k2,,amkm)(a_1^{k_1}, a_2^{k_2}, \dots, a_m^{k_m}) where km=2024k1k2km1k_m = 2024 - k_1 - k_2 - \dots - k_{m-1}, and let l(X)=ml(X) = m. And in this case, we have
f(X,Y)=a1(y2024y2024k1)+a2(y2024k1y2024k1k2)++amykm=a1Y1+a2Y2++amYm f(X, Y) = a_1(y_{2024} - y_{2024-k_1}) + a_2(y_{2024-k_1} - y_{2024-k_1-k_2}) + \dots + a_m y_{k_m} \\ = a_1 Y_1 + a_2 Y_2 + \dots + a_m Y_m
where Yt=y2024k1k2kt1y2024k1k2kt=ykt+kt+1++kmykt+1++kmY_t = y_{2024-k_1-k_2-\dots-k_{t-1}} - y_{2024-k_1-k_2-\dots-k_t} = y_{k_t+k_{t+1}+\dots+k_m} - y_{k_t+1+\dots+k_m} for t=1,2,,mt = 1, 2, \dots, m.
Now we consider X,YSX, Y \in S such that f(X,Y)f(X, Y) is minimized, and subject to that l(X)+l(Y)l(X) + l(Y) is minimum. Let X=(a1k1,a2k2,,amkm)X = (a_1^{k_1}, a_2^{k_2}, \dots, a_m^{k_m}).
Lemma. There is no 1i<m1 \le i < m such that 0<ai,ai+1<10 < a_i, a_{i+1} < 1.

Proof. Suppose 0<ai<ai+1<10 < a_i < a_{i+1} < 1 for some ii.
Case 1. YikiYi+1ki+1\frac{Y_i}{k_i} \le \frac{Y_{i+1}}{k_{i+1}}.
Let a=kiai+ki+1ai+1ki+ki+1a = \frac{k_i a_i + k_{i+1} a_{i+1}}{k_i + k_{i+1}}. Then, ai<a<ai+1a_i < a < a_{i+1}, and for
X=(a1k1,,ai1ki1,ai1ki1+ki+1,ai+2ki+2,,amkm) X' = (a_1^{k_1}, \dots, a_{i-1}^{k_{i-1}}, a_{i-1}^{k_{i-1}+k_{i+1}}, a_{i+2}^{k_{i+2}}, \dots, a_m^{k_m})
we have
f(X,Y)f(X,Y)0 f(X, Y) - f(X', Y) \ge 0
and l(X)=m1<l(X)l(X') = m - 1 < l(X), which yields a contradiction to the fact that l(X)+l(Y)l(X) + l(Y) is minimum.
Case 2. Yiki>Yi+1ki+1\frac{Y_i}{k_i} > \frac{Y_{i+1}}{k_{i+1}}.
Choose a positive real number ee such that e<aiai1e < a_i - a_{i-1} (if i=1i = 1, let a0=0a_0 = 0) and ai+1+kieki+1<ai+2a_{i+1} + \frac{k_i e}{k_{i+1}} < a_{i+2} (if i=m1i = m - 1, let am+1=1a_{m+1} = 1). Let a=aiea = a_i - e and b=ai+1+kieki+1b = a_{i+1} + \frac{k_i e}{k_{i+1}}, and consider X=(a1k1,a2k2,,ai1ki1,aki,bki+1,ai+2ki+2,,amkm)X' = (a_1^{k_1}, a_2^{k_2}, \dots, a_{i-1}^{k_{i-1}}, a^{k_i}, b^{k_{i+1}}, a_{i+2}^{k_{i+2}}, \dots, a_m^{k_m}). Since kia+ki+1b=kiai+ki+1ai+1k_i a + k_{i+1} b = k_i a_i + k_{i+1} a_{i+1}, XSX' \in S. However, f(X,Y)f(X,Y)>0f(X, Y) - f(X, Y') > 0, yielding a contradiction. Therefore there is no 1i<m1 \le i < m such that 0<ai,ai+1<10 < a_i, a_{i+1} < 1. \square
The above lemma also holds for YY. Thus, there exist non-negative integers k1,k2,k3,s1,s2,s3k_1, k_2, k_3, s_1, s_2, s_3 and real numbers 0<a,b<10 < a, b < 1 such that
k1+k2+k3=s1+s2+s3=2024, \bullet \quad k_1 + k_2 + k_3 = s_1 + s_2 + s_3 = 2024,
x1=x2==xk1=0,xk1+1==xk1+k2=a,xk1+k2+1==x2024=1 \bullet \quad x_1 = x_2 = \cdots = x_{k_1} = 0, x_{k_1+1} = \cdots = x_{k_1+k_2} = a, x_{k_1+k_2+1} = \cdots = x_{2024} = 1
y1=y2==ys1=0,ys1+1==ys1+s2=a,ys1+s2+1==y2024=1 \bullet \quad y_1 = y_2 = \cdots = y_{s_1} = 0, y_{s_1+1} = \cdots = y_{s_1+s_2} = a, y_{s_1+s_2+1} = \cdots = y_{2024} = 1
k2a+k3=s2b+s3=2024p. \bullet \quad k_2 a + k_3 = s_2 b + s_3 = 2024p.
We note that k1,k2,k3,s1,s2,s3k_1, k_2, k_3, s_1, s_2, s_3 could be zero, and we have
f(X,Y)=ayk2+k3+(1a)yk3=bxs2+s3+(1b)xs3. f(X, Y) = a y_{k_2+k_3} + (1-a) y_{k_3} = b x_{s_2+s_3} + (1-b) x_{s_3}.
If k2=0k_2 = 0, then x1+x2++x2024=k32024px_1 + x_2 + \cdots + x_{2024} = k_3 \ne 2024p (since k3k_3 is an integer), so k2>0k_2 > 0. Thus, k3<k2a+k3=2024pk_3 < k_2 a + k_3 = 2024p and k1=2024(k2+k3)<2024(k2a+k3)=2024(1p)k_1 = 2024 - (k_2 + k_3) < 2024 - (k_2 a + k_3) = 2024(1-p). That is,
k1<2024(1p),k2>0,k3<2024p, k_1 < 2024(1-p), \quad k_2 > 0, \quad k_3 < 2024p,
and similarly,
s1<2024(1p),s2>0,s3<2024p. s_1 < 2024(1-p), \quad s_2 > 0, \quad s_3 < 2024p.
Since y1=y2==ys1=0y_1 = y_2 = \dots = y_{s_1} = 0, ys1+1==ys1+s2=ay_{s_1+1} = \dots = y_{s_1+s_2} = a, and ys1+s2+1==y2024=1y_{s_1+s_2+1} = \dots = y_{2024} = 1, in order for f(X,Y)=ayk2+k3+(1a)yk3f(X, Y) = a y_{k_2+k_3} + (1-a) y_{k_3} to be minimized, the following must hold.
(i) yk2+k3+1==y2024=1y_{k_2+k_3+1} = \dots = y_{2024} = 1
(ii) yk3+1==yk2+k3y_{k_3+1} = \dots = y_{k_2+k_3}
(iii) y1==yk3y_1 = \dots = y_{k_3}
Similarly, the following must hold.
(i') xs2+s3+1==x2024=1x_{s_2+s_3+1} = \dots = x_{2024} = 1
(ii') xs3+1==xs2+s3x_{s_3+1} = \dots = x_{s_2+s_3}
(iii') x1==xs3x_1 = \dots = x_{s_3}
By (i) and (i'), k1s3k_1 \le s_3 and s1k3s_1 \le k_3.
If k1<s3k_1 < s_3, then yk3+1=1y_{k_3+1} = 1 by (i) and (ii), so k1+k2s3<2024pk_1 + k_2 \le s_3 < 2024p. Then by (iii), k3=s2k_3 = s_2, yk3=by_{k_3} = b and s1=0s_1 = 0, k1+k2=s3k_1 + k_2 = s_3. So,
a=2024pk3k2=2024pk32024k1k32024pk32024k3=12024(1p)2024k3b=2024ps3s2=2024pk1k2k3=k32024(1p)k3=12024(1p)k3 \begin{aligned} a &= \frac{2024p - k_3}{k_2} = \frac{2024p - k_3}{2024 - k_1 - k_3} \ge \frac{2024p - k_3}{2024 - k_3} = 1 - \frac{2024(1 - p)}{2024 - k_3} \\ b &= \frac{2024p - s_3}{s_2} = \frac{2024p - k_1 - k_2}{k_3} = \frac{k_3 - 2024(1 - p)}{k_3} = 1 - \frac{2024(1 - p)}{k_3} \end{aligned}
Since 2024p>k3=2024(k1+k2)=2024s3>2024(1p)2024p > k_3 = 2024 - (k_1 + k_2) = 2024 - s_3 > 2024(1 - p), we have
f(X,Y)=ayk2+k3+(1a)yk3=a+(1a)b=1(1a)(1b)=12024(1p)2024k32024(1p)k31p. \begin{aligned} f(X, Y) &= a y_{k_2+k_3} + (1-a) y_{k_3} = a + (1-a)b = 1 - (1-a)(1-b) \\ &= 1 - \frac{2024(1-p)}{2024-k_3} \cdot \frac{2024(1-p)}{k_3} \ge 1-p. \end{aligned}
So, we may assume that k1=s3k_1 = s_3 and by the symmetry, we may further assume that s1=k3s_1 = k_3. Then, k2=s2k_2 = s_2, and
(i) yk2+k3+1==y2024=1y_{k_2+k_3+1} = \dots = y_{2024} = 1
(ii) yk3+1==yk2+k3=by_{k_3+1} = \dots = y_{k_2+k_3} = b
(iii) y1==yk3=0y_1 = \dots = y_{k_3} = 0.

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.