# 2016 IMO Problems/Problem 3

## Problem

Let $P = A_1A_2 \cdots A_k$ be a convex polygon in the plane. The vertices $A_1,A_2,\dots, A_k$ have integral coordinates and lie on a circle. Let $S$ be the area of $P$. An odd positive integer $n$ is given such that the squares of the side lengths of $P$ are integers divisible by $n$. Prove that $2S$ is an integer divisible by $n$.

## Solution

Note that $2S$ is always an integer for any lattice polygon, so it remains to show that it is divisible by $n$. It clearly suffices to prove the problem for when $n=p^m$ is a prime power. We proceed using induction on $k$, with the base case of $k=3$ settled by Heron's formula: If $a,b,c$ are the side lengths of the triangle, then the square of the area is $S^2=\frac{2a^2b^2+2b^2c^2+2c^2a^2-a^4-b^4-c^4}{16}$. As $n\mid a^2,b^2,c^2$, we have that $n^2\mid S^2\implies n\mid S$, as desired.

For the inductive step, we claim that there exists a diagonal whose length squared is also divisible by $n$. Then, we may split $P$ into two polygons with less vertices and areas divisible by $n$ by assumption. Let $3\le i\le k-1$ be such that $v_p(A_1A_i^2)=q$ is minimized. By Ptolemy's Theorem on cyclic quadrilateral $A_1A_{i-1}A_iA_{i+1}$, we have that $\sqrt{A_1A_{i-1}^2\cdot A_iA_{i+1}^2}+\sqrt{A_1A_{i+1}^2\cdot A_iA_{i-1}^2}=\sqrt{A_1A_i^2\cdot A_{i-1}A_{i+1}^2}$, or $\sqrt{\frac{A_1A_{i-1}^2\cdot A_iA_{i+1}^2}{np^q}}+\sqrt{\frac{A_1A_{i+1}^2\cdot A_iA_{i-1}^2}{np^q}}=\sqrt{\frac{A_1A_i^2\cdot A_{i-1}A_{i+1}^2}{np^q}}$. As we have $p^q\mid AA_{i-1}^2,AA_{i+1}^2$ and $n\mid A_iA_{i+1}^2,A_iA_{i-1}^2$, the terms under the square roots on the LHS are integers, so the LHS is an algebraic integer. This implies that the term under the square root on the RHS is also an integer, so $np^q\mid A_1A_i^2\cdot A_{i-1}A_{i+1}^2\implies n\mid A_{i-1}A_{i+1}^2$, as desired.