View source

== Problem ==

(''Turkey'')
For a given positive integer <math> \displaystyle n >2 </math>, let <math> \displaystyle C_{1},C_{2},C_{3} </math> be the boundaries of three convex <math> \displaystyle n</math>-gons in the plane such that <math> C_{1}\cap C_{2} </math>, <math> C_{2}\cap C_{3} </math>, <math> C_{3}\cap C_{1} </math> are finite. Find the maximum number of points in the set <math> C_{1}\cap C_{2}\cap C_{3} </math>.

== Solution ==

In this solution, we understand the vertices of an <math> \displaystyle m </math>-gon to be taken mod <math> \displaystyle m </math>.

First, we will show that there are <math> \displaystyle C_1, C_2, C_3 </math> such that <math> | C_1 \cap C_2 \cap C_3 | = \left\lfloor \frac{3}{2}n \right\rfloor </math>.  Let <math> \displaystyle C_1 </math> be a regular <math> \displaystyle n </math>-gon and let <math> \displaystyle C_2 </math> be the rotation of <math> \displaystyle C_1 </math> by <math> \frac{\pi}{n} </math> about its center.  The vertices common to <math> \displaystyle C_1 </math> and <math> \displaystyle C_2 </math> are the vertices of a regular <math> \displaystyle 2n </math>-gon, which we shall denote <math> M = M_1M_2\cdots M_{2n} </math>.  Let <math> \displaystyle C_3 = Z_1Z_2\cdots Z_n </math>, and let <math> \displaystyle Z_{n+1} = Z_1 </math>.  If <math> \displaystyle n </math> is even, then for <math> 1 \le i \le n/2 </math>, we let the line <math> \displaystyle Z_{2i-1}Z_{2i} </math> be the same as the line <math> \displaystyle M_{4i-3}M_{4i-1} </math>, and we let the line <math> \displaystyle Z_{2i}Z_{2i+1} </math> be a line through <math> \displaystyle M_{4i} </math> that only intersects <math> \displaystyle M </math> at <math> \displaystyle M_{4i} </math>.  If <math> \displaystyle n </math> is odd, then this remains the same for <math> 1 \le i \le \lfloor n/2 \rfloor </math>, and we let the line <math> \displaystyle Z_{n}Z_1 </math> be a line which intersects <math> \displaystyle M </math> only at <math> \displaystyle M_{2n} </math>.  Either way, the <math> \displaystyle n </math>-gon <math> \displaystyle C_3 </math> then satisfies the desired conditions.

Now we will show that we always have <math> | C_1 \cap C_2 \cap C_3 | \le \frac{3}{2}n </math>, and therefore <math> | C_1 \cap C_2 \cap C_3 | \le \left\lfloor \frac{3}{2}n \right\rfloor </math>.  If the interiors of <math> \displaystyle C_1 </math> and <math> \displaystyle C_2 </math> do not overlap, then <math> \displaystyle C_1 </math> and <math> \displaystyle C_2 </math> can have at most one point in common, and we are done.  Otherwise, let <math> \displaystyle P </math> be a point in the interior of both <math> \displaystyle C_1 </math> and <math> \displaystyle C_2 </math> such that <math> \displaystyle P </math> is collinear with no two vertices of <math> C_1 \cup C_2 </math>.  Now, we draw <math> \displaystyle 2n </math> rays from <math> \displaystyle P </math> to each of the vertices of <math> \displaystyle C_1 </math> and <math> \displaystyle C_2 </math>.  This divides the plane into <math> \displaystyle 2n </math> regions, which we may label consecutively <math> A_1, A_2, \ldots, A_{2n} </math>, going clockwise around <math> \displaystyle P </math> and considering our indices mod <math> \displaystyle 2n </math>.  Each <math> \displaystyle A_i </math> includes its clockwise bounding line but excludes its counterclockwise bounding line.  For any integer <math> \displaystyle i </math>, there is most one point of <math> C_1 \cap C_2 </math> in <math> \displaystyle A_i </math>, or else <math> \displaystyle C_1 </math> and <math> \displaystyle C_2 </math> would share a side.  Since the vertices of <math> C_1 \cap C_2 </math> are the vertices of a convex polygon, no side of <math> \displaystyle C_3 </math> can intersect <math> C_1 \cap C_2 </math> more than twice.

Let <math> C_3 = Z_1Z_2 \cdots Z_n </math> (<math> \displaystyle Z_{n+1} = Z_1 </math>), and for any <math> \displaystyle i </math>, let <math> B_i = A_i \cap C_1 \cap C_2 </math>.  We will say that a side <math> \displaystyle Z_iZ_{i+1} </math> is ''singular'' if the segment <math> \displaystyle Z_iZ_{i+1} </math>, excluding the point <math> \displaystyle Z_{i+1} </math>, intersects <math> C_1 \cap C_2 </math> exactly once, and ''duple'' if the segment intersects <math> C_1 \cap C_2 </math> twice.  Let <math> \displaystyle a </math> be the number of singular sides, and <math> \displaystyle b </math> be the number of duple sides.  Clearly,
<center>
<math>
a+b \le n \qquad (*)
</math>.
</center>
Now, each singular segment prevents one of the <math> \displaystyle B_i </math> from being intersected by any other segment <math> \displaystyle Z_iZ_{i+1} </math> (excluding the point <math> \displaystyle Z_{i+1} </math>).  Furthermore, each duple segment prevents three of the <math> \displaystyle B_i </math> from being intersected by any other such segment, for it cannot intersect two consecutive <math> \displaystyle B_i </math> (or else <math> \displaystyle C_3 </math> would share part of a side with either <math> \displaystyle C_1 </math> or <math> \displaystyle C_2 </math>), and since the rest of <math> \displaystyle C_3 </math> must be on the same side of the duple segment, at least one of the <math> \displaystyle B_i </math> must be excluded.  Hence we obtain the inequality
<center>
<math>
a+ 3b \le 2n \qquad (**)
</math>.
</center>
Adding inequalities <math> \displaystyle (*) </math> and <math> \displaystyle (**) </math> gives the desired bound.  Thus the maximum number of points in <math> C_1 \cap C_2 \cap C_3 </math> is <math> \left\lfloor \frac{3}{2}n \right\rfloor </math>.


{{alternate solutions}}

== Resources ==

* [[2007 BMO Problems]]
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=827192#827192 Discussion on AoPS/MathLinks]


[[Category:Olympiad Combinatorics Problems]]