International Mathematics Competition for University Students

July 31 – August 6 2017, Blagoevgrad, Bulgaria

Home

Ivan is Watching You

Day 1
    Problem 1
    Problem 2
    Problem 3
    Problem 4
    Problem 5

Day 2
    Problem 6
    Problem 7
    Problem 8
    Problem 9
    Problem 10

Results
    Individuals
    Teams
    Leaders

Download
    Day 1 questions
    Day 1 solutions
    Day 2 questions
    Day 2 solutions
    Closing Ceremony
        Presentation

Official IMC site

Problem 5

5. Let $k$ and $n$ be positive integers with $n\ge k^2-3k+4$, and let $$ f(z)=z^{n-1}+c_{n-2}z^{n-2}+\ldots+c_0 $$ be a polynomial with complex coefficients such that $$c_0c_{n-2}=c_1c_{n-3}=\ldots=c_{n-2}c_0=0.$$ Prove that $f(z)$ and $z^n-1$ have at most $n-k$ common roots.

Proposed by: Vsevolod Lev and Fedor Petrov, St. Petersburg State University

Solution. Let $M=\{z:z^n=1\}$, $A=\{z\in M: f(z)\ne 0\}$ and $A^{-1}=\{z^{-1}: z\in A\}$. We have to prove $|A|\ge k$.

Claim. $$ A\cdot A^{-1}=M. $$ That is, for any $\eta\in M$, there exist some elements $a,b \in A$ such that $ab^{-1}=\eta$.

Proof. As is well-known, for every integer $m$, $$ \sum\limits_{z\in M} z^m = \begin{cases} n & \text{if $n|m$} \\ 0 & \text{otherwise.} \end{cases} $$ Define $c_{n-1}=1$ and consider $$ \sum_{z\in M} z^2 f(z) f(\eta z) = \sum_{z\in M} z^2 \sum_{j=0}^{n-1} c_jz^j \sum_{\ell=0}^{n-1} c_\ell (\eta z)^\ell = \sum_{j=0}^{n-1} \sum_{\ell=0}^{n-1} c_j c_\ell \eta^\ell \sum_{z\in M} z^{j+\ell+2} = $$ $$ = \sum_{j=0}^{n-1} \sum_{\ell=0}^{n-1} c_j c_\ell \eta^\ell \sum_{z\in M} \begin{Bmatrix} n & \text{if $n|j+\ell+2$} \\ 0 & \text{otherwise} \end{Bmatrix} = c_{n-1}^2n + \sum_{j=0}^{n-2} c_jc_{n-2-j}\eta^{n-2-j}n = n \ne 0. $$ Therefore there exists some $b\in M$ such that $f(b)\ne 0$ and $f(\eta b)\ne 0$, i.e. $b\in A$, and $a=\eta b\in A$, satisfying $ab^{-1}=\eta$.

By double-counting the elements of $M$, from the Claim we conclude $$ |A|\big(|A|-1\big) \ge \big|M\setminus\{1\}\big| = n-1 \ge k^2-3k+3 > (k-1)(k-2) $$ which shows $|A|>k-1$.


Discussion on ArtOfProblemSolving.com