MathLabs

第6题

平面上一组直线称为处于一般位置,如果其中任何两条都不平行,任何三条都不共点。处于一般位置的一组直线把平面分成若干区域,其中一些具有有限面积;称这些为其有限区域。证明:对一切充分大的 nn,在处于一般位置的任意 nn 条直线组成的集合中,总能把其中至少 n\sqrt{n} 条染成蓝色,使得没有一个有限区域的边界完全是蓝色的。
第 1/6 步:准备:点、相邻关系,以及作为多边形的有限区域
(n2) intersection points; each line carries n−1 of them\binom{n}{2} \text{ intersection points; each line carries } n-1 \text{ of them}
详细分析

把这 (n2)\binom{n}{2} 个两两交点简称为点;nn 条直线中每条都携带其中 n−1n-1 个点。同一直线上的两点若该直线上没有其他点严格位于二者之间,则称为相邻。于是每个有限区域都是一个凸多边形,其沿每条边界直线的相邻顶点彼此相邻。