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 2 of 6: Greedily grow a blue set B of lines

Previous step Next step

B \leftarrow B \cup \{\ell\} \text{ whenever } \ell \text{ is uncoloured and passes through no red point}

Detailed analysis

Colour lines and points in rounds. Start with all lines and points uncoloured. Repeatedly: while some uncoloured line $\ell$ passes through no red point, colour $\ell$ blue, colour every intersection of $\ell$ with an already-blue line blue as well, and continue as in the next step. Stop when every remaining uncoloured line already passes through a red point.