MathLabs

第2题

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

被隔离的点或对子是单色的,而窄带外剩余各区域只含另一种颜色。

k≤1+2⋅1006=2013k\le1+2\cdot1006=2013
详细分析

将辅助直线取为一般位置且足够靠近,保证没有直线经过配置点。每个隔离带恰含其同色对子(或凸包上的单点),所有带外的点都为另一颜色。因此没有区域同时含两种颜色,证明 2013 条直线足够。