第6题

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

n

,在处于一般位置的任意

n

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

\sqrt{n}

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

第 3/6 步：计费规则:每个蓝色交点至多产生两个新红点

上一步下一步

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

详细分析

当直线 $\ell$ 新染成蓝色时,对 $\ell$ 与已有蓝色直线 $\ell_1$ 的每个交点 $X$ ,把 $X$ 染成蓝色,并考察 $X$ 在 $\ell$ 上与在 $\ell_1$ 上的相邻点,即 $\ell$ 上的 $A_1,A_2$ 与 $\ell_1$ 上的 $B_1,B_2$ (若缺少相邻点则用未着色的虚拟点代替)。若 $A_1$ 、 $A_2$ 都尚未染蓝,则把两者都染红;否则若 $B_1$ 、 $B_2$ 都尚未染蓝,则把两者都染红;否则把这四点中剩余未着色的(至多两个)染红。这样每个蓝色交点 $X$ 至多新增 $2$ 个红点。