Maths Olympiad Prep

Library / /4 of 19

Algebra Difficulty 6.0 National olympiad Prove it Ukraine

Assume P1,P2,,PnP_1, P_2, \dots, P_n (n>10n > 10) are pairwise different polynomials with coefficients 11, 00, or 1-1 and such that do not have integer roots. Additionally, i=1,n\forall i = \overline{1,n} Pi(5)n22|P_i(5)| \le \frac{n^2}{2}. Prove that Pi+Pj=Pk+PlP_i + P_j = P_k + P_l for some 1i,j,k,ln1 \le i,j,k,l \le n and {i,j}{k,l}\{i, j\} \neq \{k, l\}. Note that ii may be equal jj, and kk may be equal ll.

Solution

Since the polynomials P1,,PnP_1, \dots, P_n do not have integer roots then Pi(0)0P_i(0) \neq 0 for any i=1,ni = \overline{1,n} and Pi(0)=±1P_i(0) = \pm 1. Let us consider all pairs of polynomials PkP_k and PjP_j, such that kjk \neq j and Pk(0)=Pj(0)P_k(0) = P_j(0). For each pair of polynomials we determine Qk,j=PkPjQ_{k,j} = P_k - P_j. If aa and bb are the number of polynomials such that Pi(0)=1P_i(0) = 1 and Pi(0)=1P_i(0) = -1 respectively, then the number of polynomials Qk,jQ_{k,j} will be
2Ca2+2Cb2=a(a1)+b(b1)=a2+b2n12(a+b)2n=12n(n2). 2C_a^2 + 2C_b^2 = a(a-1) + b(b-1) = a^2 + b^2 - n \ge \frac{1}{2}(a+b)^2 - n = \frac{1}{2}n(n-2).
Note that coefficients of polynomials Qk,jQ_{k,j} may be only equal to 2,1,0,1,2-2, -1, 0, 1, 2. Hence, the coefficients of Qk,jQi,lQ_{k,j} - Q_{i,l} cannot be bigger than 44 by absolute value. Therefore Qk,j(5)=Qi,l(5)Q_{k,j}(5) = Q_{i,l}(5) if and only if Qk,jQ_{k,j} and Qi,lQ_{i,l} are the same, because nN\forall n \in \mathbb{N}, 5n>4(5n1++5+1)5^n > 4(5^{n-1}+\dots+5+1).

It is easy to see that Qk,j(5)Q_{k,j}(5) is divisible by 55. Moreover, Qk,j(5)0Q_{k,j}(5) \neq 0 (otherwise Qk,jQ_{k,j} is the zero polynomial which is impossible) and Qk,j(5)Pi(5)+Pj(5)n2|Q_{k,j}(5)| \le |P_i(5)| + |P_j(5)| \le n^2. Therefore, Qk,j(5)Q_{k,j}(5) can take at most 25n2\frac{2}{5}n^2 different values. But the overall number of polynomials Qk,jQ_{k,j} is bigger than 25n2\frac{2}{5}n^2, because
12n(n2)>25n25(n2)>4nn>10. \frac{1}{2}n(n-2) > \frac{2}{5}n^2 \Leftrightarrow 5(n-2) > 4n \Leftrightarrow n > 10.
This implies that Qk,j(5)=Qi,l(5)Qk,j=Qi,lQ_{k,j}(5) = Q_{i,l}(5) \Rightarrow Q_{k,j} = Q_{i,l} for some i,j,k,li,j,k,l. Consequently, Pi+Pj=Pk+PlP_i + P_j = P_k + P_l for some 1i,j,k,ln1 \le i,j,k,l \le n, {i,j}{k,l}\{i, j\} \neq \{k, l\} which finishes the proof.

Want a route through all this instead of 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.