Suppose we have a simple polygon (that is it does not intersect itself, but not necessarily convex). Show that this polygon has a diameter which is completely inside the polygon and the two arcs it creates on the polygon perimeter (the two arcs have 2 vertices in common) both have at least one third of the vertices of the polygon.
Problem
Source: Iran TST 2006
Tags: geometry, perimeter, induction, absolute value, combinatorics proposed, combinatorics
grobber
03.05.2006 16:31
I'll sketch it very briefly, because I found it pretty difficult to write down. The idea would be to triangulate the polygon, and choose the chord we're looking for among the sides of this triangulation. We pick one such side which divides the perimeter into two arcs with minimal difference in absolute value between the numbers of vertices, and prove, based on the fact that a triangle has at most three other triangles as neighbours, that as long as this difference is $<\frac n3$ ($n$ is the number of vertices of the polygon), one of the other two sides of one of the triangles which share the chosen side will be a better choice, contradicting the optimality assumption we made.
ikap
08.05.2006 18:26
After triangulation, induction works just fine. Any triangulation has a triangle with 2 sides on the sides of the original polygon. Take this triangle out of the figure and let $AB$ be the diameter of the remaining $n-1$-gon which divides it in the way we need it to. Let $X$ be the vertice that we took out and suppose $AB$ doesn't work for the $n-gon$. This can only mean that $A...X...B$ has more than $2/3\cdot (n+1)+2$ vertices. There is a triangle $ABY$ in the triangulation with $Y\in A...X...B$. One of $A...Y$ and $Y...B$ has at least $[2/3\cdot (n+1)+3]/2$ vertices. Suppose it is $A...Y$. Then $AY$ is a diameter that works. It is clear that $A...Y$ has at least $1/3 \cdot (n+1)$ vertices. It is also clear that $A...B...Y$ has at least $\frac n3$ (induction) +1 vertices so at least $1/3 (n+1)$. I found it quite not easy (AND uneasy...) to actually find a triangulation for a simple polygon. If anyone can illuminate me with an immediate solution I would be thankfull.
Hawk Tiger
06.06.2006 12:32
Can I ask a quetion that what " the arcs it creats " means? and does the "diameter" means the "segment attaches the two points between which the distant is the largest".
Nima Ahmadi Pour
06.06.2006 20:28
Hawk Tiger wrote: Can I ask a quetion that what " the arcs it creats " means? and does the "diameter" means the "segment attaches the two points between which the distant is the largest". Arcs means the two parts created on the perimeter of the polygon. And no, diameter is only the segment between two non-adjacent points.
hal9v4ik
15.02.2014 06:00
My solution is same as ikap's but I think that grobber's better.