uniolympiads Ελληνικά

IMC 2000, Day 2, Problem 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.

Original from the official 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.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

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}

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?