MathLabs

第6题

平面上一组直线称为处于一般位置,如果其中任何两条都不平行,任何三条都不共点。处于一般位置的一组直线把平面分成若干区域,其中一些具有有限面积;称这些为其有限区域。证明:对一切充分大的 nn,在处于一般位置的任意 nn 条直线组成的集合中,总能把其中至少 n\sqrt{n} 条染成蓝色,使得没有一个有限区域的边界完全是蓝色的。
第 6/6 步：结论
上一步下一步
n large  ⟹  k≥n blue lines, no finite region entirely bluen \text{ large} \implies k \ge \sqrt{n} \text{ blue lines, no finite region entirely blue}
详细分析

该构造总会终止(未着色直线数严格递减),由正确性一步可知总能保持每个有限区域都不是单色,由计数界限总能得到至少 ⌈n⌉≥n\lceil\sqrt n\rceil\ge\sqrt n 条蓝色直线。这对一切 n≥2n\ge2 都成立,特别对一切充分大的 nn 成立,从而证明了命题。