Given nonzero real numbers λ1,λ2,…,λ2025 and a real number d. Let X be a finite set of real numbers. Define the sets: A={(x1,…,x2025)∈X2025∣λ1x1+⋯+λ2025x2025=d}; B={(x1,…,x2024)∈X2024∣x1+⋯+x1012=x1013+⋯+x2024}; C={(x1,…,x2026)∈X2026∣x1+⋯+x1013=x1014+⋯+x2026}; where Xn denotes the set of all ordered tuples (x1,…,xn) with xi∈X (i=1,…,n). Prove: ∣A∣2≤∣B∣⋅∣C∣, where ∣Y∣ denotes the number of elements in the finite set Y.
Solution
Proof 1: Let Λ be the set consisting of ±λi for 1≤i≤2025. For positive integer n, define functions S,K:Λ2n→Z≥0 as: S(c1,…,c2n)=#{(x1,…,x2n)∈X2n∣c1x1+⋯+c2nx2n=0}, K(c1,…,c2n)=#{1≤i≤2n∣ci∈{±c1}}. Let T2n be the cardinality of: {(x1,…,x2n)∈X2n∣x1+⋯+xn=xn+1+⋯+x2n}, then T2n=S(c1,…,c1,−c1,…,−c1).
Lemma: The maximum value of function S is T2n.
Proof of Lemma: Assume the maximum value of S is M≥1, and let (c1,…,c2n) be a point in S−1({M}) where K attains its maximum. Let K(c1,…,c2n)=k, and assume ci∈{±c1} for 1≤i≤k. For real y, define: I1(y)=#{(x1,…,xn)∈Xn∣c1x1+⋯+cnxn=y}, I2(y)=#{(xn+1,…,x2n)∈Xn∣−cn+1xn+1−⋯−c2nx2n=y}. Then: S(c1,…,c2n)=y∑I1(y)I2(y). By Cauchy-Schwarz: M2=S(c1,…,c2n)2≤y∑I1(y)2y∑I2(y)2=S(c1,…,cn,−c1,…,−cn)⋅S(cn+1,…,c2n,−cn+1,…,−c2n)≤M2, implying S(c1,…,cn,−c1,…,−cn)=M. By maximality of K: k=K(c1,…,c2n)≥min{2k,2n}, thus k=2n. Therefore all ci∈{±c1}, and: M=T2n. This completes the lemma's proof.
Returning to the main problem, let n=1013. For real y, define: J1(y)=#{(x1,…,xn)∈Xn∣c1x1+⋯+cnxn=y}, J2(y)=#{(xn+1,…,x2n−1)∈Xn−1∣−cn+1xn+1−⋯−c2n−1x2n−1=y}. Similarly using Cauchy-Schwarz: A2=(y∑J1(y)J2(y))2≤y∑J1(y)2y∑J2(y)2≤S(c1,…,cn,−c1,…,−cn)⋅S(cn+1,…,c2n−1,−cn+1,…,−c2n−1). Combining with the lemma yields: A^2 ≤T2026⋅T2024 = B ⋅ C. □
Want a route through all this instead of an archive? The track
puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.