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 4 of 6: Correctness: no finite region ends up entirely blue

Previous step Next step

\text{no blue line passes through a red point} \implies \text{no finite region is entirely blue}

Detailed analysis

By construction, no blue line ever passes through a red point (a point is coloured red only while its line is still uncoloured). Suppose for contradiction some finite region $P_1\cdots P_m$ had every boundary side blue; consider the first vertex among $P_1,\ldots,P_m$ to become blue, say $P_2$ , with side $P_1P_2$ coloured slightly later than $P_2P_3$ . Then $P_3$ must still be uncoloured at that time (else $P_3$ would have turned blue first), and once $P_1$ is examined as a neighbour of $P_2$ across a newly blue crossing, the charging rule colours at least one of $P_1,P_3$ red — contradicting that all vertices are blue. Hence no finite region is entirely blue.