2008 USAMO Problems/Problem 4
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] 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/e/6/1/e617e5c0fa0bb476dc3427f25094bd64576dd198.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] 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/7/b/e/7be31eca53af60e12f2d12cc4b5d7a216ef64d4c.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.