# Difference between revisions of "2016 IMO Problems/Problem 3"

(→Problem) |
Muffin cowee (talk | contribs) |
||

Line 1: | Line 1: | ||

==Problem== | ==Problem== | ||

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

+ | |||

+ | ==Solution== | ||

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

+ | |||

+ | For the inductive step, we claim that there exists a diagonal whose length squared is also divisible by <math>n</math>. Then, we may split <math>P</math> into two polygons with less vertices and areas divisible by <math>n</math> by assumption. Let <math>3\le i\le k-1</math> be such that <math>v_p(A_1A_i^2)=q</math> is minimized. By Ptolemy's Theorem on cyclic quadrilateral <math>A_1A_{i-1}A_iA_{i+1}</math>, we have that <math>\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}</math>, or <math>\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}}</math>. As we have <math>p^q\mid AA_{i-1}^2,AA_{i+1}^2</math> and <math>n\mid A_iA_{i+1}^2,A_iA_{i-1}^2</math>, 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 <math>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</math>, as desired. |

## Latest revision as of 04:42, 13 September 2017

## Problem

Let be a convex polygon in the plane. The vertices have integral coordinates and lie on a circle. Let be the area of . An odd positive integer is given such that the squares of the side lengths of are integers divisible by . Prove that is an integer divisible by .

## Solution

Note that is always an integer for any lattice polygon, so it remains to show that it is divisible by . It clearly suffices to prove the problem for when is a prime power. We proceed using induction on , with the base case of settled by Heron's formula: If are the side lengths of the triangle, then the square of the area is . As , we have that , as desired.

For the inductive step, we claim that there exists a diagonal whose length squared is also divisible by . Then, we may split into two polygons with less vertices and areas divisible by by assumption. Let be such that is minimized. By Ptolemy's Theorem on cyclic quadrilateral , we have that , or . As we have and , 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 , as desired.