24th Balkan Mathematical Olympiad

Let us first observe that, if a line intersects a convex $n$-gon at finitely many points, then the number of such points is at most $2$. Therefore any two of the $n$-gons may intersect in at most $2n$ points. Choose two of the $n$-gons, $C_1$, $C_2$, and say that their intersection points are $p_1,p_2,\dots ,p_k$. Thus $k\le 2n$. Say that the union of the set of vertices of $C_1$ and $C_2$ is $\{q_1,q_2,\dots ,q_{2n}\}$. We note that it is possible to have $q_i=q_j$ for some $i\ne j$.

We will define a one-to-one function $f$ from $\{p_1,p_2,\dots ,p_k\}$ to $\{q_1,q_2,\dots ,q_{2n}\}$ as follows. First of all, orient all $n$-gons in the clockwise direction. Thus, if one traverses an $n$-gon according to this orientation, the interior is on the right and the exterior is on the left. For every $p_i$, there exist precisely two line segments (of non-zero length) which are subsets of $C_1$ or $C_2$, say $[q_j,p_i]$ on $C_1$ and $[q_k,p_i]$ on $C_2$, such that one can approach to $p_i$ via these line segments in the clockwise direction. Suppose that the two vectors $p_i-q_j$ and $p_i-q_k$, in this order, form a right handed coordinate system. Then none of the points on $[q_j,p_i]$ can be on or in the interior of $C_2$, since for any point $q$ on or in the interior of $C_2$, the vectors $p_i-q$ and $p_i-q_k$ are either positive multiples of each other, or form a left handed coordinate system. In this case we set $f(p_i)=q_j$. Otherwise we set $f(p_i)=q_k$. In both cases, the argument above shows that there are no other intersection points between $f(p_i)$ and $p_i$, in the clockwise direction.

Let us now show that $f$ is 1-1. If $f(p_i)=f(p_l)=q$ and $q$ say (without loss of generality) belong to $C_1$, then the first intersection point encountered when one starts from $q$ and traverses $C_1$ in the clockwise direction has to be both $p_i$ and $p_l$, hence $p_i=p_l$.

Now let us estimate the number of $p_i$'s that can be contained by the third polygon $C_3$. Each edge of $C_3$ contains exactly $0$, $1$ or $2$ of the $p_i$'s. Suppose that a given edge of $C_3$ contains $2$ of the $p_i$'s, say $p_1$ and $p_2$. Since $C_1$ and $C_2$ are convex and their intersection with $C_3$ is generic, they should have vertices between (in the clockwise sense) $p_1$ and $p_2$ (with this order), and outside $C_3$. We claim that at least one of these vertices is not in the set $f(C_1\cap C_2\cap C_3)$. Let $q_1\in C_1$ and $q_2\in C_2$ respectively be between (in the clockwise sense) $p_1$ and $p_2$ (with this order). If $q_1$ is on or in the interior of $C_2$ (or $q_2$ is on or in the interior of $C_1$), then $q_1$ (or $q_2$) is not in the image of $f$, since recall that $f(p)$ for any $p\in C_1\cap C_2$ (thus for any $p\in C_1\cap C_2\cap C_3$) is a point of one of $C_1$, $C_2$ not on or in the interior of the other. So the claim is established in this case. The remaining case is to assume that none of the vertices of any of $C_1$, $C_2$ that lie outside $C_3$ (and between (in the clockwise sense) $p_1$ and $p_2$ (with this order)) also lies in the interior of the other of $C_1$, $C_2$. In this case clearly the polygons $C_1$ and $C_2$ must meet at some point between (in the clockwise sense) $p_1$ and $p_2$ (with this order). Say $p_3$ is the closest to $p_1$ such point. Then clearly $f(p_3)$ is a vertex of one of $C_1$, $C_2$ between (in the clockwise sense) $p_1$ and $p_2$ (with this order). These parts of $C_1$, $C_2$ though, lie outside $C_3$; the interior of $C_3$ lies on the other side of the line $p_1{p}_2$. Thus $f(p_3)$ is not in $f(C_1\cap C_2\cap C_3)$ and the claim is established in all cases.

