IMO 2016, Problem 3: Number Theory with the Area of a Polygon

Question

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$.

Also on http://www.artofproblemsolving.com/community/c6h1270467_imo_2016_problem_3

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?

Answer 1

The convex polygon $P$ is inscriptible in a circle of radius $r$ and its $k$ vertices are integer solutions of the equation $ x ^ 2 + y ^ 2 = r ^ 2 $. This equation has in general more integer solutions than $k$ because if $ (a, b) $ is solution so are the four points $ (± a, ± b) $ and P has been chosen such that their sides fulfill a certain condition of divisibility by $n$, odd integer. The total area $S$ of $P$ is equal to the sum of areas $S_{ij}$ of $k$ triangles (green in the figure below) and because of $\sin(\pi-x)=\sin(x)$ one has $$2S_{ij}=\text{ area of the triangle }\triangle{A_iA'_iA_j}$$ Let us remember that if a triangle has its vertices with integer coordinates, then the double of its area is an integer. In the case of $S_{ij}$ one has

$$S_{ij}=\frac12\cdot\left|\begin{array}{cc}0 & 0& 1\\a_i & b_i&1\\a_j&b_j&1\end{array}\right|$$ so $2S_{ij}$ is an integer.

Since $\triangle{A_iA'_iA_j}$ is a right triangle, we have $$2S{ij}=\frac{\overline{A_iA_j}\cdot\overline{A_jA'_i}}{2}$$

$$\overline{A_iA_j}^2=(a_j-a_i)^2+(b_j-b_i)^2=2r^2-2(a_ia_j+b_ib_j)=2r^2(1-\cos(\alpha_{ij}))\\\overline{A_jA'_i}^2=(a_j+a_i)^2+(b_j+b_i)^2=2r^2+2(a_ia_j+b_ib_j)=2r^2(1+\cos(\alpha_{ij}))$$ (we have used the formula $\vec{OA_i}*\vec{OA_j}=a_ia_j+b_ib_j=|\vec{OA_i}|\cdot|\vec{OA_j}|\cos(\alpha_{ij})$).

The odd integer $n$ can not divide $1-\cos(\alpha_{ij})$ whose unique integer values can be $0$ and $2$. Therefore $n$ must divide $2r^2$ so must divide $r^2$ since $n$ is odd.

Now the radius $r$ can be integer or pure quadratic (i.e. $r=a+b\sqrt{\theta}$ with $a=0$). The conclusion is that in both cases of $ r $ integer or quadratic, one has $$2S{ij}=\frac{\overline{A_iA_j}\cdot\overline{A_jA'_i}}{2}=r^2\sqrt{1-\cos^2(\alpha_{ij})}=r^2\sin(\alpha_{ij})$$ Consequently $2S_{ij}$ is an integer divisible by $n$ and so is for $$2S=2S_{12}+2S_{23}+\cdots+2S_{k1}$$