Olympiad Maths Prep

Track / Stage 8 / 32 of 180 #1732 of 2000

Problem 1732

IMO Shortlist mid-range; USAMO P2/P5
Algebra Difficulty 8.1 Prove it Team selection tests for IMO 2018 · Saudi Arabia · 2018

f(x)=(xF1)(xF2)(xF3030) f(x)=\left(x-F_{1}\right)\left(x-F_{2}\right) \ldots\left(x-F_{3030}\right)
with (Fn)\left(F_{n}\right) is the Fibonacci sequence, which defined as F1=1,F2=2,Fn+2=Fn+1+Fn,n1F_{1}=1, F_{2}=2, F_{n+2}= F_{n+1}+F_{n}, n \geq 1. Suppose that on the range (F1,F3030)\left(F_{1}, F_{3030}\right), the function f(x)|f(x)| takes on the maximum value at x=x0x=x_{0}. Prove that x0>22018x_{0}>2^{2018}.

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

We will prove that x0(F3029,F3030)x_{0} \in\left(F_{3029}, F_{3030}\right) by showing that for all x(F1,F3029]x^{*} \in\left(F_{1}, F_{3029}\right], there is some x(F3029,F3030)x^{**} \in\left(F_{3029}, F_{3030}\right) for which f(x)>f(x)\left|f\left(x^{**}\right)\right|>\left|f\left(x^{*}\right)\right|.

Indeed, if
x{F1,F2,,F3029} x^{*} \in\left\{F_{1}, F_{2}, \ldots, F_{3029}\right\}
then f(x)=0\left|f\left(x^{*}\right)\right|=0 which is obvious.

Suppose that x(Fk,Fk+1)x^{*} \in\left(F_{k}, F_{k+1}\right) for 1k30281 \leq k \leq 3028 then put m=xFkm=x^{*}-F_{k}, we choose x=F3030mx^{**}=F_{3030}-m. We need
f(x)>f(x)i=13030(xFi)>i=13030(xFi). \left|f\left(x^{**}\right)\right|>\left|f\left(x^{*}\right)\right| \Leftrightarrow\left|\prod_{i=1}^{3030}\left(x^{**}-F_{i}\right)\right|>\left|\prod_{i=1}^{3030}\left(x^{*}-F_{i}\right)\right|.
Each side has 3030 positive factors then we will make pair one of the left and one of the right such that the value of the right is bigger (except the case i=ki=k then xFk=m=xF3030\left|x^{*}-F_{k}\right|=m=\left|x^{**}-F_{3030}\right| ). For details:

1. If i=1,2,,ki=1,2, \ldots, k, it is clearly that xFi>xFi>0x^{**}-F_{i}>x^{*}-F_{i}>0.

2. If 1i3030k1 \leq i \leq 3030-k, we have xFk+i<xF3030i\left|x^{*}-F_{k+i}\right|<\left|x^{**}-F_{3030-i}\right|. Note that we just consider the separated ranges, i.e. k+i3030ik+i \leq 3030-i. Otherwise, some ranges are overlap then we remove that part, then
Fk+ix=(Fk+1x)+(Fk+2Fk+1)++(Fk+iFk+i1)<(xF3029)+(F3029F3028)++(F3030(i1)F3030i)=xF3030i \begin{aligned} & F_{k+i}-x^{*}=\left(F_{k+1}-x^{*}\right)+\left(F_{k+2}-F_{k+1}\right)+\cdots+\left(F_{k+i}-F_{k+i-1}\right) \\ & <\left(x^{**}-F_{3029}\right)+\left(F_{3029}-F_{3028}\right)+\cdots+\left(F_{3030-(i-1)}-F_{3030-i}\right) \\ & =x^{**}-F_{3030-i} \end{aligned}
Hence, the statement is proved. From here, we have
x0>F3029=15[(1+52)3030(152)3030]>15(1+52)3029>(1+52)3027. \begin{aligned} x_{0} & >F_{3029}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{3030}-\left(\frac{1-\sqrt{5}}{2}\right)^{3030}\right] \\ & >\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{3029}>\left(\frac{1+\sqrt{5}}{2}\right)^{3027} . \end{aligned}
It is easy to check that 1+52>223\frac{1+\sqrt{5}}{2}>2^{\frac{2}{3}} then substitute into the above inequality, we get x0>22018x_{0}>2^{2018}.

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