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 3 of 6: Charging rule: at most two new red points per blue crossing

Previous step Next step

X = \ell_1 \cap \ell_2 \text{ (both blue)} \implies \text{colour } X \text{ blue; mark } \le 2 \text{ neighbours of } X \text{ red}

Detailed analysis

When line $\ell$ is newly coloured blue, for each intersection $X$ of $\ell$ with a line $\ell_1$ already blue, colour $X$ blue and look at the neighbours of $X$ on $\ell$ and on $\ell_1$ , say $A_1,A_2$ on $\ell$ and $B_1,B_2$ on $\ell_1$ (using an uncoloured dummy point if a neighbour is missing). If neither $A_1$ nor $A_2$ is already blue, colour both red; otherwise if neither $B_1$ nor $B_2$ is blue, colour both red; otherwise colour whichever of the (at most two) remaining uncoloured points among these four red. This adds at most $2$ red points per blue intersection point $X$ .