Bulgarian National Olympiad

Let $n=2k$ and $f(x)=x^{2k}+a_{2k-1}{x}^{2k-1}+\cdots +a_{1}x+a_0$, where $a_i$ are integers. First we prove that $f(x)$ can be written in the form $$f(x)=(x^k+b_{k-1}{x}^{k-1}+\cdots +b_{1}x+b_0{)}^2+r(x),$$ where $b_0,b_1,\dots ,b_{k-1}$ are rational numbers and $r(x)$ is a polynomial with rational coefficients and degree at most $k-1$. Indeed, the coefficient of $x^{k+t}$, $t=k-1,k-2,\dots ,1,0$, of the polynomial $(x^k+b_{k-1}{x}^{k-1}+\cdots +b_{1}x+b_0{)}^2$ is of the form $c_{k+t}=2b_t+{\sum }_{i=1}^{k-1-t}{b}_{t+i}{b}_{k-i}$. Inductively we find the values of

$b_{k-1},b_{k-2},\dots ,b_1,b_0$ such that $c_{k+t}=a_{k+t}$ for $t=k-1,k-2,\dots ,1,0$. After that we compute the coefficients of $r(x)$. If $f(x)=y^2$ has infinitely many integer solutions for which $x<0$, then $f_1(x)=y^2$ for $f_1(x)=f(-x)$ has infinitely many solutions for which $x>0$. Therefore we may assume that $f(x)=y^2$ has infinitely many solutions for which $x>0$. The equality $(x^k+b_{k-1}{x}^{k-1}+\cdots +b_{1}x+b_0{)}^2+r(x)=y^2$ can be written in the form $h^2(x)+M^{2}r(x)=(M{y}_x{)}^2$, where $M$ is the least common multiple of the denominators of $b_i$, $0\le i\le k-1$ and $h(x)$ is a polynomial with integer coefficients and leading coefficient $M$. Suppose that $r(x)$ is not identically 0 (if $b_i=0$ for all $i$, $0\le i\le k-1$, we set $M=1$). Case 1. Let the leading coefficient of $r(x)$ be positive. For large enough values of $x$ we have $(M{y}_x{)}^2>h^2(x)$, implying that $(M{y}_x{)}^2\ge (h(x)+1{)}^2$. Therefore $h^2(x)+M^{2}r(x)\ge (h(x)+1{)}^2$, i.e. $2h(x)\le M^{2}r(x)-1$. The latter inequality is not true for large enough values of $x$ since $h(x)$ is of degree $k$ whereas $r(x)$ is of degree at most $k-1$. Case 2. Let the leading coefficient of $r(x)$ be negative. For large enough values of $x$ we have $(M{y}_x{)}^2<h^2(x)$, implying $(M{y}_x{)}^2\le (h(x)-1{)}^2$. Therefore $h^2(x)+M^{2}r(x)\le (h(x)-1{)}^2$, i.e. $2h(x)\le -M^{2}r(x)+1$, which is not true for large enough values of $x$. Therefore $r(x)\equiv 0$, i.e. $f(x)=(x^k+b_{k-1}{x}^{k-1}+\cdots +b_{1}x+b_0{)}^2$. Since $f(x)$ has integer coefficients the same is true for $x^k+b_{k-1}{x}^{k-1}+\cdots +b_{1}x+b_0$ (Gauss Lemma).