Olympiad Maths Prep

Track / Stage 5 / 269 of 400 #869 of 2000

Problem 869

AIME late
Combinatorics Difficulty 5.6 Prove it

Example 3 Let nn be an integer greater than 1. There are 2n2 n points on the plane, and no three points are collinear. Among these points, nn points are colored blue, and the remaining nn points are colored red. If a line passing through one red point and one blue point satisfies that the number of blue points on each side of the line equals the number of red points on that side, then this line is called a "balanced line". 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

【Analysis】First, prove that each vertex on the convex hull of these nn points lies on a balance line.

Assume RR is a vertex on the convex hull of the known 2n2 n points. Without loss of generality, let RR be a red point. Thus, there exists a line ll such that all points (excluding RR) are on the same side of the line ll. If the line ll is rotated clockwise around point RR, it will pass through all the blue points in a certain order.

Let the blue points that the line ll passes through in sequence when rotated clockwise around point RR be B1,B2,,BnB_{1}, B_{2}, \cdots, B_{n}. When ll rotates to point BiB_{i}, the number of blue points and red points that ll has passed through are denoted as bib_{i} and rir_{i}, respectively. Then,
bi=i1(i=1,2,,n),0r1r2rnn1. Define di=ribi(i=1,2,,n). Hence d1=r10,dn=rnbn=rn(n1)0, \begin{array}{l} b_{i}=i-1(i=1,2, \cdots, n), \\ 0 \leqslant r_{1} \leqslant r_{2} \leqslant \cdots \leqslant r_{n} \leqslant n-1 . \\ \text { Define } d_{i}=r_{i}-b_{i}(i=1,2, \cdots, n) . \\ \text { Hence } d_{1}=r_{1} \geqslant 0, d_{n}=r_{n}-b_{n}=r_{n}-(n-1) \leqslant 0, \end{array}

Thus, the sequence d1,d2,,dnd_{1}, d_{2}, \cdots, d_{n} starts with non-negative integers and ends with non-positive integers. As ii increases, rir_{i} does not decrease, and bib_{i} increases by 1, indicating that the difference between consecutive terms in the sequence d1,d2,,dnd_{1}, d_{2}, \cdots, d_{n} does not exceed 1.
In fact, for i=1,2,,n1i=1,2, \cdots, n-1, we have
didi+1=riri+1+bi+1bi0+1=1d_{i}-d_{i+1}=r_{i}-r_{i+1}+b_{i+1}-b_{i} \leqslant 0+1=1.
Therefore, there must exist some point i{1,2,,n}i \in\{1,2, \cdots, n\} such that di=0d_{i}=0.
Thus, ri=bir_{i}=b_{i}.
Hence, RBiR B_{i} is a balance line.
Since the convex hull of 2n(n2)2 n(n \geqslant 2) points has at least three vertices, and each vertex of the convex hull lies on a balance line, there are at least two different balance lines.

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