MathLabs

第2题

平面上 40274027 个点组成的一个配置,若由 20132013 个红点和 20142014 个蓝点组成,且配置中任何三点都不共线,则称为哥伦比亚配置。画若干条直线,可将平面分成若干区域。对某个哥伦比亚配置,若一组直线满足以下两个条件,就称这组直线的排列是好的:(1) 没有一条直线经过配置中的任何点;(2) 没有一个区域同时包含两种颜色的点。求最小的 kk,使得对任意的 40274027 点哥伦比亚配置,都存在由 kk 条直线组成的好排列。
第 1/5 步：由交替着色凸多边形得到下界
上一步下一步
通俗地说

每个红蓝边界间隙都必须被穿过，而一条直线至多两次穿过多边形边界。

k≥40262=2013k\ge\frac{4026}{2}=2013
详细分析

在凸 4026 边形顶点上交替放置 2013 个红点与 2013 个蓝点，再把剩余蓝点置于别处的一般位置。4026 条边的两端颜色相反，因此任何好排列都必须穿过每条边。一条直线至多两次与多边形边界相交，故 k≥4026/2=2013k\ge4026/2=2013。