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

(will finish soon)
(Solution)
 
(11 intermediate revisions by 7 users not shown)
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 ''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>.
+
(''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__
 
 
== Solution ==
 
== Solution ==
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>.
 
  
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
+
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. We show that <math>k</math> must have the form <math>2^{m}</math> for some nonnegative integer <math>m</math>.
<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  
+
This diagonal [[partition]]s <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 all 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> (if we allow [[degenerate|degeneracy]], then we can also let <math>m=0</math>).
 +
 
 +
<center><table><tr><td><asy>
 +
size(200); 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("Q",(pt()+pt(6))/2,SE);
 +
label("R",(pt()+pt(10))/2,W);
 +
 
 +
label("P0",pt(),N);
 +
label("P1",pt(1),NNE);
 +
label("P8",pt(8),S);
 +
label("P16",pt(-1),NNW);
 +
label("",pt(2),NE);
 +
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td><td><asy>
 +
size(200); 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("P0",pt(),N);
 +
label("P1",pt(1),NNE);
 +
label("P19",pt(-1),NNW);
 +
label("P8",pt(8),SE);
 +
label("P16",pt(16),W);
 +
label("",pt(2),NE);
 +
 
 +
</asy></td></tr><tr><td><span style="font-size:85%">An example for <math>n=17</math>,<br /><math>k=8</math></span></td><td><span style="font-size:85%">An isosceles triangle containing<br /> the center for <br /> <math>n=20</math>, <math>(x,y,z) = (0,8,16)</math></span></td></tr></table></center>
 +
 
 +
Now take the isosceles triangle <math>P_xP_yP_z,\,0 \le x < y < z < n</math> in the triangulation that contains the center of <math>\mathcal{P}</math> 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 <math>P_xP_y = P_yP_z</math>. From our previous result, it follows that there are <math>2^a</math> edges of <math>P</math> on the minor arcs of <math>P_xP_y,\, P_yP_z</math> and <math>2^b</math> edges of <math>P</math> on the minor arc of <math>P_zP_x</math>, for positive integers <math>a,\,b</math>. Therefore, we can write
 +
<cmath>n = 2 \cdot 2^a + 2^b = 2^{a+1} + 2^{b},</cmath> so <math>n</math> must be the sum of two powers of <math>2</math>.
 +
 
 +
 
 +
We now claim that this condition is sufficient. Suppose without loss of generality that <math>a+1 \ge b</math>; then we rewrite this as  
 
<cmath>n = 2^{b}(2^{a-b+1}+1).</cmath>
 
<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 1'': All regular polygons with <math>n = 2^k + 1</math> or <math>n=4</math> have triangulations that meet the conditions.
*''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>.
+
By [[induction]], it follows that we can cover all the desired <math>n</math>.
 +
 
 +
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.
 +
 
 +
<center><asy>
 +
size(200); 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("P0",pt(),N);
 +
label("P1",pt(1),NNE);
 +
label("P16",pt(-1),NNW);
 +
label("",pt(2),NE);
 +
</asy><br /><span style="font-size:85%">An example for <math>n=17 = 2^{4}+1</math></span></center>
 +
 
 +
*''Lemma 2'': If a regular polygon with <math>n</math> sides has a working triangulation, then the regular polygon with <math>2n</math> sides also has a triangulation that meets the conditions.
 +
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.
 +
 
 +
<center><asy>
 +
size(200); 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));
 +
}
  
''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. 
+
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("P0",pt(),N);
 +
label("P1",pt(1),NNE);
 +
label("P2",pt(2),NE);
 +
label("P3",pt(3),E);
 +
label("P4",pt(4),SE);
 +
label("P5",pt(5),S);
 +
label("P6",pt(6),SW);
 +
label("P7",pt(7),W);
 +
label("P8",pt(8),NW);
 +
label("P9",pt(9),NNW);
  
''Proof 2'': Construct every other edge, then reduce etc.
+
</asy><br /><span style="font-size:85%">An example for <math>n=10,\, n/2 = 5</math></span></center>
  
{{incomplete|solution}}
+
In summary, the answer is all <math>n</math> that can be written in the form <math>2^{a+1} + 2^{b},\, a,b \ge 0</math>. Alternatively, this condition can be expressed as either <math>n=2^{k},\, k \ge 2</math> (this is the case when <math>a+1 = b</math>) or <math>n</math> is the sum of two distinct powers of <math>2</math>, where <math>1= 2^0</math> is considered a power of <math>2</math>.
  
{{alternate solutions}}
+
== See also ==
 +
* <url>viewtopic.php?t=202905 Discussion on AoPS/MathLinks<\url>
  
== Resources ==
 
 
{{USAMO newbox|year=2008|num-b=3|num-a=5}}
 
{{USAMO newbox|year=2008|num-b=3|num-a=5}}
  
* <url>viewtopic.php?t=202905 Discussion on AoPS/MathLinks</url>
+
[[Category:Olympiad Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 11:37, 20 April 2022

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] size(200); 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] size(200); 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.

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

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.

[asy] size(200); 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$
  • 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.

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.

[asy] size(200); 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$.

See also

  • <url>viewtopic.php?t=202905 Discussion on AoPS/MathLinks<\url>
2008 USAMO (ProblemsResources)
Preceded by
Problem 3
Followed by
Problem 5
1 2 3 4 5 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png