Difference between revisions of "2008 USAMO Problems/Problem 4"
5849206328x (talk | contribs) m |
|||
Line 2: | Line 2: | ||
(''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>. | ||
− | == | + | == Solutions == |
− | ===Solution 1=== | + | === 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. We show that <math>k</math> must have the form <math>2^{m}</math> for some nonnegative integer <math>m</math>. | 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>. | ||
Line 71: | Line 71: | ||
By [[induction]], it follows that we can cover all the desired <math>n</math>. | By [[induction]], it follows that we can cover all the desired <math>n</math>. | ||
− | ===Solution 2=== | + | === Solution 2 === |
− | |||
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. | 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. | ||
Line 111: | Line 110: | ||
</asy><br /><span style="font-size:85%">An example for <math>n=17 = 2^{4}+1</math></span></center> | </asy><br /><span style="font-size:85%">An example for <math>n=17 = 2^{4}+1</math></span></center> | ||
− | ===Solution 3=== | + | === Solution 3 === |
− | |||
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. | 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. | ||
Line 145: | Line 143: | ||
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>. | 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}} | {{alternate solutions}} | ||
− | == See | + | == See also == |
+ | * <url>viewtopic.php?t=202905 Discussion on AoPS/MathLinks</url> | ||
+ | |||
{{USAMO newbox|year=2008|num-b=3|num-a=5}} | {{USAMO newbox|year=2008|num-b=3|num-a=5}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 04:20, 14 August 2014
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 .
Solutions
Solution 1
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 ).
An example for , | An isosceles triangle containing the center for , |
Now take the isosceles triangle in the triangulation that contains the center of 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 . 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 so must be the sum of two powers of .
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 .
Solution 2
For , this is trivial. For , we construct the diagonals of equal length and . This partitions into regions: an isosceles , 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 isosceles triangles with non-intersecting diagonals, as desired.
An example for
Solution 3
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, this condition can be expressed as 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.
See also
- <url>viewtopic.php?t=202905 Discussion on AoPS/MathLinks</url>
2008 USAMO (Problems • Resources) | ||
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.