Difference between revisions of "2008 USAMO Problems/Problem 4"

Revision as of 19:01, 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. We show that $k$ must have the form $2^{m}$ for some nonnegative integer $m$ .

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 all 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$ (if we allow degeneracy, then we can also let $m=0$ ).

$[asy] defaultpen(linewidth(0.7)+fontsize(10)); int n = 17; real r = 1; real rad = pi/2; pair pt(real k=0) { return (r*expi(rad-2*pi*k/n)); } for(int i=0; i<n; ++i){ dot(pt(i)); draw(pt(i)--pt(i+1)); } draw(pt()--pt(8)); draw(pt()--pt(4)--pt(8),linewidth(0.7)+linetype("4 4")); draw(pt()--pt(2)--pt(4),linewidth(0.7)+linetype("4 4")); label("$d$",(pt()+pt(8))/2,WNW); label("$\mathcal{Q}$",(pt()+pt(6))/2,SE); label("$\mathcal{R}$",(pt()+pt(10))/2,W); label("$P_0$",pt(),N); label("$P_1$",pt(1),NNE); label("$P_8$",pt(8),S); label("$P_{16}$",pt(-1),NNW); label("$\cdots$",pt(2),NE); [/asy]$

$[asy] defaultpen(linewidth(0.7)+fontsize(10)); int n = 20; real r = 1; real rad = pi/2; pair pt(real k=0) { return (r*expi(rad-2*pi*k/n)); } for(int i=0; i<n; ++i){ dot(pt(i)); draw(pt(i)--pt(i+1)); } draw(pt()--pt(8)--pt(16)--cycle); label("$O$",(0,0),W); dot((0,0)); draw(pt()--pt(4)--pt(8)--pt(6)--pt(4)--pt(2)--pt()--pt(18)--pt(16)--pt(12)--pt(8)--pt(10)--pt(12)--pt(14)--pt(16),linewidth(0.3)+linetype("4 4")); label("$P_0$",pt(),N); label("$P_1$",pt(1),NNE); label("$P_{19}$",pt(-1),NNW); label("$P_{8}$",pt(8),SE); label("$P_{16}$",pt(16),W); label("$\cdots$",pt(2),NE); [/asy]$

An example for $n=17$ ,
$k=8$

An isosceles triangle containing
the center for
$n=20$ , $(x,y,z) = (0,8,16)$

Now take the isosceles triangle $P_xP_yP_z,\,0 \le x < y < z < n$ in the triangulation that contains the center of $\mathcal{P}$ in its interior; if a diagonal passes through the center, select either of the isosceles triangles with that diagonal as an edge. Without loss of generality, suppose $P_xP_y = P_yP_z$ . From our previous result, it follows that there are $2^a$ edges of $P$ on the minor arcs of $P_xP_y,\, P_yP_z$ and $2^b$ edges of $P$ on the minor arc of $P_zP_x$ , for positive integers $a,\,b$ . Therefore, we can write $n = 2 \cdot 2^a + 2^b = 2^{a+1} + 2^{b},$ so $n$ must be the sum of two powers of $2$ .

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

Lemma 1: All regular polygons with $n = 2^k + 1$ or $n=4$ have triangulations that meet the conditions.
Lemma 2: If a regular polygon with $n$ sides has a working triangulation, then the regular polygon with $2n$ sides also has a triangulation that meets the conditions.

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

Proof 1: For $n = 3,4$ , this is trivial. For $k>1$ , we construct the diagonals of equal length $\overline{P_0P_{2^{k-1}}}$ and $\overline{P_{2^{k-1}+1}P_0}$ . This partitions $\mathcal{P}$ into $3$ regions: an isosceles $\triangle P_0P_{2^{k-1}}P_{2^{k-1}+1}$ , and two other regions. For these two regions, we can recursively construct the isosceles triangles defined above in the second paragraph. It follows that we have constructed $2(2^{k-1}-1) + (1) = 2^k-1 = n-2$ isosceles triangles with non-intersecting diagonals, as desired. $\ \square$

$[asy] defaultpen(linewidth(0.7)+fontsize(10)); int n = 17; real r = 1; real rad = pi/2; pair pt(real k=0) { return (r*expi(rad-2*pi*k/n)); } for(int i=0; i<n; ++i){ dot(pt(i)); draw(pt(i)--pt(i+1)); } /* could rewrite recursively, if someone wants to do .. */ draw(pt(8)--pt()--pt(9)); draw(pt()--pt(4)--pt(8)); draw(pt()--pt(2)--pt(4)); draw(pt()--pt(1)--pt(2)); draw(pt(2)--pt(3)--pt(4)); draw(pt(4)--pt(6)--pt(8)); draw(pt(4)--pt(5)--pt(6)); draw(pt(6)--pt(7)--pt(8)); draw(pt(9)--pt(13)--pt(17)); draw(pt(9)--pt(11)--pt(13)); draw(pt(9)--pt(10)--pt(11)); draw(pt(11)--pt(12)--pt(13)); draw(pt(13)--pt(15)--pt(17)); draw(pt(13)--pt(14)--pt(15)); draw(pt(15)--pt(16)--pt(17)); label("$P_0$",pt(),N); label("$P_1$",pt(1),NNE); label("$P_{16}$",pt(-1),NNW); label("$\cdots$",pt(2),NE); [/asy]$
An example for $n=17 = 2^{4}+1$

