IMO 2016 Shortlisted Problems

Let $P=A_1{A}_2\dots A_k$ and let $A_{k+i}=A_i$ for $i⩾1$. By the Shoelace Formula, the area of any convex polygon with integral coordinates is half an integer. Therefore, $2S$ is an integer. We shall prove by induction on $k⩾3$ that $2S$ is divisible by $n$. Clearly, it suffices to consider $n=p^t$ where $p$ is an odd prime and $t⩾1$.

For the base case $k=3$, let the side lengths of $P$ be $\sqrt{na}$, $\sqrt{nb}$, $\sqrt{nc}$ where $a,b,c$ are positive integers. By Heron's Formula, $$16S^2=n^2\left(2ab+2bc+2ca-a^2-b^2-c^2\right).$$ This shows $16S^2$ is divisible by $n^2$. Since $n$ is odd, $2S$ is divisible by $n$.

Assume $k⩾4$. If the square of length of one of the diagonals is divisible by $n$, then that diagonal divides $P$ into two smaller polygons, to which the induction hypothesis applies. Hence we may assume that none of the squares of diagonal lengths is divisible by $n$. As usual, we denote by ${\nu }_p(r)$ the exponent of $p$ in the prime decomposition of $r$. We claim the following.

- Claim. ${\nu }_p\left(A_1{A}_m^2\right)>{\nu }_p\left(A_1{A}_{m+1}^2\right)$ for $2⩽m⩽k-1$.

Proof. The case $m=2$ is obvious since ${\nu }_p\left(A_1{A}_2^2\right)⩾p^t>{\nu }_p\left(A_1{A}_3^2\right)$ by the condition and the above assumption.

Suppose ${\nu }_p\left(A_1{A}_2^2\right)>{\nu }_p\left(A_1{A}_3^2\right)>\cdots >{\nu }_p\left(A_1{A}_m^2\right)$ where $3⩽m⩽k-1$. For the induction step, we apply Ptolemy's Theorem to the cyclic quadrilateral $A_1{A}_{m-1}{A}_m{A}_{m+1}$ to get $$A_1{A}_{m+1}\times A_{m-1}{A}_m+A_1{A}_{m-1}\times A_m{A}_{m+1}=A_1{A}_m\times A_{m-1}{A}_{m+1}$$ which can be rewritten as $$\begin{array}{rl}{A}_1{A}_{m+1}^2\times A_{m-1}{A}_m^2=& A_1{A}_{m-1}^2\times A_m{A}_{m+1}^2+A_1{A}_m^2\times A_{m-1}{A}_{m+1}^2\\ & -2A_1{A}_{m-1}\times A_m{A}_{m+1}\times A_1{A}_m\times A_{m-1}{A}_{m+1}\end{array}\text{\hspace{1em}(1)}$$ From this, $2A_1{A}_{m-1}\times A_m{A}_{m+1}\times A_1{A}_m\times A_{m-1}{A}_{m+1}$ is an integer. We consider the component of $p$ of each term in (1). By the inductive hypothesis, we have ${\nu }_p\left(A_1{A}_{m-1}^2\right)>{\nu }_p\left(A_1{A}_m^2\right)$. Also, we have ${\nu }_p\left(A_m{A}_{m+1}^2\right)⩾p^t>{\nu }_p\left(A_{m-1}{A}_{m+1}^2\right)$. These give $$\begin{array}{c}{\nu }_p\left(A_1{A}_{m-1}^2\times A_m{A}_{m+1}^2\right)>{\nu }_p\left(A_1{A}_m^2\times A_{m-1}{A}_{m+1}^2\right)\end{array}\text{\hspace{1em}(2)}$$ Next, we have ${\nu }_p\left(4A_1{A}_{m-1}^2\times A_m{A}_{m+1}^2\times A_1{A}_m^2\times A_{m-1}{A}_{m+1}^2\right)={\nu }_p\left(A_1{A}_{m-1}^2\times A_m{A}_{m+1}^2\right)+{\nu }_p\left(A_1{A}_m^2\times A_{m-1}{A}_{m+1}^2\right)>2{\nu }_p\left(A_1{A}_m^2\times A_{m-1}{A}_{m+1}^2\right)$ from (2). This implies $$\begin{array}{c}{\nu }_p\left(2A_1{A}_{m-1}\times A_m{A}_{m+1}\times A_1{A}_m\times A_{m-1}{A}_{m+1}\right)>{\nu }_p\left(A_1{A}_m^2\times A_{m-1}{A}_{m+1}^2\right)\end{array}\text{\hspace{1em}(3)}$$ Combining (1), (2) and (3), we conclude that $${\nu }_p\left(A_1{A}_{m+1}^2\times A_{m-1}{A}_m^2\right)={\nu }_p\left(A_1{A}_m^2\times A_{m-1}{A}_{m+1}^2\right)$$ By ${\nu }_p\left(A_{m-1}{A}_m^2\right)⩾p^t>{\nu }_p\left(A_{m-1}{A}_{m+1}^2\right)$, we get ${\nu }_p\left(A_1{A}_{m+1}^2\right)<{\nu }_p\left(A_1{A}_m^2\right)$. The Claim follows by induction.