Difference between revisions of "2008 USAMO Problems/Problem 4"
(will finish soon) |
(finish (yay, i actually wrote my own usamo solution for once :p )) |
||
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__ | __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. | + | 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>. |
− | |||
− | |||
− | We now claim that this condition is sufficient. Suppose | + | 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 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 degeneracy, then we can also let <math>m=0</math>). |
+ | |||
+ | |||
+ | 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, 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 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> | ||
+ | |||
+ | |||
+ | 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> | + | *''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> | + | *''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. |
− | 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>. |
+ | |||
+ | |||
+ | ''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 triangle <math>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>, as desired. <math>\ \square</math> | ||
+ | |||
+ | <center><asy> | ||
+ | defaultpen(linewidth(0.62)+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(" | ||
+ | label(" | ||
+ | label(" | ||
+ | label(" | ||
+ | </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> | ||
+ | |||
+ | <center><asy> | ||
+ | defaultpen(linewidth(0.62)+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(" | ||
+ | label(" | ||
+ | label(" | ||
+ | label(" | ||
+ | </asy><br /><span style="font-size:85%">An example for <math>n=10,\, n/2 = 5</math></span></center> | ||
− | + | 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, either <math>n=2^{a},\, a \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>. <math>\ \blacksquare</math> | |
{{alternate solutions}} | {{alternate solutions}} |
Revision as of 18:22, 2 May 2008
Problem
(Gregory Galparin) Let be a convex polygon with sides, . Any set of diagonals of that do not intersect in the interior of the polygon determine a triangulation of into triangles. If is regular and there is a triangulation of consisting of only isosceles triangles, find all the possible values of .
Contents
[hide]Solution
We label the vertices of as . Consider a diagonal in the triangulation. We show that must have the form for some nonnegative integer .
This diagonal partitions into two regions , and is the side of an isosceles triangle in both regions. Without loss of generality suppose the area of is less than the area of (so the center of does not lie in the interior of ); it follows that the lengths of the edges and diagonals in are all smaller than . Thus must the be the base of the isosceles triangle in , from which it follows that the isosceles triangle is , and so . Repeating this process on the legs of isosceles triangle (), it follows that for some positive integer (if we allow degeneracy, then we can also let ).
Now take the isosceles triangle in the triangulation that contains the center of 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 . From our previous result, it follows that there are edges of on the minor arcs of and edges of on the minor arc of , for positive integers . Therefore, we can write
We now claim that this condition is sufficient. Suppose without loss of generality that ; then we rewrite this as
- Lemma 1: All regular polygons with or have triangulations that meet the conditions.
- Lemma 2: If a regular polygon with sides has a working triangulation, then the regular polygon with sides also has a triangulation that meets the conditions.
By induction, it follows that we can cover all the desired .
Proof 1: For , this is trivial. For , we construct the diagonals of equal length and . This partitions into regions: an isosceles triangle , 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 , as desired.
An example for
Proof 2: We construct the diagonals . This partitions into isosceles triangles of the form , as well as a central regular polygon with sides. However, we know that there exists a triangulation for the -sided polygon that yields isosceles triangles. Thus, we have created isosceles triangles with non-intersecting diagonals, as desired.
An example for
In summary, the answer is all that can be written in the form . Alternatively, either (this is the case when ), or is the sum of two distinct powers of , where is considered a power of .
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>