Let $u$ be the positive root of the equation $x^2+x-4=0$. The polynomial $$P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0$$where $n$ is positive integer has non-negative integer coefficients and $P(u)=2017$. 1) Prove that $a_0+a_1+...+a_n\equiv 1\mod 2$. 2) Find the minimum possible value of $a_0+a_1+...+a_n$.
Problem
Source: 2017 Greece National Olympiad Problem 4
Tags: polynomial, algebra
Akatsuki1010
02.05.2017 18:11
1) Since $u$ is root of the function $P(x)=2017$ hence $x^{2}+x-4|P(x)-2017$ because $x^{2}+x-4$ is the polynomial with minimized degree has the irrational root $u$ and $P(x)$ is an integer polynomial. We obtain $-2|P(1)-2017$. Q.E.D
silouan
06.05.2017 14:07
Bump! What about 2) ?
hieudg
07.05.2017 21:25
(2) $$P(x)=Q(x).(x^2+x-4)+2017$$ $$Q(x)=b_{n-2}.x^{n-2}+b_{n-3}x^{n-3}+\ldots+b_1x+b_0$$with the coefficients of $Q(x)$ are: $$b_0=504$$$$b_1=126$$$$\ldots$$$$b_k=\bigg[\dfrac{b_{k-1}+b_{k-2}}{4}\bigg] $$$$\ldots$$$$b_{n-2}=\bigg[\dfrac{b_{n-3}+b_{n-4}}{4}\bigg]$$with $(k=2,...,n-2)$ We found that $b_{13}=0$, so: $$Q(x)=x^{12}+2x^{11}+3x^{10}+5x^9+8x^8+13x^7+21x^6+31x^5+56x^4+70x^3+157x^2+126x+504$$$\Rightarrow$ $P(1)_{min}=Q(1).-2+2017=997.-2+2017=23$. I thinks so
umaru
27.05.2017 18:14
hieudg wrote: (2) $$P(x)=Q(x).(x^2+x-4)+2017$$ $$Q(x)=b_{n-2}.x^{n-2}+b_{n-3}x^{n-3}+\ldots+b_1x+b_0$$with the coefficients of $Q(x)$ are: $$b_0=504$$$$b_1=126$$$$\ldots$$$$b_k=\bigg[\dfrac{b_{k-1}+b_{k-2}}{4}\bigg] $$$$\ldots$$$$b_{n-2}=\bigg[\dfrac{b_{n-3}+b_{n-4}}{4}\bigg]$$with $(k=2,...,n-2)$ We found that $b_{13}=0$, so: $$Q(x)=x^{12}+2x^{11}+3x^{10}+5x^9+8x^8+13x^7+21x^6+31x^5+56x^4+70x^3+157x^2+126x+504$$$\Rightarrow$ $P(1)_{min}=Q(1).-2+2017=997.-2+2017=23$. I thinks so You do that means $a1=a2=...=an=1$ but how you know that???
huynguyen
11.08.2017 17:38
hieudg wrote: (2) $$P(x)=Q(x).(x^2+x-4)+2017$$ $$Q(x)=b_{n-2}.x^{n-2}+b_{n-3}x^{n-3}+\ldots+b_1x+b_0$$with the coefficients of $Q(x)$ are: $$b_0=504$$$$b_1=126$$$$\ldots$$$$b_k=\bigg[\dfrac{b_{k-1}+b_{k-2}}{4}\bigg] $$$$\ldots$$ How can you get $b_k$ like this?
khbghvb
20.12.2017 15:11
Some one please give a solution to this question
ThE-dArK-lOrD
10.03.2018 16:22
Note that $x^2+x-4$ is the minimal polynomial of $u$, so $x^2-x+4\mid P(x)-2017$.
This gives $-2\mid P(1)-2017\implies P(1)\equiv 1\pmod{2}$, done.
It's clear that the must exists (one of) polynomial $P$ that gives minimum value of sum of coefficients.
For that $P$, we get that $0\leq a_i\leq 3$ for all $i\in \{ 0,1,2,...,n\}$, else we can add $(x^2+x-4)x^i$ and get polynomial with smaller sum of coefficients.
Note that there exists $Q\in \mathbb{Z}[x]$ that $P(x)=Q(x)(x^2+x-4)+2017$.
Let $Q(x)=b_{n-2}x^{n-2}+b_{n-3}x^{n-3}+...+b_0$.
We get
$$a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0=(b_{n-2}x^{n-2}+b_{n-3}x^{n-3}+...+b_0)(x^2+x-4)+2017.$$Comparing the coefficients gives us the following relations:
\begin{align*}
a_0=-4b_0+2017 &\implies a_0\equiv_4 2017&\implies a_0=1\; &\implies b_0=504\\
a_1= -4b_1+b_0&\implies a_1\equiv_4 b_0&\implies a_1=0 \; &\implies b_0=126\\
a_2= -4b_2+b_1+b_0&\implies a_2\equiv_4 b_1+b_0&\implies a_2=2\; &\implies b_2=157\\
a_3= -4b_3+b_2+b_1&\implies a_3\equiv_4 b_2+b_1&\implies a_3=3\; &\implies b_3=70\\
a_4= -4b_4+b_3+b_2&\implies a_4\equiv_4 b_3+b_2&\implies a_4=3\; &\implies b_3=56\\
\vdotswithin{ a_4= -4b_4+b_3+b_2 }&\implies \vdotswithin{ a_4\equiv_4 b_3+b_2} &\implies \vdotswithin{ a_4=3 } \; &\implies \vdotswithin{ b_3=56 }\\
a_{11}= -4b_{11}+b_{10}+b_{9}&\implies a_{11}\equiv_4 b_{10}+b_{9} &\implies a_{11}=0&\implies b_{11}=2\\
a_{12}= -4b_{12}+b_{11}+b_{10}&\implies a_{12}\equiv_4 b_{11}+b_{10} &\implies a_{12}=1&\implies b_{12}=1\\
\end{align*}Note that for two possible cases of $a_{13}$, to equal to $-4b_{13}+b_{12}+b_{11}$, or $b_{12}+b_{11}$, both satisfy $a_{13} \equiv_4 b_{12}+b_{11}$.
Now, $a_{13}\equiv_4 b_{12}+b_{11}$ forces $a_{13}=3$ so, it can be $a_{n-1}$ and lastly, $a_{14}=a_n=b_{n-2}=b_{12}=1$.
This gives minimal value of $\sum_{i=0}^{14}{a_i}=1+0+2+3+3+2+3+0+2+1+1+0+1+3+1=23$.