Maths Olympiad Prep

Library / /19 of 92

Combinatorics Difficulty 5.9 AIME, harder Prove it Iran

Let 1<t<21 < t < 2 be a real number. Prove that for all sufficiently large positive integers like dd, there is a monic polynomial P(x)P(x) of degree dd, such that all of its coefficients are either +1+1 or 1-1 and
P(t)2019<1. |P(t) - 2019| < 1.

Solution

At first we shall prove following lemma:
Lemma. Let bnb_n be a sequence of positive real numbers satisfying
bn2b0+b1++bn1, b_n \leq 2b_0 + b_1 + \cdots + b_{n-1},
then for each real number zz where
z2b0+b1++bn, |z| \leq 2b_0 + b_1 + \cdots + b_n,
there are a0,a1,,an{1,1}a_0, a_1, \dots, a_n \in \{1, -1\} such that
zi=0naibi<b0. \left|z - \sum_{i=0}^{n} a_i b_i\right| < b_0.
Proof. Write the inequality z2b0+b1++bn|z| \leq 2b_0 + b_1 + \cdots + b_n in the form
zsgn(z)bn2b0+b1++bn1, |z - \operatorname{sgn}(z)b_n| \leq 2b_0 + b_1 + \cdots + b_{n-1},
then, proceed the proof by induction on nn. For sake of convenience, we also define sgn(0)=1\operatorname{sgn}(0) = 1. This completes our proof. \square

Back to the problem, define bi=tib_i = t^i, then it is easy to deduce that
bnb0=tn11+t++tn1=tn1t1=b0+b1++bn1. b_n - b_0 = t^n - 1 \le 1 + t + \cdots + t^{n-1} = \frac{t^n - 1}{t-1} = b_0 + b_1 + \cdots + b_{n-1}.
Moreover, choose dd such that td2019t^d \ge 2019, then
2019td2+t++td. 2019 \le t^d \le 2 + t + \cdots + t^d.
Hence, by the lemma, there are a0,a1,,ad{1,1}a_0, a_1, \dots, a_d \in \{1, -1\} such that
i=0daiti2019<1. \left| \sum_{i=0}^{d} a_i t^i - 2019 \right| < 1.
We are done.

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.