Olympiad Maths Prep

Track / Stage 6 / 75 of 400 #1075 of 2000

Problem 1075

National olympiad, first round
Combinatorics Difficulty 6.1 Prove it

5 Let nn be a positive integer greater than 1, and there are 2n2n points on a plane, with no three points being collinear. Among these points, nn points are colored blue, and the remaining nn points are colored red. If a line passes through one blue point and one red point, and the number of blue points and red points on each side of the line is the same, then the line is called balanced. Prove: there are at least two balanced lines.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Prove that taking the convex hull Ω\Omega of these 2n2n points, we prove: each vertex on Ω\Omega lies on a balanced line.

If the above proposition is proven, then by the condition, Ω\Omega has at least 3 distinct vertices, and each balanced line passes through at most two vertices of Ω\Omega, so there are at least two balanced lines.

Now we prove (1) holds. For any vertex AA of Ω\Omega, assume AA is a red point, draw a line ll through AA such that Ω\Omega is on one side of ll. Then, rotate ll counterclockwise around AA, each time passing through a blue point, to get nn lines AB1,AB2,,ABnA B_{1}, A B_{2}, \cdots, A B_{n}. The number of blue points on the left side of the line ABiA B_{i} is bi=i1b_{i}=i-1, and the number of red points on this side is denoted as rir_{i}, then 0r1r2rnn10 \leqslant r_{1} \leqslant r_{2} \leqslant \cdots \leqslant r_{n} \leqslant n-1.
We need to prove: there exists i{1,2,,n}i \in\{1,2, \cdots, n\}, such that bi=rib_{i}=r_{i} (thus, (1) holds).
In fact, let di=ribi,i=1,2,,nd_{i}=r_{i}-b_{i}, i=1,2, \cdots, n, then d1=r10,dn=rn(n1)0d_{1}=r_{1} \geqslant 0, d_{n}=r_{n}-(n-1) \leqslant 0. Therefore, the sequence d1,,dnd_{1}, \cdots, d_{n} starts from a number not less than zero and ends with a number not greater than zero. Furthermore, there is
didi+1=(riri+1)+(bi+1bi)0+1=1, d_{i}-d_{i+1}=\left(r_{i}-r_{i+1}\right)+\left(b_{i+1}-b_{i}\right) \leqslant 0+1=1,

So, from d1d_{1} to dnd_{n}, it decreases by at most 1 each time. Therefore, (2) holds.
The proposition is proven.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.