$101$ blue and $101$ red points are selected on the plane, and no three lie on one straight line. The sum of the pairwise distances between the red points is $1$ (that is, the sum of the lengths of the segments with ends at red points), the sum of the pairwise distances between the blue ones is also $1$, and the sum of the lengths of the segments with the ends of different colors is $400$. Prove that you can draw a straight line separating everything red dots from all blue ones.
Problem
Source: 2016 Kazakhstan MO grades XI P5
Tags: combinatorics, Coloring, points, combinatorial geometry
10.10.2021 18:28
If we show that the convex hull of all red points and the convex hull of all blue points do not intersect, then by the Separating Axis Theorem, there exists a line separating all red points from all blue points. Call a segment red if it connects two red points, blue if it connects two blue points, and mixed if it connects a red and a blue point. We will show that all red segments do not intersect with any blue segment. From this, the convex hull of all red points and the convex hull of all blue points do not intersect, which finishes the problem. Claim: The lengths of all red segments and all blue segments are all less than $\frac{1}{100}$. Proof: Let $A$ and $B$ be any two points of the same color, and $P_1, P_2, \dots, P_{99}$ be the remaining points with the same color as $A$ and $B$. Note that the sum of all red segments is equal to $$1 = AB + \sum_{i=1}^{99} (AR_i + BR_i) + \sum_{1 \le i < j \le 99} R_iR_j > AB + \sum_{i=1}^{99} (AR_i + BR_i) > AB + \sum_{i=1}^{99} AB = 100AB$$Thus, $AB < \frac{1}{100}$, which means the lengths of all red segments are all less than $\frac{1}{100}$. Similarly, it can be said that the lengths of all blue segments are all less than $\frac{1}{100}$, proving the claim. Now assume that a red segment $R_1R_2$ and a blue segment $B_1B_2$ intersect at point $P$. Let $R$ be any red point (can be $R_1$ or $R_2$) and let $B$ be any blue point (can be $B_1$ or $B_2$). Then $RB < RP + BP \le max\{RR_1, RR_2\} + max\{BB_1, BB_2\} < 2 \cdot \frac{1}{100} = \frac{1}{50}$. So the lengths of all mixed segments are all less than $\frac{1}{50}$. There are $101 \cdot 101 = 10201$ mixed segments. Thus, the sum of the lengths of all mixed segments is $10201 \cdot \frac{1}{50} < 400$, contradiction. Therefore, all red segments do not intersect with any blue segment, and we are done.