IMC 2018 · Day 1 · P5

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

The minimal polynomial of $\omega$ over $\mathbb{Q}[x]$ is the cyclotomic polynomial $\Phi_{pq}(x) = \frac{(x^{pq} - 1)(x - 1)} {(x^p - 1)(x^q - 1)}$, so $\Phi_{pq}(x)$ divides $f(x)$. At the same time, $\Phi_{pq}(x)$ is the greatest common divisor of $s(x) = \frac{x^{pq} - 1}{x^p - 1} = \Phi_q(x^p)$ and $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 $f(x) = s(x) u(x) + t(x) v(x)$, with some polynomials $u(x), v(x)$. These polynomials can be replaced by $u^*(x) = u(x) + w(x) \frac{x^p - 1}{x - 1}$ and $v^*(x) = v(x) - w(x) \frac{x^q - 1}{x - 1}$, so without loss of generality we may assume that $\deg u \le p - 1$. Since $\deg a = pq - 1$, this forces $\deg v \le q - 1$.

Let $u(x) = u_{p-1} x^{p-1} + \dots + u_1 x + u_0$ and $v(x) = v_{q-1} x^{q-1} + \dots + v_1 x + v_0$. Denote by $(i, j)$ the unique integer $n \in \{0, 1, \dots, pq-1\}$ with $n \equiv i \pmod p$ and $n \equiv j \pmod q$. By the choice of $s$ and $t$, we have $a_{(i,j)} = u_i + v_j$. Then $$\begin{align*} P_1 P_2 + \dots + P_k P_{k+1} &= \sum_{i=0}^{k-1} a_{(i,i)} = \sum_{i=0}^{k-1} (u_i + v_i) = \frac1k \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} (u_i + v_j) \\ &= \frac1k \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} a_{(i,j)} \overset{(*)}{\ge} \frac1k \bigl( 1 + 2 + \dots + k^2 \bigr) = \frac{k^3 + k}{2} \end{align*}$$ where $(*)$ uses the fact that the numbers $(i, j)$ are pairwise different.