AoPSWiki

Visit the AoPS Book Store.

Personal tools

Search

Toolbox

2007 BMO Problems/Problem 4

From AoPSWiki

Revision as of 03:36, 5 May 2007 by Boy Soprano II (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Problem

(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}$ .

Solution

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.

Resources

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2007_BMO_Problems/Problem_4"

Category: Olympiad Combinatorics Problems

Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us