Olympiad Maths Prep

Track / Stage 9 / 27 of 80 #1907 of 2000

Problem 1907

IMO P2/P5; hard shortlist
Algebra Difficulty 9.1 Prove it 2025 International Mathematical Olympiad China National Team Selection Test · China · 2025

Given nonzero real numbers λ1,λ2,,λ2025\lambda_1, \lambda_2, \dots, \lambda_{2025} and a real number dd. Let XX be a finite set of real numbers. Define the sets:
A={(x1,,x2025)X2025λ1x1++λ2025x2025=d}; A = \{(x_1, \dots, x_{2025}) \in X^{2025} \mid \lambda_1 x_1 + \dots + \lambda_{2025} x_{2025} = d\};
B={(x1,,x2024)X2024x1++x1012=x1013++x2024}; B = \{(x_1, \dots, x_{2024}) \in X^{2024} \mid x_1 + \dots + x_{1012} = x_{1013} + \dots + x_{2024}\};
C={(x1,,x2026)X2026x1++x1013=x1014++x2026}; C = \{(x_1, \dots, x_{2026}) \in X^{2026} \mid x_1 + \dots + x_{1013} = x_{1014} + \dots + x_{2026}\};
where XnX^n denotes the set of all ordered tuples (x1,,xn)(x_1, \dots, x_n) with xiXx_i \in X (i=1,,ni = 1, \dots, n).
Prove: A2BC|A|^2 \le |B| \cdot |C|, where Y|Y| denotes the number of elements in the finite set YY.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Proof 1: Let Λ\Lambda be the set consisting of ±λi\pm\lambda_i for 1i20251 \le i \le 2025. For positive integer nn, define functions S,K:Λ2nZ0S, K: \Lambda^{2n} \to \mathbb{Z}_{\ge 0} as:
S(c1,,c2n)=#{(x1,,x2n)X2nc1x1++c2nx2n=0}, S(c_1, \dots, c_{2n}) = \#\{(x_1, \dots, x_{2n}) \in X^{2n} \mid c_1 x_1 + \dots + c_{2n} x_{2n} = 0\},
K(c1,,c2n)=#{1i2nci{±c1}}. K(c_1, \dots, c_{2n}) = \#\{1 \le i \le 2n \mid c_i \in \{\pm c_1\}\}.
Let T2nT_{2n} be the cardinality of:
{(x1,,x2n)X2nx1++xn=xn+1++x2n}, \{(x_1, \dots, x_{2n}) \in X^{2n} \mid x_1 + \dots + x_n = x_{n+1} + \dots + x_{2n}\},
then T2n=S(c1,,c1,c1,,c1)T_{2n} = S(c_1, \dots, c_1, -c_1, \dots, -c_1).

Lemma: The maximum value of function SS is T2nT_{2n}.

Proof of Lemma: Assume the maximum value of SS is M1M \ge 1, and let (c1,,c2n)(c_1, \dots, c_{2n}) be a point in S1({M})S^{-1}(\{M\}) where KK attains its maximum.
Let K(c1,,c2n)=kK(c_1, \dots, c_{2n}) = k, and assume ci{±c1}c_i \in \{\pm c_1\} for 1ik1 \le i \le k. For real yy, define:
I1(y)=#{(x1,,xn)Xnc1x1++cnxn=y}, I_1(y) = \#\{(x_1, \dots, x_n) \in X^n \mid c_1 x_1 + \dots + c_n x_n = y\},
I2(y)=#{(xn+1,,x2n)Xncn+1xn+1c2nx2n=y}. I_2(y) = \#\{(x_{n+1}, \dots, x_{2n}) \in X^n \mid -c_{n+1}x_{n+1} - \dots - c_{2n}x_{2n} = y\}.
Then:
S(c1,,c2n)=yI1(y)I2(y). S(c_1, \dots, c_{2n}) = \sum_y I_1(y) I_2(y).
By Cauchy-Schwarz:
M2=S(c1,,c2n)2yI1(y)2yI2(y)2=S(c1,,cn,c1,,cn)S(cn+1,,c2n,cn+1,,c2n)M2, \begin{align*} M^2 &= S(c_1, \dots, c_{2n})^2 \le \sum_y I_1(y)^2 \sum_y I_2(y)^2 \\ &= S(c_1, \dots, c_n, -c_1, \dots, -c_n) \cdot S(c_{n+1}, \dots, c_{2n}, -c_{n+1}, \dots, -c_{2n}) \\ &\le M^2, \end{align*}
implying S(c1,,cn,c1,,cn)=MS(c_1, \dots, c_n, -c_1, \dots, -c_n) = M. By maximality of KK:
k=K(c1,,c2n)min{2k,2n}, k = K(c_1, \dots, c_{2n}) \ge \min\{2k, 2n\},
thus k=2nk = 2n. Therefore all ci{±c1}c_i \in \{\pm c_1\}, and:
M=T2n. M = T_{2n}.
This completes the lemma's proof.

