National Math Olympiad

We will show that there exist at least $n+1$ divisor lines. First, let us give an example where there are exactly $n+1$ of them. For that the given points should be the vertices of a regular $(2n+2)$-gon. Denote them by $A_1,A_2,\dots ,A_{2n+2}$. For each $1\le i\le n+1$ the line $A_i{A}_{i+n+1}$ is obviously a divider. No other line is a divider, so there are exactly $n+1$ of them.

Now, let us show that we can always find at least $n+1$ dividers regardless of the positions of the given points. We will show that there is at least one divider passing through each of the points. Let $A$ be one of the points and denote the remaining points by $A_1,A_2,\dots ,A_{2n+1}$. Consider the lines $A{A}_1,A{A}_2,\dots ,A{A}_{2n+1}$. Let us paint the half-plane on one of the sides of the line $A{A}_1$ gray. Let $r_1$ be the number of points contained in the gray part (the line $A{A}_1$ itself does not belong to the gray part).

Now, let us rotate the gray part around $A$ in the positive direction. In each step rotate it so that the image of the gray part borders on the next possible line amongst $A{A}_1,A{A}_2,\dots ,A{A}_{2n+1}$. We may assume that these lines are already ordered, so we get $A{A}_1,A{A}_2,\dots ,A{A}_{2n+1}$ and then again $A{A}_1$. Let $r_{i+1}$ be the number of the given points in the gray part after $i$ steps.

Assume that at some point we started with the line $A{A}_i$ and then rotated the gray part so that it is now bordering on the line $A{A}_{i+1}$. We consider four possible cases for the positions of the points $A_i$ and $A_{i+1}$. If $A_{i+1}$ was initially in the gray part and $A_i$ is there after the rotation, then $r_i=r_{i+1}$. If $A_{i+1}$ was initially in the gray part and $A_i$ is not in the gray part after the rotation, then the number of points in the gray part decreased by 1, so $r_{i+1}=r_i-1$. If $A_{i+1}$ was initially not in the gray part, then we have $r_{i+1}=r_i$ if $A_i$ is not in the gray part after the rotation. Otherwise we have $r_{i+1}=r_i+1$.

In each step the number of points in the gray part changes by at most 1. All these numbers are integers. At the beginning there were $r_1$ points in the gray part. After $2n+1$ rotations we have the situation where the gray part is once more bordering on the line $A{A}_1$, but it is not on the same side as in the beginning. So, the number of points in the gray part is in the end equal to



$2n-r_1$. If $r_1=n$, then $A{A}_1$ is a divider. If not, then one of the numbers $r_1$ and $2n-r_1$ is greater than $n$, and the other is smaller. After each rotation of the gray part the numbers $r_i$ change by 1, so after a number of steps we have $r_i=n$. The line $A{A}_i$ is then a divider.

As promised, we have shown that for each of the given points there is a divider passing through this point. There are $2n+2$ points altogether, so we have thus obtained $2n+2$ lines. Each line was counted twice. Hence, there are at least $\frac{2n+2}{2}=n+1$ dividers.