Maths Olympiad Prep

Library / /35 of 35

Geometry Difficulty 7.5 National olympiad, round 2 Prove it Slovenia

Let nn be a positive integer. There are 2n+22n + 2 points in a plane such that no three of the points lie on the same line. A line in the plane is a *divider*, if two of the given points lie on this line and there are exactly nn points on each of the two sides. Find the greatest possible mm for which there are always at least mm dividers in the plane.

Solution

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

Now, let us show that we can always find at least n+1n+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 AA be one of the points and denote the remaining points by A1,A2,,A2n+1A_1, A_2, \dots, A_{2n+1}. Consider the lines AA1,AA2,,AA2n+1AA_1, AA_2, \dots, AA_{2n+1}. Let us paint the half-plane on one of the sides of the line AA1AA_1 gray. Let r1r_1 be the number of points contained in the gray part (the line AA1AA_1 itself does not belong to the gray part).

Now, let us rotate the gray part around AA in the positive direction. In each step rotate it so that the image of the gray part borders on the next possible line amongst AA1,AA2,,AA2n+1AA_1, AA_2, \dots, AA_{2n+1}. We may assume that these lines are already ordered, so we get AA1,AA2,,AA2n+1AA_1, AA_2, \dots, AA_{2n+1} and then again AA1AA_1. Let ri+1r_{i+1} be the number of the given points in the gray part after ii steps.

Assume that at some point we started with the line AAiAA_i and then rotated the gray part so that it is now bordering on the line AAi+1AA_{i+1}. We consider four possible cases for the positions of the points AiA_i and Ai+1A_{i+1}. If Ai+1A_{i+1} was initially in the gray part and AiA_i is there after the rotation, then ri=ri+1r_i = r_{i+1}. If Ai+1A_{i+1} was initially in the gray part and AiA_i is not in the gray part after the rotation, then the number of points in the gray part decreased by 1, so ri+1=ri1r_{i+1} = r_i - 1. If Ai+1A_{i+1} was initially not in the gray part, then we have ri+1=rir_{i+1} = r_i if AiA_i is not in the gray part after the rotation. Otherwise we have ri+1=ri+1r_{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 r1r_1 points in the gray part. After 2n+12n+1 rotations we have the situation where the gray part is once more bordering on the line AA1AA_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

Figure 1
Figure 2
Figure 3

2nr12n - r_1. If r1=nr_1 = n, then AA1AA_1 is a divider. If not, then one of the numbers r1r_1 and 2nr12n - r_1 is greater than nn, and the other is smaller. After each rotation of the gray part the numbers rir_i change by 1, so after a number of steps we have ri=nr_i = n. The line AAiAA_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+22n + 2 points altogether, so we have thus obtained 2n+22n + 2 lines. Each line was counted twice. Hence, there are at least 2n+22=n+1\frac{2n+2}{2} = n + 1 dividers.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.