## Problems Problem 1 A monic polynomial \( f(x) \) of fourth degree satisfies \( f(1)=10 \), \( f(2)=20 \) and \( f(3)=30 \). Determine \( f(12)+f(-8) \). The polynomial \( f(x)-10x \) vanishes at points \( x=1,2,3 \), so it is divisible by polynomial \( (x-1)(x-2)(x-3) \). The monicity implies that \( f(x)-10x=(x-1)(x-2)(x-3)(x-c) \) for some \( c \). Now \[ f(12)+f(-8) =11\cdot10\cdot9\cdot(12-c)+120+(-9)(-10)(-11)(-8-c)-80= %9\cdot10\cdot11\cdot20+40= 19840.\] Problem 2 Consider complex polynomials \( P(x)=x^n+a_1x^{n-1}+\cdots +a_n \) with the zeros \( x_1,\dots,x_n \), and \( Q(x)=x^n+b_1x^{n-1}+\cdots+ b_n \) with the zeros \( x_1^2,\dots,x_n^2 \). Prove that if \( a_1+a_3+a_5+\cdots \) and \( a_2+a_4+a_6+\cdots \) are real numbers, then \( b_1+b_2+\dots+b_n \) is also real. Note that \( Q(x^2)=\prod(x^2-x_i^2)= \prod(x-x_i)\cdot\prod(x+x_i)=(-1)^nP(x)P(-x) \). We now have \[ b_1+b_2+\cdots+b_n=Q(1)-1=(-1)^nP(1)P(-1)-1= (-1)^n(1+B-A)(1+B+A),\] where \( A=a_1+a_3+a_5+\cdots \) and \( B=a_2+a_4+\cdots \). Problem 3 If a polynomial \( P \) with real coefficients satisfies for all \( x \) \[ P(\cos x)=P(\sin x),\] show that there exists a polynomial \( Q \) such that \( P(x)=Q(x^4-x^2) \) for each \( x \). It follows from the conditions that \( P(-\sin x)=P(\sin x) \), i.e. \( P(-t)=P(t) \) for infinitely many \( t \), so the polynomials \( P(x) \) and \( P(-x) \) coincide. Therefore, \( P(x)=S(x^2) \) for some polynomial \( S \). Now \( S(\cos^2 x)=S(\sin^2 x) \) for all \( x \), i.e. \( S(1-t)=S(t) \) for infinitely many \( t \), which implies \( S(x)\equiv S(1-x) \). This is equivalent to \( R(x-\frac12)=R(\frac12-x) \), i.e. \( R(y)\equiv R(-y) \), where \( R \) is a polynomial such that \( S(x)=R(x-\frac12) \). Now \( R(x)= T(x^2) \) for some polynomial \( T \), and therefore \( P(x)=S(x^2)= R(x^2-\frac12)=T(x^4-x^2+\frac14)=Q(x^4-x^2) \) for some polynomial \( Q \). Problem 4 **(a)**Prove that for each \( n\in\mathbb{N} \) there is a polynomial \( T_n \) with integer coefficients and the leading coefficient \( 2^{n-1} \) such that \( T_n(\cos x)=\cos nx \) for all \( x \).**(b)**Prove that the polynomials \( T_n \) satisfy \( T_{m+n}+T_{m-n}= 2T_mT_n \) for all \( m,n\in\mathbb{N} \), \( m\geq n \).**(c)**Prove that the polynomial \( U_n \) given by \( U_n(2x)=2T_n(x) \) also has integer coefficients and satisfies \( U_n(x+x^{-1})=x^n+x^{-n} \).
The polynomials \( T_n(x) \) are known as the **(a)**Clearly, \( T_0(x)=1 \) and \( T_1(x)=x \) satisfy the requirements. For \( n> 1 \) we use induction on \( n \). Since \( \cos(n+1)x=2\cos x\cos nx-\cos(n-1)x \), we can define \( T_{n+1}=2T_1T_n-T_{n-1} \). Since \( T_1T_n \) and \( T_{n-1} \) are of degrees \( n+1 \) and \( n-1 \) respectively, \( T_{n+1} \) is of degree \( n+1 \) and has the leading coefficient \( 2\cdot2^n=2^{n+1} \). It also follows from the construction that all its coefficients are integers.**(b)**The relation follows from the identity \( \cos(m+n)x+\cos(m-n)x= 2\cos mx\cos nx \).**(c)**The sequence of polynomials \( (U_n) \) satisfies \( U_0(x)=2 \), \( U_1(x)=x \) and \( U_{n+1}=U_1U_n-U_{n-1} \), implying that each \( U_n \) has integer coefficients. The equality \( U_n(x+x^{-1})=x^n+x^{-n} \) holds for each \( x=\cos t+i\sin t \), and therefore it holds for all \( x \).
Problem 5 Prove that if \( \cos\frac pq\pi=a \) is a rational number for some \( p,q\in\mathbb{Z} \), then \( a\in\{0,\pm\frac12,\pm1\} \). Suppose that \( \cos\frac pq\pi=a \). It follows from the previous problem that \( U_q(2a)=2\cos p\pi=\pm2 \), where \( U_q \) is monic with integer coefficients, so \( 2a \) is an integer by Theorem 3.2. Problem 6 Prove that the maximum in absolute value of any monic real polynomial of \( n \)-th degree on \( [-1,1] \) is not less than \( \frac1{2^{n-1}} \). Note that equality holds for a multiple of the \( n \)-th Chebyshev polynomial \( T_n(x) \). The leading coefficient of \( T_n \) equals \( 2^{n-1} \), so \( C_n(x)=\frac1{2^{n-1}}T_n(x) \) is a monic polynomial and \[ |T_n(x)|=\frac1{2^{n-1}}\left|\cos(n\arccos x)\right|\leq \frac1{2^{n-1}}\quad\mbox{za }x\in[-1,1].\] Moreover, the values of \( T_n \) at points \( 1,\cos\frac{\pi}n,\cos\frac{2\pi}n,\cdots,\cos \frac{(n-1)\pi}n,-1 \) are alternately \( \frac1{2^{n-1}} \) and \( -\frac1{2^{n-1}} \). Now suppose that \( P\neq T_n \) is a monic polynomial such that \( \max_{-1\leq x\leq 1}|P(x)|< \frac1{2^{n-1}} \). Then \( P(x)-C_n(x) \) at points \( 1,\cos\frac{\pi}n,\cdots,\cos\frac{(n-1)\pi}n,-1 \) alternately takes positive and negative values. Therefore the polynomial \( P-C_n \) has at least \( n \) zeros, namely, at least one in every interval between two adjacent points. However, \( P-C_n \) is a polynomial of degree \( n-1 \) as the monomial \( x^n \) is canceled, so we have arrived at a contradiction. Problem 7 The polynomial \( P \) of \( n \)-th degree is such that, for each \( i=0,1,\dots,n \), \( P(i) \) equals the remainder of \( i \) modulo 2. Evaluate \( P(n+1) \). Since \( P^{[i]}(x)=(-2)^{i-1}(-1)^x \) for \( x=0,1,\dots,n-i \), we have \[ P(n+1)=P(n)+P^{[1]}(n-1)+\cdots+P^{[n]}(0)=\left\{ \begin{array}{ll}2^n,&2\nmid n;\\ 1-2^n,&2\mid n.\end{array} \right.\] Problem 8 A polynomial \( P(x) \) of \( n \)-th degree satisfies \( P(i)=\frac1i \) for \( i=1,2,\dots,n+1 \). Find \( P(n+2) \). By Theorem 5.2 we have \[ P(n+2)=\sum_{i=0}^n(-1)^{n-i}\frac1{i+1}\binom{n+1}i= \frac1{n+2}\sum_{i=0}^n(-1)^{n-i}\binom{n+2}{i+1}=\left\{ \begin{array}{cl}0,&2\nmid n;\\ \frac2{n+2},&2\mid n.\end{array} \right.\] Problem 9 Let \( P(x) \) be a real polynomial. **(a)**If \( P(x)\geq0 \) for all \( x \), show that there exist real polynomials \( A(x) \) and \( B(x) \) such that \( P(x)=A(x)^2+B(x)^2 \).**(b)**If \( P(x)\geq0 \) for all \( x\geq0 \), show that there exist real polynomials \( A(x) \) and \( B(x) \) such that \( P(x)=A(x)^2+xB(x)^2 \).
By Theorem 1.9, the polynomial \( P(x) \) can be factorized as \[ P(x)=(x-a_1)^{\alpha_1}\cdots(x-a_k)^{\alpha_k}\cdot(x^2-b_1x+c_1) \cdots(x^2-b_mx+c_m),\quad\quad\quad\quad\quad(\ast)\] where \( a_i,b_j,c_j \) are real numbers such that the \( a_i \) are different and the polynomials \( x^2-b_ix+c_i \) has no real zeros. The condition \( P(x)\geq0 \) for all \( x \) implies that the \( \alpha_i \) are even, whereas the condition \( P(x)\geq0 \) for \( x\geq0 \) implies that \( (\forall i) \) \( \alpha_i \) is even or \( a_i< 0 \). It is now easy to write each factor in \( (\ast) \) in the form \( A^2+B^2 \), respectively \( A^2+xB^2 \), so by the known formula \( (a^2+\gamma b^2)(c^2+\gamma d^2)=(ac+\gamma bd)^2+\gamma (ad-bc)^2 \) one can express their product \( P(x) \) in the desired form. Problem 10 Prove that if the equation \( Q(x)=ax^2+(c-b)x+(e-d)=0 \) has real roots greater than 1, where \( a,b,c,d,e\in\mathbb{R} \), then the equation \( P(x)=ax^4+bx^3+cx^2+dx+e=0 \) has at least one real root. Write \[ P(-x)=ax^4+(c-b)x^2+(e-d)-b(x^3-x^2)- d(x-1).\] If \( r \) is a root of the polynomial \( Q \), we have \( P\left(\sqrt r \right)=-(\sqrt r-1)(br+d) \) and \( P\left(-\sqrt r\right)=(\sqrt r+1)(br+d) \). Note that one of the two numbers \( P\left(\pm\sqrt r\right) \) positive and the other is negative (or both are zero). Hence there must be a zero of \( P \) between \( -\sqrt r \) and \( \sqrt r \). Problem 11 A monic polynomial \( P \) with real coefficients satisfies \( |P(i)|< 1 \). Prove that there is a root \( z=a+bi \) of \( P \) such that \( (a^2+b^2+1)^2< 4b^2+1 \). Let us write \( P(x)=(x-x_1)\cdots(x-x_m)(x^2-p_1x+q_1)\cdots (x^2-p_nx+q_n) \), where the polynomials \( x^2-p_kx+q_k \) have no real zeros. We have \[ 1> |P(i)|=\prod_{j=1}^m|i-x_j|\prod_{k=1}^n|-1-p_ki+ q_k|,\] and since \( |i-x_j|^2=1+x_j^2> 1 \) for all \( j \), we must have \( |-1-p_ki+q_k|< 1 \) for some \( k \), i.e. \[ p_k^2+(q_k-1)^2< 1.\quad\quad\quad\quad\quad (\ast)\] Let \( a\pm bi \) be the zeros of the polynomial \( x^2-p_kx+q_k \) (and also of the polynomial \( P \)). Then \( p_k=2a \) and \( q_k=a^2+b^2 \), so the inequality \( (\ast) \) becomes \( 4a^2+(a^2+b^2-1)^2< 1 \), which is equivalent to the desired inequality. Problem 12 For what real values of \( a \) does there exist a rational function \( f(x) \) that satisfies \( f(x^2)=f(x)^2-a \)? (A rational function is a quotient of two polynomials.) Write \( f \) in the form \( f=P/Q \), where \( P \) and \( Q \) are coprime polynomials and \( Q \) is monic. Comparing the leading coefficients we conclude that \( P \) is also monic. The condition of the problem becomes \( P(x^2)/Q(x^2)=P(x)^2/Q(x)^2-a \). Since \( P(x^2) \) and \( Q(x^2) \) are coprime (if they have a common zero, so do \( P \) and \( Q \)), it follows that \( Q(x^2)=Q(x)^2 \) and hence \( Q(x)=x^n \) for some \( n\in\mathbb{N} \). Therefore, \( P(x^2)=P(x)^2-ax^{2n} \). Let \( P(x)=a_0+a_1x+\cdots+a_{m-1}x^{m-1}+x^m \). Comparing the coefficients of \( P(x)^2 \) and \( P(x^2) \) we find that \( a_{n-1}=\cdots= a_{2m-n+1}=0 \), \( a_{2m-n}=a/2 \), \( a_1=\cdots=a_{m-1}=0 \) and \( a_0=1 \). Clearly, this is only possible if \( a=0 \), or \( a=2 \) and \( 2m-n=0 \). Problem 13 Find all polynomials \( P \) satisfying \( P(x^2+1)= P(x)^2+1 \) for all \( x \). Since \( P \) is symmetric with respect to point 0, it is easy to show that \( P \) is also a polynomial in \( x^2 \), so there is a polynomial \( Q \) such that \( P(x)=Q(x^2+1) \) or \( P(x)=xQ(x^2+1) \). Then \( Q((x^2+1)^2+1)=Q(x^2+1)^2-1 \), respectively \( (x^2+1)Q((x^2+1)^2+1)= x^2Q(x^2+1)^2+1 \). The substitution \( x^2+1=y \) yields \( Q(y^2+1)=Q(y)^2+1 \), resp. \( yQ(y^2+1)=(y-1)Q(y)^2+1 \). Suppose that \( yQ(y^2+1)=(y-1)Q(y)^2+1 \). Setting \( y=1 \) gives us \( Q(2)=1 \). Note that if \( a\neq0 \) and \( Q(a)=1 \) then \( aQ(a^2+1)=(a-1)+1 \), so \( Q(a^2+1)=1 \) as well. This leads to an infinite sequence \( (a_n) \) of points at which \( Q \) takes the value 1, given by \( a_0=2 \) and \( a_{n+1}=a_n^2+1 \). We conclude that \( Q\equiv1 \). We have shown that if \( Q\not\equiv1 \), then \( P(x)=Q(x^2+1) \). Now we easily come to all solutions: these are the polynomials of the form \( T(T(\cdots(T(x))\cdots)) \), where \( T(x)=x^2+1 \). Problem 14 Find all \( P \) for which \( P(x)^2-2=2P(2x^2-1) \). Let us denote \( P(1)=a \). We have \( a^2-2a-2=0 \). Since \( P(x)= (x-1)P_1(x)+a \), substituting in the original equation and simplifying yields \( (x-1)P_1(x)^2+2aP_1(x)=4(x+1)P_1(2x^2-1) \). For \( x=1 \) we have \( 2aP_1(1)=8P_1(1) \), which together with \( a\neq4 \) implies \( P_1(1)=0 \), i.e. \( P_1(x)=(x-1)P_2(x) \), so \( P(x)=(x-1)^2 P_2(x)+a \). Assume that \( P(x)=(x-1)^nQ(x)+a \), where \( Q(1)\neq0 \). Again substituting in the original equation and simplifying yields \( (x-1)^nQ(x)^2+2aQ(x)=2(2x+2)^nQ(2x^2-1) \), which implies that \( Q(1)=0 \), a contradiction. We conclude that \( P(x)=a \). Problem 15 If the polynomials \( P \) and \( Q \) each have a real root and \[ P(1+x+Q(x)^2)=Q(1+x+P(x)^2),\] prove that \( P\equiv Q \). At first, note that there exists \( x=a \) for which \( P(a)^2= Q(a)^2 \). This follows from the fact that, if \( p \) and \( q \) are real roots of \( P \) and \( Q \) respectively, then \( P(p)^2-Q(p)^2\leq 0\leq P(q)^2-Q(q)^2 \), whereby \( P^2-Q^2 \) is a continuous function. Then we also have \( P(b)=Q(b) \) for \( b=1+a+P(a)^2 \). Assuming that \( a \) is the largest real number with \( P(a)=Q(a) \), we come to an immediate contradiction. Problem 16 (IMO04.2) Find all polynomials \( P(x) \) with real coefficients satisfying the equality \[ P(a-b)+P(b-c)+P(c-a)=2P(a+b+c)\] for all triples \( (a,b,c) \) of real numbers such that \( ab+bc+ca=0 \). Let \( P(x)=a_0+a_1x+\dots+a_nx^n \). For every \( x \) the triple \( (a,b,c)=(6x,3x,-2x) \) satisfies the condition \( ab+bc+ca=0 \). The condition in \( P \) gives us \( P(3x)+P(5x)+P(-8x)=2P(7x) \) for all \( x \), so by comparing the coefficients on both sides we obtain \( K(i)= \left(3^i+5^i+(-8)^i-2\cdot 7^i\right)=0 \) whenever \( a_i\neq0 \). Since \( K(i) \) is negative for odd \( i \) and positive for \( i=0 \) and even \( i\geq6 \), \( a_i=0 \) is only possible for \( i=2 \) and \( i=4 \). Therefore, \( P(x)=a_2x^2+a_4x^4 \) for some real numbers \( a_2,a_4 \). It is easily verified that all such \( P(x) \) satisfy the conditions. Problem 17 A sequence of integers \( (a_n)_{n=1}^{\infty} \) has the property that \( m-n\mid a_m-a_n \) for any distinct \( m,n\in\mathbb{N} \). Suppose that there is a polynomial \( P(x) \) such that \( |a_n|< P(n) \) for all \( n \). Show that there exists a polynomial \( Q(x) \) such that \( a_n= Q(n) \) for all \( n \). Let \( d \) be the degree of \( P \). There is a unique polynomial \( Q \) of degree at most \( d \) such that \( Q(k)=a_k \) for \( k=1,2,\dots,d+1 \). Let us show that \( Q(n)=a_n \) for all \( n \). Let \( n> d+1 \). Polynomial \( Q \) might not have integral coefficients, so we cannot deduce that \( n-m\mid Q(n)-Q(m) \), but it certainly has rational coefficients, i.e. there is a natural number \( M \) for which \( R(x)=MQ(x) \) has integral coefficients. By the condition of the problem, \( M(a_n-Q(n))=M(a_n-a_k)-(R(n)-R(k)) \) is divisible by \( n-k \) for each \( k=1,2,\dots,d+1 \). Therefore, for each \( n \) we either have \( a_n=Q(n) \) or \[ L_n=\mbox{\rm{lcm}}(n-1,n-2,\dots,n-d-1)\leq M(a_n-Q(n))< Cn^d\] for some constant \( C \) independent of \( n \). Suppose that \( a_n\neq Q(n) \) for some \( n \). note that \( L_n \) is not less than the product \( (n-1)\cdots(n-d-1) \) divided by the product \( P \) of numbers \( \gcd(n-i,n-j) \) over all pairs \( (i,j) \) of different numbers from \( \{1,2,\dots,d+1\} \). Since \( \gcd(n-i,n-j)\leq i-j \), we have \( P\leq 1^d2^{d-1}\cdots d \). It follows that \[ (n-1)(n-2)\cdots(n-d-1)\leq PL_n< CPn^d,\] which is false for large enough \( n \) as the left hand side is of degree \( d+1 \). Thus, \( a_n=Q(n) \) for each sufficiently large \( n \), say \( n> N \). What happens for \( n\leq N \)? By the condition of the problem, \( M(a_n-Q(n))= M(a_n-a_k)-(R(n)-R(k)) \) is divisible by \( m-n \) for every \( m> N \), so it must be equal to zero. Hence \( a_n=Q(n) \) for all \( n \). Problem 18 (IMO06.5) Let \( P(x) \) be a polynomial of degree \( n> 1 \) with integer coefficients and let \( k \) be a natural number. Consider the polynomial \( Q(x)=P(P(\dots P(P(x))\dots)) \), where \( P \) is applied \( k \) times. Prove that there exist at most \( n \) integers \( t \) such that \( Q(t)=t \). We have shown in Problem 7 from the text that every such \( t \) satisfies \( P(P(t)) \) \( =t \). If every such \( t \) also satisfies \( P(t)=t \), the number of solutions is clearly at most \( \deg P=n \). Suppose that \( P(t_1)=t_2 \), \( P(t_2)=t_1 \), \( P(t_3)=t_4 \) i \( P(t_4)=t_3 \), where \( t_1\neq t_{2,3,4} \). By Theorem 2.1, \( t_1-t_3 \) divides \( t_2-t_4 \) and vice versa, from which we deduce that \( t_1-t_3=\pm(t_2-t_4) \). Assume that \( t_1-t_3=t_2-t_4 \), i.e. \( t_1-t_2=t_3-t_4=k\neq0 \). Since the relation \( t_1-t_4=\pm(t_2-t_3) \) similarly holds, we obtain \( t_1-t_3+k=\pm(t_1-t_3-k) \) which is impossible. Therefore, we must have \( t_1-t_3=t_4-t_2 \), which gives us \( P(t_1)+t_1=P(t_3)+t_3=c \) for some \( c \). It follows that all integral solutions \( t \) of the equation \( P(P(t))=t \) satisfy \( P(t)+t=c \), and hence their number does not exceed \( n \). Problem 19 If \( P \) and \( Q \) are monic polynomials such that \( P(P(x))=Q(Q(x)) \), prove that \( P\equiv Q \). Suppose that \( R=P-Q\neq0 \) and that \( 0< k\leq n-1 \) is the degree of \( R(x) \). Then \[ P(P(x))-Q(Q(x))=[Q(P(x))-Q(Q(x))]+R(P(x)).\] Writing \( Q(x)=x^n+\cdots+a_1x+a_0 \) yields \[ Q(P(x))-Q(Q(x))=[P(x)^n-Q(x)^n]+\cdots+ a_1[P(x)-Q(x)],\] where all the summands but the first have a degree at most \( n^2-n \), while the first summand equals \( R(x)\cdot\left(P(x)^{n-1}+P(x)^{n-2}Q(x)+ \cdots+Q(x)^{n-1}\right) \) and has the degree \( n^2-n+k \) with the leading coefficient \( n \). Therefore the degree of \( Q(P(x))-Q(Q(x)) \) is \( n^2-n+k \). On the other hand, the degree of the polynomial \( R(P(x)) \) equals \( kn< n^2-n+k \), from which we conclude that the difference \( P(P(x))-Q(Q(x)) \) has the degree \( n^2-n+k \), a contradiction. It remains to check the case of a constant \( R\equiv c \). Then the condition \( P(P(x))= Q(Q(x)) \) yields \( Q(Q(x)+c)=Q(Q(x))-c \), so the equality \( Q(y+c)=Q(y)-c \) holds for infinitely many values of \( y \); hence \( Q(y+c)\equiv Q(y)-c \) which is only possible for \( c=0 \) (to see this, just compare the coefficients). Problem 20 Let \( m,n \) and \( a \) be natural numbers and \( p< a-1 \) a prime number. Prove that the polynomial \( f(x)=x^m(x-a)^n+p \) is irreducible. Suppose that \( f(x)=g(x)h(x) \) for some nonconstant polynomials with integer coefficients. Since \( |f(0)|=p \), either \( |g(0)|=1 \) or \( |h(0)|=1 \) holds. Assume w.l.o.g. that \( |g(0)|=1 \). Write \( g(x)= (x-\alpha_1)\cdots(x-\alpha_k) \). Then \( |\alpha_1\cdots\alpha_k|=1 \). Since \( f(\alpha_i)-p=\alpha_i^m(\alpha_i-a)^n=-p \), taking the product over \( i=1,2,\dots,k \) yields \( |g(a)|^n=|(\alpha_1-a)\cdots (\alpha_k-a)|^n=p^k \). Since \( g(a) \) divides \( |g(a)h(a)|=p \), we must have \( |g(a)|=p \) and \( n=k \). However, \( a \) must divide \( |g(a)-g(0)|=p\pm 1 \), which is impossible. Problem 21 Prove that the polynomial \( F(x)=(x^2+x)^{2^n}+1 \) is irreducible for all \( n\in\mathbb{N} \). Suppose that \( F=G\cdot H \) for some polynomials \( G,H \) with integer coefficients. Let us consider this equality modulo 2. Since \( (x^2+x+1)^{2^n}\equiv F(x) \) (mod 2), we obtain \( (x^2+x+1)^{2^n}= g(x)h(x) \), where \( g\equiv G \) and \( h\equiv H \) are polynomials over \( \mathbb{Z}_2 \). The polynomial \( x^2+x+1 \) is irreducible over \( \mathbb{Z}_2[x] \), so there exists a natural number \( k \) for which \( g(x)=(x^2+x+1)^k \) and \( h(x)=(x^2+x+1)^{2^n-k} \); of course, these equalities hold in \( \mathbb{Z}_2[x] \) only. Back in \( \mathbb{Z}[x] \), these equalities become \( H(x)=(x^2+x+1)^{2^n-k}+2V(x) \) and \( G(x)=(x^2+x+ 1)^k+2U(x) \) for some polynomials \( U \) and \( V \) with integer coefficients. Thus, \[ [(x^2+x+1)^k+2U(x)][(x^2+x+1)^{2^n-k}+2V(x)]=F(x).\] Now if we set \( x=\epsilon=\frac{-1+i\sqrt3}2 \) in this equality, we obtain \( U(\epsilon)V(\epsilon)=\frac14F(\epsilon)=\frac12 \). However, this is impossible as the polynomial \( U(x)V(x) \) has integer coefficients, so \( U(\epsilon)V(\epsilon) \) must be of the form \( a+b\epsilon \) for some \( a,b\in\mathbb{Z} \) (since \( \epsilon^2=-1-\epsilon \)), which is not the case with \( \frac12 \). Problem 22 A polynomial \( P(x) \) has the property that for every \( y\in \mathbb{Q} \) there exists \( x\in\mathbb{Q} \) such that \( P(x)=y \). Prove that \( P \) is a linear polynomial. It is clear, for example by Theorem 4.1, that \( P \) must have rational coefficients. For some \( m\in\mathbb{N} \) the coefficients of the polynomial \( mP(x) \) are integral. Let \( p \) be a prime number not dividing \( m \). We claim that, if \( P \) is not linear, there is no rational number \( x \) for which \( P(x)=\frac1{mp} \). Namely, such an \( x \) would also satisfy \( Q(x)=mpP(x)-1=0 \). On the other hand, the polynomial \( Q(x) \) is irreducible because so is the polynomial \( x^nQ(1/x) \) by the Eisenstain criterion; indeed, all the coefficients of \( x^nQ(1/x) \) but the first are divisible by \( p \) and the constant term is not divisible by \( p^2 \). This proves our claim. Problem 23 Let \( P(x) \) be a monic polynomial of degree \( n \) whose zeros are \( i-1,i-2,\dots,i-n \) (where \( i^2=-1 \)) and let \( R(x) \) and \( S(x) \) be the real polynomials such that \( P(x)=R(x)+iS(x) \). Prove that the polynomial \( R(x) \) has \( n \) real zeros. Denote \( P(x)=P_n(x)=R_n(x)+iS_n(x) \). We prove by induction on \( n \) that all zeros of \( P_n \) are real; moreover, if \( x_1> x_2> \cdots > x_n \) are the zeros of \( R_n \) and \( y_1> y_2> \cdots> y_{n-1} \) the zeros of \( R_{n-1} \), then \[ x_1> y_1> x_2> y_2> \cdots> x_{n-1}> y_{n-1}> x_n.\] This statement is trivially true for \( n=1 \). Suppose that it is true for \( n-1 \). Since \( R_n+iS_n=(x-i+n)(R_{n-1}+iS_{n-1}) \), the polynomials \( R_n \) and \( S_n \) satisfy the recurrent relations \( R_n=(x+n)R_{n-1}+S_{n-1} \) and \( S_n=(x+n)S_{n-1}-R_{n-1} \). This gives us \[ R_n-(2x+2n-1)R_{n-1} +[(x+n-1)^2+1]R_{n-2}=0.\] If \( z_1> \cdots> z_{n-2} \) are the (real) zeros \( R_{n-2} \), by the inductive hypothesis we have \( z_{i-1}> y_i> z_i \). Since the value of \( R_{n-2} \) is alternately positive and negative on the intervals \( (z_1,+\infty) \), \( (z_2,z_1) \), etc, it follows that \( \mbox{sgn } R_{n-2}(y_i)=(-1)^{i-1} \). Now we conclude from the relation \( R_n(y_i)=-[(x+n-1)^2+1]R_{n-2}(y_i) \) that \[ \mbox{sgn } R_n(y_i)=(-1)^i,\] which means that the polynomial \( R_n \) has a zero on each of the \( n \) intervals \( (y_1,+\infty) \), \( (y_2,y_1) \), \( \dots \), \( (-\infty, y_{n-1}) \). This finishes the induction. Problem 24 Let \( a,b,c \) be natural numbers. Prove that if there exist coprime polynomials \( P,Q,R \) with complex coefficients such that \[ P^a+Q^b=R^c,\] then \( \frac1a+\frac1b+\frac1c> 1 \).
We first prove the following auxiliary statement.
Now we apply Lemma on the polynomials \( P^a \), \( Q^b \), and \( R^c \). We obtain that each of the numbers \( a\deg P \), \( b\deg Q \), \( c\deg R \) is less than \( \deg P+\deg Q+\deg R \), and therefore \[ \frac1a> \frac{\deg P}{\deg P+\deg Q+\deg R},\] etc. Adding these yields the desired inequality. Problem 25 Suppose that all zeros of a monic polynomial \( P(x) \) with integer coefficients are of module 1. Prove that there are only finitely many such polynomials of any given degree; hence show that all its zeros are actually roots of unity, i.e. \( P(x)\mid(x^n-1)^k \) for some natural \( n,k \). Let us fix \( \deg P=n \). Let \( P(x)=(x-z_1)\cdots(x-z_n)=x^n+ a_{n-1}x^{n-1}+\cdots+a_0 \), where \( |z_i|=1 \) for \( i=1,\dots,n \). By the Vieta formulas, \( a_{n-i}=\pm\sigma_i(z_1,\dots,z_n) \), which is a sum of \( \binom ni \) summands of modulus 1, and hence \( |a_{n-i}| \leq\binom ni \). Therefore, there are at most \( 2\binom mi+1 \) possible values of the coefficient of \( P(x) \) at \( x^{n-i} \) for each \( i \). Thus the number of possible polynomials \( P \) of degree \( n \) is finite. Now consider the polynomial \( P_r(x)=(x-z_1^r)\cdots(x-z_n^r) \) for each natural number \( r \). All coefficients of polynomial \( P_r \) are symmetric polynomials in \( z_i \) with integral coefficients, so by the Theorem 7.2 they must be integers. Therefore, every polynomial \( P_r \) satisfies the conditions of the problem, but there are infinitely many \( r \)’s and only finitely many such polynomials. We conclude that \( P_r(x)=P_s(x) \) for some distinct \( r,s\in\mathbb{N} \), and the main statement of the problem follows. |

2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |