Prove there are at least $2$ lines with the property that each of them divides the plane into $2$ regions with the same number of red and blue points.

71 Views Asked by At

Let $n \geq 2$ a natural number, and $2n$ points chosen in plane, $n$ red points and $n$ blue points. There are no $3$ collinear points among the $2n$ points in plane. A 'good' line is a line that passes through a blue and a red point, and divides the plane into $2$ regions, both of them containing an equal number of red and blue points (not necessarily the same in both regions). Prove that there are at least $2$ 'good' lines.

Attempt

Let's consider $Z$ a random variable that express the difference between the number of red points and the number of blue points in one of the regions. Define $x_i$ ($1, 2, \dots, n - 1$) a set of independent random variables that are $0$ if the $i^{th}$ red point is not in the considered region, and $1$ otherwise. Similarly, $y_i$ are variables for blue points.

Obviously, as the points are chosen arbitrarly in plane: $$\mathbb{P}(x_i = 0) = \mathbb{P}(x_i = 1) = \mathbb{P}(y_i = 0) = \mathbb{P}(y_i = 1) = 0.5$$

So, the expected values are: $$\mathbb{E}(x_i) = 0.5 \cdot 0 + 0.5 \cdot 1 = 0.5$$

Also, we'll get: $$\mathbb{E}(y_i) = 0.5$$

We know that: $$Z = \sum x_i - \sum y_i$$

Therefore, by Linearity of Expectation: $$\mathbb{E}(Z) = (n - 1) \cdot 0.5 - (n - 1) \cdot 0.5 = 0$$

And, by Probabilistic Method Lemma, there exists at least one 'good' line ('good' lines have $Z = 0$).

However, I'm not able to prove that there are two 'good' lines in this plane.