International Mathematics Competition
for University Students
2018

IMC2018: Day 1, 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.