IMO 2016 (Problem 3). Let $P=A_1A_2\cdots A_k$ be a convex polygon in the plane. The vertices $A_1, A_2, \cdots , 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$.
Here's my idea so far.
$k=3$ is a very easy case. My idea is to strong induct on $k$.
Assume that the statement for $3 \le k \le t$. We show this for $k=t+1$. Start with a $t+1$-gon on a circle. If one of the main diagonals of this polygon has square of its length as a multiple of $n$, we can slice the polygon by that diagonal. Then we are left with two polygon with squares of all of its side lengths as a multiple of $n$, and the polygons have no more than $t$ vertices each. So if we denote the areas as $S_1, S_2$, we have $n|2S_1$ and $n|2S_2$, so $n|2S$ and we are good.
So for this induction to work, we need to prove that for every polygon that satisfies the condition, there is at least one main diagonal which has the square of its length as a multiple of $n$.
For example, we can prove the case $k=4$ with just Ptolemy.
Can someone help me finish the solution using this idea, or maybe introduce a different solution?