 International Mathematics Competition for University Students

July 22 – 28 2018, Blagoevgrad, Bulgaria

Home

Results
Individuals
Teams

Official IMC site

Problem 5

Problem 5. Let $\displaystyle p$ and $\displaystyle q$ be prime numbers with $\displaystyle p<q$. Suppose that in a convex polygon $\displaystyle P_1P_2\dots P_{pq}$ all angles are equal and the side lengths are distinct positive integers. Prove that

$\displaystyle P_1P_2+P_2P_3+\dots+P_kP_{k+1}\geq \dfrac{k^3+k}2$

holds for every integer $\displaystyle k$ with $\displaystyle 1\le k\le p$.

(Proposed by Ander Lamaison Vidarte, Berlin Mathematical School, Berlin)

Solution. Place the polygon in the complex plane counterclockwise, so that $\displaystyle P_2-P_1$ is a positive real number. Let $\displaystyle a_i=|P_{i+2}-P_{i+1}|$, which is an integer, and define the polynomial $\displaystyle f(x)=a_{pq-1}x^{pq-1}+\dots+a_1x+a_0$. Let $\displaystyle \omega=e^{\frac{2\pi i}{pq}}$; then $\displaystyle P_{i+1}-P_i=a_{i-1}\omega^{i-1}$, so $\displaystyle f(\omega)=0$.

The minimal polynomial of $\displaystyle \omega$ over $\displaystyle \mathbb{Q}[x]$ is the cyclotomic polynomial $\displaystyle \Phi_{pq}(x)=\frac{(x^{pq}-1)(x-1)}{(x^p-1)(x^q-1)}$, so $\displaystyle \Phi_{pq}(x)$ divides $\displaystyle f(x)$. At the same time, $\displaystyle \Phi_{pq}(x)$ is the greatest common divisor of $\displaystyle s(x)=\frac{x^{pq}-1}{x^p-1}=\Phi_q(x^p)$ and $\displaystyle t(x)=\frac{x^{pq}-1}{x^q-1}=\Phi_p(x^q)$, so by Bézout's identity (for real polynomials), we can write $\displaystyle f(x)=s(x)u(x)+t(x)v(x)$, with some polynomials $\displaystyle u(x), v(x)$. These polynomials can be replaced by $\displaystyle u^*(x)=u(x)+w(x)\frac{x^p-1}{x-1}$ and $\displaystyle v^*(x)=v(x)-w(x)\frac{x^q-1}{x-1}$, so without loss of generality we may assume that $\displaystyle \deg u\leq p-1$. Since $\displaystyle \deg a=pq-1$, this forces $\displaystyle \deg v\leq q-1$.

Let $\displaystyle u(x)=u_{p-1}x^{p-1}+\dots+u_1x+u_0$ and $\displaystyle v(x)=v_{q-1}x^{q-1}+\dots+v_1x+v_0$. Denote by $\displaystyle (i,j)$ the unique integer $\displaystyle n\in\{0, 1, \dots, pq-1\}$ with $\displaystyle n\equiv i \pmod p$ and $\displaystyle n \equiv j \pmod q$. By the choice of $\displaystyle s$ and $\displaystyle t$, we have $\displaystyle a_{(i,j)}=u_i+v_j$. Then

\displaystyle \begin{align*} P_1P_2+\dots+P_kP_{k+1}=&\sum\limits_{i=0}^{k-1}a_{(i,i)}=\sum\limits_{i=0}^{k-1}u_i+v_i=\frac{1}{k}\sum\limits_{i=0}^{k-1}\sum\limits_{j=0}^{k-1}\left(u_i+v_j\right)\\ =&\frac{1}{k}\sum\limits_{i=0}^{k-1}\sum\limits_{j=0}^{k-1}a_{(i,j)}\stackrel{(*)}{\geq}\frac1k\left(1+2+\dots+k^2\right)=\frac{k^3+k}{2} \end{align*}

where $\displaystyle (*)$ uses the fact that the numbers $\displaystyle (i,j)$ are pairwise different.