uniolympiads English

IMC 2007, Ημέρα 1, Θέμα 6

How many nonzero coefficients can a polynomial P(z)P(z) have if its coefficients are integers and ∣P(z)∣≤2|P(z)| \le 2 for any complex number zz of unit length?

Πρωτότυπο από το επίσημο PDFHow many nonzero coefficients can a polynomial P (z) have if its coefficients are integers and |P (z)| ≤ 2 for any complex number z of unit length?

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

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

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

Επίσημη λύση

Solution. We show that the number of nonzero coefficients can be 0, 1 and 2. These values are possible, for example the polynomials P0(z)=0P_0(z)=0, P1(z)=1P_1(z)=1 and P2(z)=1+zP_2(z)=1+z satisfy the conditions and they have 0, 1 and 2 nonzero terms, respectively.

Now consider an arbitrary polynomial P(z)=a0+a1z+…+anznP(z)=a_0+a_1z+\ldots+a_nz^n satisfying the conditions and assume that it has at least two nonzero coefficients. Dividing the polynomial by a power of zz and optionally replacing p(z)p(z) by −p(z)-p(z), we can achieve a0>0a_0>0 such that conditions are not changed and the number of nonzero terms is preserved. So, without loss of generality, we can assume that a0>0a_0>0.

Let Q(z)=a1z+…+an−1zn−1Q(z)=a_1z+\ldots+a_{n-1}z^{n-1}. Our goal is to show that Q(z)=0Q(z)=0.

Consider those complex numbers w0,w1,…,wn−1w_0,w_1,\dots,w_{n-1} on the unit circle for which anwkn=∣an∣a_nw_k^n=|a_n|; namely, let

wk={e2kπi/nif an>0e(2k+1)πi/nif an<0(k=0,1,…,n).w_k=\begin{cases}e^{2k\pi i/n}&\text{if }a_n>0\\e^{(2k+1)\pi i/n}&\text{if }a_n<0\end{cases}\qquad(k=0,1,\dots,n).
Notice that
∑k=0n−1Q(wk)=∑k=0n−1Q(w0e2kπi/n)=∑j=1n−1ajw0j∑k=0n−1(e2jπi/n)k=0.\sum_{k=0}^{n-1}Q(w_k)=\sum_{k=0}^{n-1}Q(w_0e^{2k\pi i/n})=\sum_{j=1}^{n-1}a_jw_0^j\sum_{k=0}^{n-1}(e^{2j\pi i/n})^k=0.
Taking the average of polynomial P(z)P(z) at the points wkw_k, we obtain
1n∑k=0n−1P(wk)=1n∑k=0n−1(a0+Q(wk)+anwkn)=a0+∣an∣\frac1n\sum_{k=0}^{n-1}P(w_k)=\frac1n\sum_{k=0}^{n-1}\big(a_0+Q(w_k)+a_nw_k^n\big)=a_0+|a_n|
and
2≥1n∑k=0n−1∣P(wk)∣≥∣1n∑k=0n−1P(wk)∣=a0+∣an∣≥2.2\ge\frac1n\sum_{k=0}^{n-1}\big|P(w_k)\big|\ge\left|\frac1n\sum_{k=0}^{n-1}P(w_k)\right|=a_0+|a_n|\ge2.
This obviously implies a0=∣an∣=1a_0=|a_n|=1 and ∣P(wk)∣=∣2+Q(wk)∣=2\big|P(w_k)\big|=\big|2+Q(w_k)\big|=2 for all kk. Therefore, all values of Q(wk)Q(w_k) must lie on the circle ∣2+z∣=2|2+z|=2, while their sum is 0. This is possible only if Q(wk)=0Q(w_k)=0 for all kk. Then polynomial Q(z)Q(z) has at least nn distinct roots while its degree is at most n−1n-1. So Q(z)=0Q(z)=0 and P(z)=a0+anznP(z)=a_0+a_nz^n has only two nonzero coefficients.

Remark. From Parseval's formula (i.e. integrating ∣P(z)∣2=P(z)P(z)‾|P(z)|^2=P(z)\overline{P(z)} on the unit circle) it can be obtained that

∣a0∣2+…+∣an∣2=12π∫02π∣P(eit)∣2 dt≤12π∫02π4 dt=4.(4)|a_0|^2+\ldots+|a_n|^2=\frac1{2\pi}\int_0^{2\pi}\big|P(e^{it})\big|^2\,dt\le\frac1{2\pi}\int_0^{2\pi}4\,dt=4. \tag{4}
Hence, there cannot be more than four nonzero coefficients, and if there are more than one nonzero term, then their coefficients are ±1\pm1.

It is also easy to see that equality in (4) cannot hold two or more nonzero coefficients, so it is sufficient to consider only polynomials of the form 1±xm±xn1\pm x^m\pm x^n. However, we do not know (yet :-)) any simpler argument for these cases than the proof above.

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

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

Πώς πήγε;