Maths Olympiad Prep

Library / /61 of 61

Algebra Difficulty 7.7 National Olympiad, round 2 Prove it Greece

Let ξ\xi be the positive root of the equation x2+x4=0x^2 + x - 4 = 0. The polynomial P(x)=anxn+an1xn1++a1x+a0P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0, where nn is a positive integer, has nonnegative integer coefficients and P(ξ)=2017P(\xi) = 2017.
(i) Prove that: a0+a1++an1(mod2)a_0 + a_1 + \dots + a_n \equiv 1 \pmod{2}
(ii) Find the least possible value of the sum: a0+a1++ana_0 + a_1 + \dots + a_n.

Solution

(i) Since ξ=1+172\xi = \frac{-1 + \sqrt{17}}{2} is irrational and the polynomial Fx=Px2017F x = P x - 2017 has rational coefficients and ξ\xi as a root, then it will have also the conjugate 1172\frac{-1 - \sqrt{17}}{2} as a root, and therefore it is divided by the polynomial φx=x2+x4\varphi x = x^2 + x - 4. It comes easily from the identity
Fx=Px2017=x2+x4Qx+κx+λ, F x = P x - 2017 = x^2 + x - 4 Q x + \kappa x + \lambda,
by putting x=ξx = \xi. Then κξ+λ=0\kappa \xi + \lambda = 0 which gives κ=λ=0\kappa = \lambda = 0, taking in mind that ξ\xi is irrational. Therefore there exists a polynomial QxQ x such that:
Fx=Px2017=x2+x4Qxanxn+an1xn1++a1x+a02017=x2+x4Qx(1) \begin{aligned} F x = P x - 2017 &= x^2 + x - 4 \mathcal{Q} x \\ \Leftrightarrow a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0 - 2017 &= x^2 + x - 4 \mathcal{Q} x \end{aligned} \quad (1)
From (1) for x=1x=1 we get:
a0+a1++an2017=2Q1a0+a1++an=20172Q11mod 2 \begin{aligned} & a_0 + a_1 + \dots + a_n - 2017 = -2Q \quad 1 \\ \Rightarrow \quad a_0 + a_1 + \dots + a_n = 2017 - 2Q \quad 1 \equiv 1 \quad \text{mod } 2 \end{aligned}

(ii) We consider the set a0,a1,...,ana_0, a_1, ..., a_n with elements nonnegative integers satisfying the following:
(α) anξn+an1ξn1+...+a1ξ+a0=2017a_n \xi^n + a_{n-1} \xi^{n-1} + ... + a_1 \xi + a_0 = 2017 and
(β) the sum a0+a1+...+ana_0 + a_1 + ... + a_n is minimal.
First we observe that: 0ai30 \le a_i \le 3, for all i=1,2,...,n2i = 1, 2, ..., n-2.
In fact, if it was not true for someone i=1,2,...,n2i = 1, 2, ..., n-2, then the elements of the set a0,...,ai1,ai4,ai1+1,ai+1+1,ai+2+1,ai+3,...,ana_0, ..., a_{i-1}, a_{i-4}, a_{i-1}+1, a_{i+1}+1, a_{i+2}+1, a_{i+3}, ..., a_n would be nonnegative integers, it would satisfy relation (α), while the sum of its elements would be less than of a1+a2+...+ana_1 + a_2 + ... + a_n, which is absurd.
Let now Qx=bn2xn2+bn1xn1+...+b1x+b0Q x = b_{n-2} x^{n-2} + b_{n-1} x^{n-1} + ... + b_1 x + b_0. Then from the identity
anxn+an1xn1+...+a1x+a02017=x2+x4bn2xn2+bn3xn3+...+b1x+b0a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0 - 2017 = x^2 + x - 4 \quad b_{n-2} x^{n-2} + b_{n-3} x^{n-3} + ... + b_1 x + b_0 we get the equations:
a 0 - 2017 = -4b 0 a 1 = -4b 1 + b 0 a 2 = -4b 2 + b 1 + b 0 a 3 = -4b 3 + b 2 + b 1 ........................................ a n-2 = -4b n-2 + b n-3 + b n-4 a n-1 = b n-2 + b n-3 a n = b n-2 a 0 - 2017 = -4b 0 a 1 - b 0 = -4b 1 a 2 - b 1 - b 0 = -4b 2 a 3 - b 2 - b 1 = -4b 3 ........................................ a n-2 - b n-3 - b n-4 = -4b n-2 a n-1 - b n-2 = b n-3 a n = b n-2\text{a 0 - 2017 = -4b 0 a 1 = -4b 1 + b 0 a 2 = -4b 2 + b 1 + b 0 a 3 = -4b 3 + b 2 + b 1 ........................................ a n-2 = -4b n-2 + b n-3 + b n-4 a n-1 = b n-2 + b n-3 a n = b n-2 a 0 - 2017 = -4b 0 a 1 - b 0 = -4b 1 a 2 - b 1 - b 0 = -4b 2 a 3 - b 2 - b 1 = -4b 3 ........................................ a n-2 - b n-3 - b n-4 = -4b n-2 a n-1 - b n-2 = b n-3 a n = b n-2}
In general we have: ai+2bi+1bi=4bi+2a_{i+2} - b_{i+1} - b_i = -4b_{i+2}, for all i=0,1,...,n4i = 0, 1, ..., n-4
Since 0ai30 \le a_i \le 3, for all i=1,2,...,n2i = 1, 2, ..., n-2, from the first equation we have a0=1a_0 = 1 and b0=504b_0 = 504. From the second equation we get a1=0a_1 = 0 and b1=126b_1 = 126. From the third equation we get a2=2a_2 = 2 and b2=157b_2 = 157. Continuing in the same way we find the sets
b0,b1,b2,...b14=504,126,157,70,56,31,21,13,8,5,3,2,1,0,0b_0, b_1, b_2, ... b_{14} = 504, 126, 157, 70, 56, 31, 21, 13, 8, 5, 3, 2, 1, 0, 0
a0,a1,a2,...a14=1,0,2,3,3,2,3,0,2,1,1,0,1,3,1a_0, a_1, a_2, ... a_{14} = 1, 0, 2, 3, 3, 2, 3, 0, 2, 1, 1, 0, 1, 3, 1
Therefore the least possible value of the sum a0+a1+...+ana_0 + a_1 + ... + a_n is 23.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.