Proof 2: We construct the diagonals $\overline{P_0P_2},\ \overline{P_2P_4},\ \ldots \overline{P_{2n-2}P_0}$ . This partitions $\mathcal{P}$ into $n$ isosceles triangles of the form $\triangle P_{2k}P_{2k+1}P_{2k+2}$ , as well as a central regular polygon with $n$ sides. However, we know that there exists a triangulation for the $n$ -sided polygon that yields $n-2$ isosceles triangles. Thus, we have created $(n) + (n-2) = 2n-2$ isosceles triangles with non-intersecting diagonals, as desired. $\ \square$

$[asy] defaultpen(linewidth(0.7)+fontsize(10)); int n = 10; real r = 1; real rad = pi/2; pair pt(real k=0) { return (r*expi(rad-2*pi*k/n)); } for(int i=0; i<n; ++i){ dot(pt(i)); draw(pt(i)--pt(i+1)); } draw(pt()--pt(2)--pt(4)--pt(6)--pt(8)--cycle); draw(pt()--pt(4)--pt(6)--cycle,linewidth(0.5)+linetype("4 4")); label("$P_0$",pt(),N); label("$P_1$",pt(1),NNE); label("$P_{2}$",pt(2),NE); label("$P_{3}$",pt(3),E); label("$P_{4}$",pt(4),SE); label("$P_{5}$",pt(5),S); label("$P_{6}$",pt(6),SW); label("$P_{7}$",pt(7),W); label("$P_{8}$",pt(8),NW); label("$P_{9}$",pt(9),NNW); [/asy]$
An example for $n=10,\, n/2 = 5$

In summary, the answer is all $n$ that can be written in the form $2^{a+1} + 2^{b},\, a,b \ge 0$ . Alternatively, this condition can be expressed as either $n=2^{k},\, k \ge 2$ (this is the case when $a+1 = b$ ) or $n$ is the sum of two distinct powers of $2$ , where $1= 2^0$ is considered a power of $2$ . $\ \blacksquare$

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>

@@ Line 71: / Line 71: @@
-''Proof 1'': For <math>n = 3,4</math>, this is trivial. For <math>k>1</math>, we construct the diagonals of equal length <math>\overline{P_0P_{2^k}}</math> and <math>\overline{P_{2^k+1}P_0}</math>. This partitions <math>\mathcal{P}</math> into <math>3</math> regions: an isosceles <math>\triangle P_0P_{2^k}P_{2^k+1}</math>, and two other regions. For these two regions, we can recursively construct the isosceles triangles defined above in the second paragraph. It follows that we have constructed <math>2(2^{k-1}-1) + (1) = 2^k-1 = n-2</math> isosceles triangles with non-intersecting diagonals, as desired. <math>\ \square</math>
+''Proof 1'': For <math>n = 3,4</math>, this is trivial. For <math>k>1</math>, we construct the diagonals of equal length <math>\overline{P_0P_{2^{k-1}}}</math> and <math>\overline{P_{2^{k-1}+1}P_0}</math>. This partitions <math>\mathcal{P}</math> into <math>3</math> regions: an isosceles <math>\triangle P_0P_{2^{k-1}}P_{2^{k-1}+1}</math>, and two other regions. For these two regions, we can recursively construct the isosceles triangles defined above in the second paragraph. It follows that we have constructed <math>2(2^{k-1}-1) + (1) = 2^k-1 = n-2</math> isosceles triangles with non-intersecting diagonals, as desired. <math>\ \square</math>
 <center><asy>
@@ Line 109: / Line 109: @@
 </asy><br /><span style="font-size:85%">An example for <math>n=17 = 2^{4}+1</math></span></center>
-''Proof 2'': We construct the diagonals <math>\overline{P_0P_2},\ \overline{P_2P_4},\ \overline{P_{2n-2}P_0}</math>. This partitions <math>\mathcal{P}</math> into <math>n</math> isosceles triangles of the form <math>\triangle P_{2k}P_{2k+1}P_{2k+2}</math>, as well as a central regular polygon with <math>n</math> sides. However, we know that there exists a triangulation for the <math>n</math>-sided polygon that yields <math>n-2</math> isosceles triangles. Thus, we have created <math>(n) + (n-2) = 2n-2</math> isosceles triangles with non-intersecting diagonals, as desired. <math>\ \square</math>
+''Proof 2'': We construct the diagonals <math>\overline{P_0P_2},\ \overline{P_2P_4},\ \ldots \overline{P_{2n-2}P_0}</math>. This partitions <math>\mathcal{P}</math> into <math>n</math> isosceles triangles of the form <math>\triangle P_{2k}P_{2k+1}P_{2k+2}</math>, as well as a central regular polygon with <math>n</math> sides. However, we know that there exists a triangulation for the <math>n</math>-sided polygon that yields <math>n-2</math> isosceles triangles. Thus, we have created <math>(n) + (n-2) = 2n-2</math> isosceles triangles with non-intersecting diagonals, as desired. <math>\ \square</math>
 <center><asy>
@@ Line 148: / Line 148: @@
 * <url>viewtopic.php?t=202905 Discussion on AoPS/MathLinks</url>
+[[Category:Olympiad Combinatorics Problems]]

Page

Toolbox

Search

Difference between revisions of "2008 USAMO Problems/Problem 4"

Revision as of 19:01, 2 May 2008

Problem

Contents

Solution

Resources