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 "2008 USAMO Problems/Problem 4"

(Fixed link)
(will finish soon)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
(''Gregory Galparin'') Let <math>\mathcal{P}</math> be a convex polygon with <math>n</math> sides, <math>n\ge3</math>. Any set of <math>n - 3</math> diagonals of <math>\mathcal{P}</math> that do not intersect in the interior of the polygon determine a [i]triangulation[/i] of <math>\mathcal{P}</math> into <math>n - 2</math> triangles. If <math>\mathcal{P}</math> is regular and there is a triangulation of <math>\mathcal{P}</math> consisting of only isosceles triangles, find all the possible values of <math>n</math>.
+
(''Gregory Galparin'') Let <math>\mathcal{P}</math> be a convex polygon with <math>n</math> sides, <math>n\ge3</math>. Any set of <math>n - 3</math> diagonals of <math>\mathcal{P}</math> that do not intersect in the interior of the polygon determine a ''triangulation'' of <math>\mathcal{P}</math> into <math>n - 2</math> triangles. If <math>\mathcal{P}</math> is regular and there is a triangulation of <math>\mathcal{P}</math> consisting of only isosceles triangles, find all the possible values of <math>n</math>.
  
 
__TOC__
 
__TOC__
 
== Solution ==
 
== Solution ==
−
=== Solution 1 ===
+
We label the vertices of <math>\mathcal{P}</math> as <math>P_0, P_1, P_2, \ldots, P_n</math>. Consider a diagonal <math>d = \overline{P_a,P_{a+k}},\,k \le n/2</math> in the triangulation. This diagonal partitions <math>\mathcal{P}</math> into two regions <math>\mathcal{Q},\, \mathcal{R}</math>, and is the side of an isosceles triangle in both regions. [[Without loss of generality]] suppose the area of <math>Q</math> is less than the area of <math>R</math> (so the [[circumcenter|center]] of <math>P</math> does not lie in the interior of <math>Q</math>); it follows that the lengths of the edges and diagonals in <math>Q</math> are smaller than <math>d</math>. Thus <math>d</math> must the be the base of the isosceles triangle in <math>Q</math>, from which it follows that the isosceles triangle is <math>\triangle P_aP_{a+k/2}P_{a+k}</math>, and so <math>2|k</math>. Repeating this process on the legs of isosceles triangle (<math>\overline{P_aP_{a+k/2}},\,\overline{P_{a+k}P_{a+k/2}}</math>), it follows that <math>k = 2^m</math> for some positive integer <math>m</math>.
−
=== Solution 2 ===
+
 
 +
Now take the isosceles triangle <math>P_xP_yP_z</math> in the triangulation that contains the center of <math>\mathcal{P}</math> in its interior; if a diagonal passes through the center, selecting either of the isosceles triangles with that diagonal is an edge will suffice. Without loss of generality, suppose <math>P_xP_y = P_yP_z</math>. From our previous result, it follows that (sum of powers of <math>2</math>), eg
 +
<cmath>n = 2^{a+1} + 2^{b}</cmath>
 +
 
 +
We now claim that this condition is sufficient. Suppose WLOG that <math>a+1 \ge b</math>; then we rewrite this as
 +
<cmath>n = 2^{b}(2^{a-b+1}+1).</cmath>
 +
*''Lemma 1'': All <math>n = 2^k + 1</math> and <math>n=4</math> have triangulations that work.
 +
*''Lemma 2'': If <math>n</math>-sided polygon works, then <math>2n</math>-sided polygon works.
 +
By induction, it follows that we can cover all the <math>n</math>.
 +
 
 +
''Proof 1'': For <math>n = 3,4</math>, this is trivial. For <math>k>1</math>, construct <math>P_0P_{2^k}</math> and <math>P_{2^k+1}P_O</math>, then make midpoint isosceles triangles, repeat. 
 +
 
 +
 
 +
''Proof 2'': Construct every other edge, then reduce etc.
 +
 
 +
{{incomplete|solution}}
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Revision as of 17:19, 2 May 2008

Problem

(Gregory Galparin) Let $\mathcal{P}$ be a convex polygon with $n$ sides, $n\ge3$. Any set of $n - 3$ diagonals of $\mathcal{P}$ that do not intersect in the interior of the polygon determine a triangulation of $\mathcal{P}$ into $n - 2$ triangles. If $\mathcal{P}$ is regular and there is a triangulation of $\mathcal{P}$ consisting of only isosceles triangles, find all the possible values of $n$.

Solution

We label the vertices of $\mathcal{P}$ as $P_0, P_1, P_2, \ldots, P_n$. Consider a diagonal $d = \overline{P_a,P_{a+k}},\,k \le n/2$ in the triangulation. This diagonal partitions $\mathcal{P}$ into two regions $\mathcal{Q},\, \mathcal{R}$, and is the side of an isosceles triangle in both regions. Without loss of generality suppose the area of $Q$ is less than the area of $R$ (so the center of $P$ does not lie in the interior of $Q$); it follows that the lengths of the edges and diagonals in $Q$ are smaller than $d$. Thus $d$ must the be the base of the isosceles triangle in $Q$, from which it follows that the isosceles triangle is $\triangle P_aP_{a+k/2}P_{a+k}$, and so $2|k$. Repeating this process on the legs of isosceles triangle ($\overline{P_aP_{a+k/2}},\,\overline{P_{a+k}P_{a+k/2}}$), it follows that $k = 2^m$ for some positive integer $m$.

Now take the isosceles triangle $P_xP_yP_z$ in the triangulation that contains the center of $\mathcal{P}$ in its interior; if a diagonal passes through the center, selecting either of the isosceles triangles with that diagonal is an edge will suffice. Without loss of generality, suppose $P_xP_y = P_yP_z$. From our previous result, it follows that (sum of powers of $2$), eg \[n = 2^{a+1} + 2^{b}\]

We now claim that this condition is sufficient. Suppose WLOG that $a+1 \ge b$; then we rewrite this as \[n = 2^{b}(2^{a-b+1}+1).\]

  • Lemma 1: All $n = 2^k + 1$ and $n=4$ have triangulations that work.
  • Lemma 2: If $n$-sided polygon works, then $2n$-sided polygon works.

By induction, it follows that we can cover all the $n$.

Proof 1: For $n = 3,4$, this is trivial. For $k>1$, construct $P_0P_{2^k}$ and $P_{2^k+1}P_O$, then make midpoint isosceles triangles, repeat.


Proof 2: Construct every other edge, then reduce etc. 

Template:Incomplete

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

2008 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
  • <url>viewtopic.php?t=202905 Discussion on AoPS/MathLinks</url>
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_USAMO_Problems/Problem_4&oldid=25793"