4. Let $n$ be a natural number. In the plane, there are $2n+2$ points, no three of which lie on the same line. A line in the plane is a separator if it passes through two of the given points and on each side of this line there are exactly $n$ points. Determine the largest number $m$ such that there are always at least $m$ separators in the plane.

## 54th Mathematical Competition for High School Students in Slovenia  Ljubljana, April 17, 2010

## Solutions to the problems
IV /4. We will show that there are at least $n+1$ lines that pass through two of the given points and are separators. First, let's give an example where the number of separators is exactly $n+1$. Let the points be the vertices of a regular $(2 n+2)$-gon. Denote them by $A_{1}, A_{2}, \ldots, A_{2 n+2}$. For each $1 \leq i \leq n+1$, it is clear that the line $A_{i} A_{i+n+1}$ is a separator. No other line is a separator, so there are exactly $n+1$ separators.

We will also show that there are always at least $n+1$ separators regardless of the position of the points. We will show that through each of the given points, there is at least one separator. Let $A$ be one of the points and $A_{1}, A_{2}, \ldots, A_{2 n+1}$ the remaining points. Consider the lines $A A_{1}, A A_{2}, \ldots, A A_{2 n+1}$. Color the part of the plane that lies on one side of the line $A A_{1}$ red. Let $r_{1}$ be the number of points in the red part (the line $A A_{1}$ is not in the red part). We will rotate the red part of the plane around the point $A$ in the positive direction. In each step, we rotate so that the red part borders the next possible line among $A A_{1}, A A_{2}, \ldots, A A_{2 n+1}$. We can assume that the lines follow in the order $A A_{1}, A A_{2}, \ldots, A A_{2 n+1}$ and then repeat $A A_{1}$. Let $r_{i+1}$ be the number of points in the red part of the plane after we have rotated the red part $i$ times.

Suppose that in some step we had the line $A A_{i}$ and the corresponding red part of the plane, and then we rotated the red part so that it bordered the line $A A_{i+1}$. We distinguish four cases based on the position of the points $A_{i}$ and $A_{i+1}$. If the point $A_{i+1}$ was in the original red part and $A_{i}$ is in the rotated red part, then $r_{i}=r_{i+1}$. If the point $A_{i+1}$ was in the original red part and $A_{i}$ is not in the rotated red part, the number of points in the red part has decreased by 1, so $r_{i+1}=r_{i}-1$. Suppose that $A_{i+1}$ was not in the original red part. If $A_{i}$ is not in the new red part, then $r_{i+1}=r_{i}$, otherwise $r_{i+1}=r_{i}+1$.

In each step, the number of red points changes by at most 1. All numbers are integers. Initially, there were $r_{1}$ points in the red part, and after $2 n+1$ rotations, we return to the situation where the red part borders the line $A A_{1}$, but on the opposite side of the line $A A_{1}$ as it was initially. Therefore, the number of points in the red part at the end is $2 n-r_{1}$. If $r_{1}=n$, then the line $A A_{1}$ is a separator. Otherwise, one of the numbers $r_{1}$ or $2 n-r_{1}$ is greater than $n$, and the other is less than $n$. During the rotation of the red part, the numbers $r_{i}$ change by 1, which means there is a step where $r_{i}=n$. The corresponding line $A A_{i}$ is then a separator.

We have shown that there is a separator through each point. Since there are $2 n+2$ points, we get $2 n+2$ lines, each counted twice (once for each point that lies on it). Thus, there are always at least $\frac{2 n+2}{2}=n+1$ separators.