uniolympiads English

IMC 2000, Ημέρα 2, Θέμα 3

Let p(z)p(z) be a polynomial of degree nn with complex coefficients. Prove that there exist at least n+1n + 1 complex numbers zz for which p(z)p(z) is 00 or 11.

Πρωτότυπο από το επίσημο PDFLet p(z) be a polynomial of degree n with complex coefficients. Prove that there exist at least n + 1 complex numbers z for which p(z) is 0 or 1.

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

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

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

Επίσημη λύση

Solution. The statement is not true if pp is a constant polynomial. We prove it only in the case if nn is positive.

For an arbitrary polynomial q(z)q(z) and complex number cc, denote by μ(q,c)\mu(q,c) the largest exponent α\alpha for which q(z)q(z) is divisible by (z−c)α(z-c)^\alpha. (With other words, if cc is a root of qq, then μ(q,c)\mu(q,c) is the root's multiplicity. Otherwise 0.)

Denote by S0S_0 and S1S_1 the sets of complex numbers zz for which p(z)p(z) is 0 or 1, respectively. These sets contain all roots of the polynomials p(z)p(z) and p(z)−1p(z)-1, thus

∑c∈S0μ(p,c)=∑c∈S1μ(p−1,c)=n.(1)\sum_{c\in S_0}\mu(p,c)=\sum_{c\in S_1}\mu(p-1,c)=n.\tag{1}

The polynomial p′p' has at most n−1n-1 roots (n>0n>0 is used here). This implies that

∑c∈S0∪S1μ(p′,c)≤n−1.(2)\sum_{c\in S_0\cup S_1}\mu(p',c)\le n-1.\tag{2}

If p(c)=0p(c)=0 or p(c)−1=0p(c)-1=0, then

μ(p,c)−μ(p′c)=1orμ(p−1,c)−μ(p′c)=1,(3)\mu(p,c)-\mu(p'c)=1\quad\text{or}\quad\mu(p-1,c)-\mu(p'c)=1,\tag{3}

respectively. Putting (1), (2) and (3) together we obtain

∣S0∣+∣S1∣=∑c∈S0(μ(p,c)−μ(p′,c))+∑c∈S1(μ(p−1,c)−μ(p′,c))==∑c∈S0μ(p,c)+∑c∈S1μ(p−1,c)−∑c∈S0∪S1μ(p′,c)≥n+n−(n−1)=n+1.\begin{aligned}\big|S_0\big|+\big|S_1\big|&=\sum_{c\in S_0}\big(\mu(p,c)-\mu(p',c)\big)+\sum_{c\in S_1}\big(\mu(p-1,c)-\mu(p',c)\big)=\\ &=\sum_{c\in S_0}\mu(p,c)+\sum_{c\in S_1}\mu(p-1,c)-\sum_{c\in S_0\cup S_1}\mu(p',c)\ge n+n-(n-1)=n+1.\end{aligned}

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

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

Πώς πήγε;