Returning to the main problem, let n=1013n = 1013. For real yy, define:
J1(y)=#{(x1,,xn)Xnc1x1++cnxn=y}, J_1(y) = \#\{(x_1, \dots, x_n) \in X^n \mid c_1 x_1 + \dots + c_n x_n = y\},
J2(y)=#{(xn+1,,x2n1)Xn1cn+1xn+1c2n1x2n1=y}. J_2(y) = \#\{(x_{n+1}, \dots, x_{2n-1}) \in X^{n-1} \mid -c_{n+1}x_{n+1} - \dots - c_{2n-1}x_{2n-1} = y\}.
Similarly using Cauchy-Schwarz:
A2=(yJ1(y)J2(y))2yJ1(y)2yJ2(y)2S(c1,,cn,c1,,cn)S(cn+1,,c2n1,cn+1,,c2n1). A^2 = \left(\sum_y J_1(y)J_2(y)\right)^2 \le \sum_y J_1(y)^2 \sum_y J_2(y)^2 \\ \le S(c_1, \dots, c_n, -c_1, \dots, -c_n) \cdot S(c_{n+1}, \dots, c_{2n-1}, -c_{n+1}, \dots, -c_{2n-1}).
Combining with the lemma yields:
A^2 \le T_{2026} \cdot T_{2024} = B \cdot C. \quad \square **Proof 2:** (Based on solutions by Deng Leyan and Zhang Hengye) For non-zero real $p$, using Newton-Leibniz formula:
\lim_{T \to +\infty} \frac{1}{T} \int_0^T e^{ipt} dt = 0.
Thus: Thus:
\lim_{T \to +\infty} \frac{1}{T} \int_{0}^{T} e^{ipt} dt = \begin{cases} 0, & p \ne 0, \\ 1, & p = 0. \end{cases}
Let $f(t) = \sum_{x \in X} e^{ixt}$. Then:
|A| = \lim_{T \to +\infty} \frac{1}{T} \left| \int_{0}^{T} e^{-ibt} \prod_{j=1}^{2025} f(\lambda_j t) dt \right|.
ByHo¨ldersinequality: By Hölder's inequality:
\begin{align*}
|A| &= \lim_{T \to +\infty} \frac{1}{T} \left| \int_0^T e^{-ibt} \prod_{j=1}^{2025} f(\lambda_j t) dt \right| \\
&\le \lim_{T \to +\infty} \frac{1}{T} \int_0^T \prod_{j=1}^{2025} |f(\lambda_j t)| dt \\
&= \lim_{T \to +\infty} \frac{1}{T} \int_0^T \prod_{j=1}^{2025} (|f(\lambda_j t)|^{2025})^{\frac{1}{2025}} dt \\
&\le \lim_{T \to +\infty} \prod_{j=1}^{2025} \left( \frac{1}{T} \int_0^T |f(\lambda_j t)|^{2025} dt \right)^{\frac{1}{2025}} \\
&= \prod_{j=1}^{2025} \left( \lim_{T \to +\infty} \frac{1}{T} \int_0^T |f(|\lambda_j|t)|^{2025} dt \right)^{\frac{1}{2025}} \\
&= \prod_{j=1}^{2025} \left( \lim_{T \to +\infty} \frac{1}{|\lambda_j|T} \int_0^{|\lambda_j|T} |f(s)|^{2025} ds \right)^{\frac{1}{2025}} \\
&= \lim_{T \to +\infty} \frac{1}{T} \int_0^T |f(t)|^{2025} dt.
\end{align*}
Similarly: Similarly:
|B| = \lim_{T \to +\infty} \frac{1}{T} \int_{0}^{T} |f(t)|^{2024} dt,

|C| = \lim_{T \to +\infty} \frac{1}{T} \int_{0}^{T} |f(t)|^{2026} dt.
Finally,byCauchySchwarz: Finally, by Cauchy-Schwarz:
\begin{align*}
|B| \cdot |C| &= \lim_{T \to +\infty} \frac{1}{T^2} \int_0^T |f(t)|^{2024} dt \int_0^T |f(t)|^{2026} dt \\
&\ge \lim_{T \to +\infty} \frac{1}{T^2} \left( \int_0^T |f(t)|^{2025} dt \right)^2 \\
&= \left( \lim_{T \to +\infty} \frac{1}{T} \int_0^T |f(t)|^{2025} dt \right)^2 \\
&\ge |A|^2,
\end{align*}

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