IMO 2015 Team Selection Tests

a) Let $P(x)=c_n{x}^n+c_{n-1}{x}^{n-1}+\cdots +c_{1}x+c_0-2015$, then $P(\alpha )=0$. Suppose that when we divide $P(x)$ by $x^2+x-5$, we have a quotient $Q(x)$ and the remainder $R(x)=Ax+B$ with integers $A,B$. Then $$0=P(\alpha )=({\alpha }^2+\alpha -5)Q(\alpha )+A\alpha +B=A\alpha +B.$$ Since $\alpha$ is irrational, it follows that $A=B=0$. So $$P(x)=Q(x)(x^2+x-5).$$ When $x=1$, we have $P(1)=-3Q(1)$. This implies that $$c_0+c_1+\cdots +c_n\equiv 2015-3Q(1)\equiv 2(\mathrm{mod}3).$$

b) Suppose that $(c_0,c_1,\dots ,c_n)$ is the set of nonnegative integers such that (1) $c_0+c_1\alpha +\cdots +c_n{\alpha }^n=2015$; and (2) $c_0+c_1+\cdots +c_n$ is minimal. We note that $0\le c_i\le 4$ for all $i=0,1,\dots ,n-2$, since otherwise, the set $(c_0,\dots ,c_{i-1},c_i-5,c_{i+1}+1,c_{i+2}+1,c_{i+3},\dots ,c_n)$ also satisfies (1) and has a smaller sum, which is a contradiction. Let $Q(x)=a_{n-2}{x}^{n-2}+\cdots +a_0$. Since $P(x)=Q(x)(x^2+x-5)$, we have $$\begin{array}{rl}{c}_0-2015& =-5a_0\\ c_1& =-5a_1+a_0\\ c_2& =-5a_2+a_1+a_0\\ c_3& =-5a_3+a_2+a_1\\ \dots & \end{array}$$ Since $c_i\in \{0,1,2,3,4\}$, it follows from the first line that $c_0=0$ and $a_0=403$. From the second line, we have $c_1=3,a_1=80$. In general, $c_{i+1}=\text{MOD}(a_i+a_{i-1},5)$ and $a_{i+1}=\text{DIV}(a_i+a_{i-1},5)$. Therefore, we have $$\begin{array}{rl}\{a_0,a_1,\dots ,a_{11}\}& =\{403,80,96,35,26,12,7,3,2,1,0,0\}\\ \{c_0,c_1,\dots ,c_{11}\}& =\{0,3,3,1,1,1,3,4,0,0,3,1\}.\end{array}$$ Hence, the minimum value of $c_0+\cdots +c_n$ is $$0+3+3+1+1+1+3+4+0+0+3+1=20.$$