Prove that there exists a constant C>0 such that for every pair A,B of
positive integers, there is a real polynomial p(x) with
p(0)2>i=1∑Ap(−i)2+i=1∑Bp(i)2anddegp<CAB.
(proposed by Géza Kós, Loránd Eötvös University, Budapest)
Solution (official)
Without loss of generality we can assume A≥B.
Let k be an odd integer with 7AB≤k≤7AB+2,
and consider the Chebishev polynomial Tk(x).
Let ω=arccosA+BA−B, and let
u0=cosω0 be the greatest root of Tk(x) in the interval
[−1,A+BA−B]. Since k is odd, we have
Tk(0)=0, so u0≥0. Moreover,
ω≤ω0<ω+kπ.
The requested polynomial will be constructed as
p(x)=xTk(u0+A1+u0x).
Notice that for all x∈[−A,B] we have
u0+A1+u0x≥u0+A1+u0(−A)=−1andu0+A1+u0x≤A+BA−B+A1+A+BA−BB=1.
Hence, for x∈[−A,B] we have
Tk(u0+A1+u0x)≤1 and
∣p(x)∣≤∣x∣1, and therefore
i=1∑A∣p(−i)∣2+i=1∑B∣p(i)∣2<2i=1∑∞i21=3π2<4.
In order to estimate p(0), notice that
∣p(0)∣=A1+u0∣Tk′(u0)∣≥A1∣Tk′(u0)∣.
From cos(kt)=Tk(cost) we get
−ksin(kt)=Tk′(cost)⋅(−sint)T′(u0)=T′(cosω0)=ksinω0sin(kω0)=±sinω0k.
Since ω0≤min(ω+kπ,2π),sinω0<sinω+kπ≤1−cos2ω+7ABπ=1−(A+BA−B)2+ABπ/7=A+B2AB+ABπ/7<3AB.
Hence,
∣p(0)∣≥A1∣Tk′(u0)∣=A1⋅sinω0k>A⋅3AB7AB>2,
so indeed
∣p(0)∣2>4>i=1∑A∣p(−i)∣2+i=1∑B∣p(i)∣2.
The degree of p is
degp=k−1<7AB+1≤8AB.
So, C=8 is suitable.
How the field did
contestants scored
412
average (of 10)
0.10
solved (≥ 80%)
0.7%
near-0 (≤ 10%)
99.0%
discrimination
0.09
Score distribution (field cohort)
Computed on contestants with a meaningful total (field cohort); discrimination is the corrected item–total correlation.