2007 BMO Problems/Problem 4

Revision as of 22:36, 4 May 2007 by Boy Soprano II (talk | contribs) (rambling solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


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


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

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

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

Let $C_3 = Z_1Z_2 \cdots Z_n$ ($\displaystyle Z_{n+1} = Z_1$), and for any $\displaystyle i$, let $B_i = A_i \cap C_1 \cap C_2$. We will say that a side $\displaystyle Z_iZ_{i+1}$ is singular if the segment $\displaystyle Z_iZ_{i+1}$, excluding the point $\displaystyle Z_{i+1}$, intersects $C_1 \cap C_2$ exactly once, and duple if the segment intersects $C_1 \cap C_2$ twice. Let $\displaystyle a$ be the number of singular sides, and $\displaystyle b$ be the number of duple sides. Clearly,

$a+b \le n \qquad (*)$.

Now, each singular segment prevents one of the $\displaystyle B_i$ from being intersected by any other segment $\displaystyle Z_iZ_{i+1}$ (excluding the point $\displaystyle Z_{i+1}$). Furthermore, each duple segment prevents three of the $\displaystyle B_i$ from being intersected by any other such segment, for it cannot intersect two consecutive $\displaystyle B_i$ (or else $\displaystyle C_3$ would share part of a side with either $\displaystyle C_1$ or $\displaystyle C_2$), and since the rest of $\displaystyle C_3$ must be on the same side of the duple segment, at least one of the $\displaystyle B_i$ must be excluded. Hence we obtain the inequality

$a+ 3b \le 2n \qquad (**)$.

Adding inequalities $\displaystyle (*)$ and $\displaystyle (**)$ gives the desired bound. Thus the maximum number of points in $C_1 \cap C_2 \cap C_3$ is $\left\lfloor \frac{3}{2}n \right\rfloor$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.