2007 BMO Problems/Problem 4
Problem
(Turkey) For a given positive integer , let be the boundaries of three convex -gons in the plane such that , , are finite. Find the maximum number of points in the set .
Solution
In this solution, we understand the vertices of an -gon to be taken mod .
First, we will show that there are such that . Let be a regular -gon and let be the rotation of by about its center. The vertices common to and are the vertices of a regular -gon, which we shall denote . Let , and let . If is even, then for , we let the line be the same as the line , and we let the line be a line through that only intersects at . If is odd, then this remains the same for , and we let the line be a line which intersects only at . Either way, the -gon then satisfies the desired conditions.
Now we will show that we always have , and therefore . If the interiors of and do not overlap, then and can have at most one point in common, and we are done. Otherwise, let be a point in the interior of both and such that is collinear with no two vertices of . Now, we draw rays from to each of the vertices of and . This divides the plane into regions, which we may label consecutively , going clockwise around and considering our indices mod . Each includes its clockwise bounding line but excludes its counterclockwise bounding line. For any integer , there is most one point of in , or else and would share a side. Since the vertices of are the vertices of a convex polygon, no side of can intersect more than twice.
Let (), and for any , let . We will say that a side is singular if the segment , excluding the point , intersects exactly once, and duple if the segment intersects twice. Let be the number of singular sides, and be the number of duple sides. Clearly,
.
Now, each singular segment prevents one of the from being intersected by any other segment (excluding the point ). Furthermore, each duple segment prevents three of the from being intersected by any other such segment, for it cannot intersect two consecutive (or else would share part of a side with either or ), and since the rest of must be on the same side of the duple segment, at least one of the must be excluded. Hence we obtain the inequality
.
Adding inequalities and gives the desired bound. Thus the maximum number of points in is .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.