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 1 of 6: Setup: points, neighbours, and finite regions as polygons

Previous step Next step

\binom{n}{2} \text{ intersection points; each line carries } n-1 \text{ of them}

Detailed analysis

Call the $\binom{n}{2}$ pairwise intersection points simply points; each of the $n$ lines carries $n-1$ of them. Two points on the same line are neighbours if no other point of that line lies strictly between them. Every finite region is then a convex polygon whose consecutive vertices along each bounding line are neighbours.