MathLabs

第6题

平面上一组直线称为处于一般位置,如果其中任何两条都不平行,任何三条都不共点。处于一般位置的一组直线把平面分成若干区域,其中一些具有有限面积;称这些为其有限区域。证明:对一切充分大的 nn,在处于一般位置的任意 nn 条直线组成的集合中,总能把其中至少 n\sqrt{n} 条染成蓝色,使得没有一个有限区域的边界完全是蓝色的。
第 2/6 步:贪心地扩大蓝色直线集合 B
B←B∪{ℓ} whenever ℓ is uncoloured and passes through no red pointB \leftarrow B \cup \{\ell\} \text{ whenever } \ell \text{ is uncoloured and passes through no red point}
详细分析

分轮次给直线和点上色。初始时所有直线和点都未着色。重复以下过程:只要存在未着色直线 ℓ\ell 不经过任何红点,就把 ℓ\ell 染成蓝色,并把 ℓ\ell 与已有蓝色直线的每个交点也染成蓝色,然后按下一步继续处理。当剩余的每条未着色直线都已经过某个红点时停止。