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 6 of 6: Conclusion

Previous step Next step

n \text{ large} \implies k \ge \sqrt{n} \text{ blue lines, no finite region entirely blue}

Detailed analysis

The construction always terminates (the number of uncoloured lines strictly decreases), always keeps every finite region non-monochromatic by the correctness step, and always ends with at least $\lceil\sqrt n\rceil\ge\sqrt n$ blue lines by the counting bound. This holds for every $n\ge2$ , and in particular for all sufficiently large $n$ , proving the statement.