For the side $a$ of $C_3$ containing $p_1$, $p_2$ let us call $q(a)$ a vertex as the one in the claim we just proved. It is easy to see that for distinct sides $a$, $t$ of $C_3$ that contain two of the $p$'s, the points $q_a$, $q_b$ are distinct. Indeed, let $a$ contain $p_1$, $p_2$ and $b$ contain $p_3$, $p_4$ among the $p$'s. If one of $q_a$, $q_b$ belongs to one of $C_1$, $C_2$ and the other does not belong to it, we are okay. If both $q_a$, $q_b$ belong to say $C_1$, then in a clockwise tour around $C_1$ starting at $p_1$, we meet $p_1$, $p_2$, $p_3$, $p_4$ in this order. If not, say the order is $p_1$, $p_3$, $p_2$, $p_4$. Then the segments $p_1{p}_2$, $p_3{p}_4$ intersect at an interior point, since $C_1$ is a convex polygon. But then the sides $a$, $b$ of $C_3$ have a common interior point, a contradiction. So the correct order is $p_1$, $p_2$, $p_3$, $p_4$. But we know that adding $q(a)$, $q(b)$ in this tour the correct order is $p_1$, $q(a)$, $p_2$, $p_3$, $q(b)$, $p_4$. Thus $q(a)$, $q(b)$ are distinct as claimed.

Now if $x$ of the edges of $C_3$ contain $1$ of the $p_i$'s and $y$ of them contain $2$ of the $p_i$'s, then $x+y\le$ number of sides of $C_3$, i.e. $x+y\le n$. The number of points in $C_1\cap C_2\cap C_3$ is $x+2y$. Since $f$ is injective, $x+2y$ is also the number of $q$'s in $f(C_1\cap C_2\cap C_3)$. Also, by the argument in the previous paragraph, we see that for every distinct edge of $C_3$ containing $2$ points we can assign a corresponding distinct $q_i$ outside the image of $f(C_1\cap C_2\cap C_3)$. Therefore $x$ is less or equal to the number of $q$'s that do not belong in $f(C_1\cap C_2\cap C_3)$. So $(x+2y)+y$ is at most as much as the number of $q$'s. I.e. $x+3y\le 2n$. Adding this with $x+y\le n$ and dividing by $2$, and also taking into account that $x+2y$ is an integer

$$x+2y\le \lfloor \frac{3n}{2}\rfloor$$

Let us now show that this is the best upper bound for every $n\ge 3$. One way (among many) to construct an example is as follows: Construct two regular $n$-gons $C_1$, $C_2$ with the same center, such that their intersection points form a regular $2n$-gon. Call the vertices $p_1,p_2,\dots ,p_{2n}$ in a cyclic order. Let the circumcircle of this $2n$-gon be $C$. Then let the $n$-gon bounded by the lines $p_1{p}_3$, $p_5{p}_7$, $p_9{p}_{11}$, $\dots$ (including $p_{2k+1}{p}_1$ in case $n$ is an odd $n=2k+1$) together with the tangent lines to $C$ at $p_4$, $p_8$, $p_{12}$, $\dots$ be $C_3$. It can easily be checked that $|C_1\cap C_2\cap C_3|=\lfloor \frac{3n}{2}\rfloor$.

---

Alternative solution.

Let $A$ and $B$ be two consecutive points of $C_1\cap C_2\cap C_3$ observed in the clockwise direction from a point in the interior of all three $n$-gons. Let's look for each $C_i$ its section in the clockwise direction between $A$ and $B$ excluding these points. If some two of these sections both do not contain any vertices of their corresponding $n$-gons, then the segment $AB$ belongs to both $n$-gons, a contradiction. Thus at least two of these segments have at least one vertex each, and moreover they do not contain the segment. Trivially, two distinct such vertices exist. Since there exist $|C_1\cap C_2\cap C_3|$ many consecutive points $A$ and $B$ of $C_1\cap C_2\cap C_3$, there should exist at least $2|C_1\cap C_2\cap C_3|$ distinct vertices of the three $n$-gons. Thus $2|C_1\cap C_2\cap C_3|\le 3n$ i.e. $|C_1\cap C_2\cap C_3|\le \lfloor \frac{3n}{2}\rfloor$ since $|C_1\cap C_2\cap C_3|$ is an integer as well).

Actually we can achieve this upper bound by the example given in the Solution 1.