Problem 6

A set of lines in the plane is in general position if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; call these its finite regions. Prove that for all sufficiently large

n

, in any set of

n

lines in general position it is possible to colour at least

\sqrt{n}

of the lines blue in such a way that none of its finite regions has a completely blue boundary.

Step 5 of 6: Counting bound: k blue lines force n ≤ k²

Previous step Next step

n-k \le 2\binom{k}{2} = k(k-1) \implies k \ge \sqrt{n}

Detailed analysis

Suppose the process ends with $k$ blue lines. Every non-blue line must contain at least one red point (otherwise the process would not have stopped), and every red point lies on exactly one blue line and one non-blue line (it is created as a neighbour of a blue-blue crossing point along a line that was not yet blue). Since coloring the $t$ -th blue line creates at most $t-1$ new blue crossing points, each contributing at most $2$ red points, the total number of red points is at most $2\binom{k}{2}=k(k-1)$ . As each of the $n-k$ non-blue lines needs at least one red point on it, $n-k\le k(k-1)$ , i.e. $n\le k^2$ , so $k\ge\sqrt n$ .