Difference between revisions of "2008 USAMO Problems/Problem 4"
(→Solution) |
|||
(5 intermediate revisions by 4 users not shown) | |||
Line 4: | Line 4: | ||
== 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 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 10: | Line 9: | ||
<center><table><tr><td><asy> | <center><table><tr><td><asy> | ||
− | defaultpen(linewidth(0.7)+fontsize(10)); | + | size(200); defaultpen(linewidth(0.7)+fontsize(10)); |
int n = 17; real r = 1; real rad = pi/2; | int n = 17; real r = 1; real rad = pi/2; | ||
Line 35: | Line 34: | ||
label(" | label(" | ||
</asy> </td><td><asy> | </asy> </td><td><asy> | ||
− | defaultpen(linewidth(0.7)+fontsize(10)); | + | size(200); defaultpen(linewidth(0.7)+fontsize(10)); |
int n = 20; real r = 1; real rad = pi/2; | int n = 20; real r = 1; real rad = pi/2; | ||
Line 68: | Line 67: | ||
<cmath>n = 2^{b}(2^{a-b+1}+1).</cmath> | <cmath>n = 2^{b}(2^{a-b+1}+1).</cmath> | ||
*''Lemma 1'': All regular polygons with <math>n = 2^k + 1</math> or <math>n=4</math> have triangulations that meet the conditions. | *''Lemma 1'': All regular polygons with <math>n = 2^k + 1</math> or <math>n=4</math> have triangulations that meet the conditions. | ||
− | + | ||
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>. | ||
− | |||
− | |||
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. | ||
<center><asy> | <center><asy> | ||
− | defaultpen(linewidth(0.7)+fontsize(10)); | + | size(200); defaultpen(linewidth(0.7)+fontsize(10)); |
int n = 17; real r = 1; real rad = pi/2; | int n = 17; real r = 1; real rad = pi/2; | ||
Line 111: | Line 108: | ||
</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> | ||
− | + | *''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. | 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> | <center><asy> | ||
− | defaultpen(linewidth(0.7)+fontsize(10)); | + | size(200); defaultpen(linewidth(0.7)+fontsize(10)); |
int n = 10; real r = 1; real rad = pi/2; | int n = 10; real r = 1; real rad = pi/2; | ||
Line 144: | Line 140: | ||
</asy><br /><span style="font-size:85%">An example for <math>n=10,\, n/2 = 5</math></span></center> | </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, 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>. |
− | + | == 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}} |
Latest revision as of 11:37, 20 April 2022
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 .
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 ).
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.
By induction, it follows that we can cover all the desired .
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
- 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.
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 .
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.