Olympiad Maths Prep

Library / /4 of 4

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:
{a02017=4b0a1=4b1+b0a2=4b2+b1+b0a3=4b3+b2+b1\multicolumn5c........................................an2=4bn2+bn3+bn4an1=bn2+bn3an=bn2}{a02017=4b0a1b0=4b1a2b1b0=4b2a3b2b1=4b3\multicolumn5c........................................an2bn3bn4=4bn2an1bn2=bn3an=bn2} \left\{ \begin{array}{l} 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 \\ \multicolumn{5}{c}{\text{........................................}} \\ 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} \end{array} \right\} \Leftrightarrow \left\{ \begin{array}{l} 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 \\ \multicolumn{5}{c}{\text{........................................}} \\ 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} \end{array} \right\}
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.

Looking for a route rather than 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.