International Mathematics Competition for University Students

July 22 – 28 2018, Blagoevgrad, Bulgaria


Ivan is Watching You
Ivan's Office

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

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


    Day 1 questions
    Day 1 solutions
    Day 2 questions
    Day 2 solutions
    Closing Ceremony

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.