Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Problem)
(→‎Problem: →‎Solution)
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.

Revision as of 03:42, 13 September 2017

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_IMO_Problems/Problem_3&oldid=87486"