第6题

平面上一组直线称为处于一般位置,如果其中任何两条都不平行,任何三条都不共点。处于一般位置的一组直线把平面分成若干区域,其中一些具有有限面积;称这些为其有限区域。证明:对一切充分大的

n

,在处于一般位置的任意

n

条直线组成的集合中,总能把其中至少

\sqrt{n}

条染成蓝色,使得没有一个有限区域的边界完全是蓝色的。

第 4/6 步：正确性:没有有限区域最终全为蓝色

上一步下一步

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

详细分析

按构造,蓝色直线不会经过红点(一个点只有在其所在直线仍未着色时才会被染红)。反证:设某个有限区域 $P_1\cdots P_m$ 的每条边界都是蓝色;考察 $P_1,\ldots,P_m$ 中最先变蓝的顶点,设为 $P_2$ ,且边 $P_1P_2$ 比 $P_2P_3$ 稍晚被染色。那么此时 $P_3$ 必仍未着色(否则 $P_3$ 会更早变蓝),而当 $P_1$ 作为 $P_2$ 处新蓝色交点的相邻点被考察时,计费规则会把 $P_1,P_3$ 中至少一个染红——这与所有顶点都是蓝色矛盾。因此没有有限区域是完全蓝色的。