uniolympiads English

IMC 2005, Ημέρα 1, Θέμα 4

Find all polynomials P(x)=anxn+an−1xn−1+⋯+a1x+a0P(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 (an≠0a_n \ne 0) satisfying the following two conditions:

(i) (a0,a1,…,an)(a_0, a_1, \dots, a_n) is a permutation of the numbers (0,1,…,n)(0, 1, \dots, n)

and

(ii) all roots of P(x)P(x) are rational numbers.

Πρωτότυπο από το επίσημο PDFFind all polynomials P (x) = a n x n + a n−1 x n−1 + ... + a 1 x + a 0 (a n 6 = 0) satisfying the following two conditions: (i) (a 0 , a 1 , ..., a n ) is a permutation of the numbers (0, 1, ..., n) and (ii) all roots of P (x) are rational numbers.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution 1. Note that P(x)P(x) does not have any positive root because P(x)>0P(x)>0 for every x>0x>0. Thus, we can represent them in the form −αi-\alpha_i, i=1,2,…,ni=1,2,\dots,n, where αi≥0\alpha_i\ge0. If a0≠0a_0\ne0 then there is a k∈N,1≤k≤n−1k\in\mathbb{N}, 1\le k\le n-1, with ak=0a_k=0, so using Viete's formulae we get

α1α2...αn−k−1αn−k+α1α2...αn−k−1αn−k+1+...+αk+1αk+2...αn−1αn=akan=0,\alpha_1\alpha_2...\alpha_{n-k-1}\alpha_{n-k}+\alpha_1\alpha_2...\alpha_{n-k-1}\alpha_{n-k+1}+...+\alpha_{k+1}\alpha_{k+2}...\alpha_{n-1}\alpha_n=\frac{a_k}{a_n}=0,
which is impossible because the left side of the equality is positive. Therefore a0=0a_0=0 and one of the roots of the polynomial, say αn\alpha_n, must be equal to zero. Consider the polynomial Q(x)=anxn−1+an−1xn−2+...+a1Q(x)=a_nx^{n-1}+a_{n-1}x^{n-2}+...+a_1. It has zeros −αi-\alpha_i, i=1,2,…,n−1i=1,2,\dots,n-1. Again, Viete's formulae, for n≥3n\ge3, yield:
α1α2...αn−1=a1an(1)\alpha_1\alpha_2...\alpha_{n-1}=\frac{a_1}{a_n}\tag{1}
α1α2...αn−2+α1α2...αn−3αn−1+...+α2α3...αn−1=a2an(2)\alpha_1\alpha_2...\alpha_{n-2}+\alpha_1\alpha_2...\alpha_{n-3}\alpha_{n-1}+...+\alpha_2\alpha_3...\alpha_{n-1}=\frac{a_2}{a_n}\tag{2}
α1+α2+...+αn−1=an−1an.(3)\alpha_1+\alpha_2+...+\alpha_{n-1}=\frac{a_{n-1}}{a_n}.\tag{3}
Dividing (2) by (1) we get
1α1+1α2+...+1αn−1=a2a1.(4)\frac{1}{\alpha_1}+\frac{1}{\alpha_2}+...+\frac{1}{\alpha_{n-1}}=\frac{a_2}{a_1}.\tag{4}
From (3) and (4), applying the AM-HM inequality we obtain
an−1(n−1)an=α1+α2+...+αn−1n−1≥n−11α1+1α2+...+1αn−1=(n−1)a1a2,\frac{a_{n-1}}{(n-1)a_n}=\frac{\alpha_1+\alpha_2+...+\alpha_{n-1}}{n-1}\ge\frac{n-1}{\frac{1}{\alpha_1}+\frac{1}{\alpha_2}+...+\frac{1}{\alpha_{n-1}}}=\frac{(n-1)a_1}{a_2},
therefore a2an−1a1an≥(n−1)2\frac{a_2a_{n-1}}{a_1a_n}\ge(n-1)^2. Hence n22≥a2an−1a1an≥(n−1)2\frac{n^2}{2}\ge\frac{a_2a_{n-1}}{a_1a_n}\ge(n-1)^2, implying n≤3n\le3. So, the only polynomials possibly satisfying (i)(i) and (ii)(ii) are those of degree at most three. These polynomials can easily be found and they are P(x)=xP(x)=x, P(x)=x2+2xP(x)=x^2+2x, P(x)=2x2+xP(x)=2x^2+x, P(x)=x3+3x2+2xP(x)=x^3+3x^2+2x and P(x)=2x3+3x2+xP(x)=2x^3+3x^2+x. □\square

Solution 2. Consider the prime factorization of PP in the ring Z[x]\mathbb{Z}[x]. Since all roots of PP are rational, PP can be written as a product of nn linear polynomials with rational coefficients. Therefore, all prime factor of PP are linear and PP can be written as

P(x)=∏k=1n(bkx+ck)P(x)=\prod_{k=1}^n(b_kx+c_k)
where the coefficients bk,ckb_k,c_k are integers. Since the leading coefficient of PP is positive, we can assume bk>0b_k>0 for all kk. The coefficients of PP are nonnegative, so PP cannot have a positive root. This implies ck≥0c_k\ge0. It is not possible that ck=0c_k=0 for two different values of kk, because it would imply a0=a1=0a_0=a_1=0. So ck>0c_k>0 in at least n−1n-1 cases.

Now substitute x=1x=1.

P(1)=an+⋯+a0=0+1+⋯+n=n(n+1)2=∏k=1n(bk+ck)≥2n−1;P(1)=a_n+\dots+a_0=0+1+\dots+n=\frac{n(n+1)}{2}=\prod_{k=1}^n(b_k+c_k)\ge2^{n-1};
therefore it is necessary that 2n−1≤n(n+1)22^{n-1}\le\frac{n(n+1)}{2}, therefore n≤4n\le4. Moreover, the number n(n+1)2\frac{n(n+1)}{2} can be written as a product of n−1n-1 integers greater than 1.

If n=1n=1, the only solution is P(x)=1x+0P(x)=1x+0.

If n=2n=2, we have P(1)=3=1⋅3P(1)=3=1\cdot3, so one factor must be xx, the other one is x+2x+2 or 2x+12x+1. Both x(x+2)=1x2+2x+0x(x+2)=1x^2+2x+0 and x(2x+1)=2x2+1x+0x(2x+1)=2x^2+1x+0 are solutions.

If n=3n=3, then P(1)=6=1⋅2⋅3P(1)=6=1\cdot2\cdot3, so one factor must be xx, another one is x+1x+1, the third one is again x+2x+2 or 2x+12x+1. The two polynomials are x(x+1)(x+2)=1x3+3x2+2x+0x(x+1)(x+2)=1x^3+3x^2+2x+0 and x(x+1)(2x+1)=2x3+3x2+1x+0x(x+1)(2x+1)=2x^3+3x^2+1x+0, both have the proper set of coefficients.

In the case n=4n=4, there is no solution because n(n+1)2=10\frac{n(n+1)}{2}=10 cannot be written as a product of 3 integers greater than 1.

Altogether we found 5 solutions: 1x+01x+0, 1x2+2x+01x^2+2x+0, 2x2+1x+02x^2+1x+0, 1x3+3x2+2x+01x^3+3x^2+2x+0 and 2x3+3x2+1x+02x^3+3x^2+1x+0.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;