MathLabs

第2题

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

每对同色点都可放在两条平行线围成的窄带中。

2013=1+2⋅10062013=1+2\cdot1006
详细分析

第一次切割后,第一种情形还剩 2012 个红点,第二种情形还剩 2012 个蓝点。任意将这 2012 个点配成对子。对每对子 {A,B},画两条平行于 AB 且足够靠近 AB 的直线,使两线之间的闭带不含其他配置点。于是每对子被隔离在单色区域中,共需 2⋅10062\cdot1006 条直线。