Difference between revisions of "2008 USAMO Problems/Problem 4"
m (→Solution: typo fix) |
(→Solution) |
||
(8 intermediate revisions by 7 users not shown) | |||
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>. | ||
− | |||
== 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 9: | 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 34: | Line 34: | ||
label("\(\cdots\)",pt(2),NE); | label("\(\cdots\)",pt(2),NE); | ||
</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 67: | 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. | |
− | |||
<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 109: | 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. | ||
<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 140: | 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]] | |
+ | {{MAA Notice}} |
Latest revision as of 12: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.
![[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]](http://latex.artofproblemsolving.com/a/e/5/ae50d7ab825d1155ee542204fe49aa51afd540b4.png)
An example for
![$n=17 = 2^{4}+1$](http://latex.artofproblemsolving.com/3/2/6/32672571d766a1854e8b7fe6e800dead54da392e.png)
- 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.
![[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]](http://latex.artofproblemsolving.com/6/e/b/6ebc167ef6ba30af947a8f74e8f9cd1a237cf70b.png)
An example for
![$n=10,\, n/2 = 5$](http://latex.artofproblemsolving.com/4/4/d/44d9efb2b06e58f625f7266ba38099caacebfe8a.png)
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.