For a given positive integer $n >2$, let $C_{1},C_{2},C_{3}$ be the boundaries of three convex $n-$ gons in the plane , such that $C_{1}\cap C_{2}, C_{2}\cap C_{3},C_{1}\cap C_{3}$ are finite. Find the maximum number of points of the sets $C_{1}\cap C_{2}\cap C_{3}$.
Problem
Source: Balkan MO 2007
Tags: floor function, geometry, geometric transformation, rotation, combinatorial geometry, combinatorics unsolved, combinatorics
28.04.2007 19:09
I doubt that what I'm going to post has much to do with reality, but... Let our intersection be $\mathcal C = \left\{ x_{1}, \ldots, x_{m}\right\}$ (it's clear that the maximal $m$ is $\geq n$ and $\leq 2n$). No three points are collinear and the convex hull of $\mathcal C$ is a convex $m$-gon. Now we construct a $n$-gon which passes through the vertices in $\mathcal C$. If a side of the $m$-gon is part of a side of the $n$-gon, then assign a $+$ to it. We assign $-$'s to the other sides of the $m$-gon. Now go through the sides in counter-clockwise direction. The number of consecutive pairs $(+,-)$ must be equal to $m-n$. Thus, the number of sides common to both the $m$-gon and to the $n$-gon is somewhere between $m-n$ and $n$. In particular, it's $\geq m-n$ (that's obviously reachable). To get three convex $n$-gons such that any two do not have common sides, we should have that $3(m-n) \leq m$, i.e. $m \leq \frac{3n}2$. The answer is $m = \left\lfloor \frac{3n}2 \right\rfloor$. As you may have noticed, my post contains excessively many gaps, so chances are high that I missed some things.
04.05.2007 18:04
i don`t understand the $m-n$ and pairs $(+,-)$ part. however, the answer is correct. here is my solution (from the contest) assume for the sake of contradiction that for some $n$, the maximal number is greater (strictly) than $3n/2$. first, it is easy to see that $C_{1}\cap C_{2}$ can intersect in at most two points on each side of $C_{1}$. let`s assume that the intersection points are $A_{1},A_{2},\ldots,A_{2n}$, and if some doesn`t exist then it doesn`t matter. note : $A_{2i-1}$ and $A_{2i}$ are on the $i$`th side of $C_{1}$. if one of them doesn`t exits, then the problem isn`t affected, because i only count the points. now, $C_{3}$ must have "many" $A_{i}$`s on it`s sides, and must fulfill the condition. one side of $C_{3}$ can`t contain more than two $A_{i}$`s. first, i assume wlog that none of the $A_{i}$`s are vertices of $C_{3}$ (if so, then i do a small rotation of one side, perserving all the properties of $C_{3}$). let`s denote by $k$ the number of sides of $C_{3}$ that contain two $A_{i}$`s. then, since there are strictly more than $3n/2$ $A_{i}$`s on the sides of $C_{3}$, and the number of $A_{i}$`s on the sides of $C_{3}$ is less (or equal) than $2k+(n-k)$, it follows that $2k+(n-k)>3n/2$, thus $k>n/2$. now, i go in a clockwise direction starting from $A_{1}$, and i make the observation that any side of $C_{3}$ "leaves outside" one of the points $A_{i}$. more precisely, since no side of $C_{3}$ can contain both $A_{i}$ and $A_{i+1}$ (since $[A_{i}A_{i+1}]$ is contained in a side of $C_{1}$ or $C_{2}$), the two $A_{i}$`s can`t be consecutive, thus there is another one between them. by fixing the clockwise direction, i assure that by picking a point that corresponds to a side, it corresponds to that side only (thus this "application" is injective). hence, there are at least $k$ points from the $A_{i}$`s that are not contained in $C_{3}$, thus, $C_{3}$ contains at most $2n-k < 3n/2$ points from the $A_{i}$`s, contradiction. thus $f(n)\leq 3n/2$. an example is easy to see. consider a regular $2n$-gon, and take the two $n$-gons that are formed by it`s even-indiced vertices and odd-indiced vertices. this two $n$-gons intersect in $2n$ points $A_{1},A_{2},\ldots,A_{2n}$, and now take $C_{3}$ with sides $l_{1},l_{2},\ldots,l_{n}$, such that $A_{1},A_{3}\in l_{1}$, $A_{4}\in l_{2}$, $A_{5},A_{7}\in l_{3}$ and so on... i know the above isn`t written very well but this is the main idea.
04.05.2007 19:04
Let's take $n=5$ and then wonder what if the intersection had $m = 7$ points ($A,B,\ldots,G$). As you noticed, some sides of the $m$-gon will be part of a side of the $n$-gon (in the image, the sides numbered $1,2,5$). First, take a side with a $+$ on it (it must exist, since it's clear that $m \geq n+1$). Next, go in counter-clockwise direction, until you hit a pair $(+,-)$ (that also must exist). In this case, $2^{+}\ 3^{-}$. Continuing, it's kind of obvious that you'll eventually reach a pair $(-,+)$, i.e. $4^{-}\ 5^{+}$. My idea was to notice that one side gets "eaten" this way. In the $m$-gon, we went through four sides $\left( 1^{+}2^{+}3^{-}4^{-}\right)$, whilst in the $n$-gon we have only three sides (the $n$-gon is, of course, the one in blue). I think that continuing this way my statement should follow. Here, we have $m-n=2$ pairs of $(+,-)$, namely $2^{+}\ 3^{-}$ and $5^{+}\ 6^{-}$. The number of sides common to the $m$-gon and to the $n$-gon is $3$, which is obviously $\geq m-n$. Invalid URL I believe that your argument is pretty much the same
08.05.2007 00:02
I didn't consider the case when more than one vertex of $n$-gon is "near" a side of the $m$-gon (e.g. $AG$). Fortunately, that can be easily taken care of. If we have $t$ "extra" vertices, then we can eliminate them, and then use the result from my previous post to get that the number of $(+,-)$ pairs is $\geq m-(n-t) \geq m-n$, so what I said holds in the general case, too.
11.06.2009 12:26
How about this ? Let the number of points in $ C_{1}\cap C_{2}\cap C_{3}$ be $ M$. Between two consecutive points, there must be at least two vertices of the original three polygons, otherwise two sides of the polygons overlap each other. As there are $ 3n$ vertices from $ C_{1},C_{2},C_{3}$, we must have $ M\leq\frac{3n}{2}$.