平面上的 $4027$ 个点称为是一个哥伦比亚式点集，如果其中任意三点不共线，且有 $2013$ 个点是红色的，$2014$ 个点是蓝色的．在平面上画出一组直线，可以将平面分成若干区域．如果一组直线对于一个哥伦比亚式点集满足下述两个条件，我们就称这是一个好直线组：
（1）这些直线不经过该哥伦比亚式点集中的任何一个点；
（2）每个区域中都不会同时出现两种颜色的点．
求 $k$ 的最小值，使得对于任意的哥伦比亚式点集，都存在由 $k$ 条直线构成的好直线组．（澳大利亚）
（1）这些直线不经过该哥伦比亚式点集中的任何一个点；
（2）每个区域中都不会同时出现两种颜色的点．
求 $k$ 的最小值，使得对于任意的哥伦比亚式点集，都存在由 $k$ 条直线构成的好直线组．（澳大利亚）
【难度】
【出处】
2013年第54届IMO试题
【标注】
【答案】
略
【解析】
证法一
答案是 $k=2013$．
首先，我们举一个例子说明 $k\geqslant 2013$．在一个圆周上顺次交替标记 $2013$ 个红点和 $2013$ 个蓝点，在平面上另外任取一点染上蓝色．这个圆周就被分成了 $4026$ 段弧，每一段的两个端点都被染了不同的颜色．这样，如果题目的要求被满足，那么每一段弧都要和某条画出的直线相交．因为每条直线和圆周至多有两个交点，所以至少要有 $\frac{4026}{2}=2013$ 条直线．
下面证明用 $2013$ 条直线总能满足要求．首先，我们注意到对于任意两个同色的点 $A$ 和 $B$．都可以用两条直线把它们和其他的点分离．具体的做法是在直线 $AB$ 的西侧作两条和 $AB$ 平行的直线，只要它们足够接近 $AB$．它们之间的带状区域里就会只有 $A$ 和 $B$ 这两个染色点．
现在设 $P$ 是所有染色点的凸包．有以下两种情况：
情形一：假设 $P$ 有一个红色顶点，不妨仍记为 $A$．那么我们可以作一条直线，把 $A$ 和所有其他的染色点分隔开来．这样余下的 $2012$ 个红点可以组成 $1006$ 对，每对可以用两条平行直线和所有其他的染色点分隔开来，所以总共用 $2013$ 条直线可以达到要求．
情形二：假设 $P$ 的所有顶点都是蓝的．考虑 $P$ 上的两个相邻顶点，
不妨记为 $A$ 和 $B$．那么用一条直线就可以把这两个点和其他所有染色点分隔开来．这样余下的 $2012$ 个蓝点可以分为 $1006$ 对，每一对可以用两条直线和其他所有染色点分隔开．这样总共也用了 $2013$ 条直线．
注：我们可以不考虑凸包，而只考虑一条过两个染色点 $A$ 和 $B$ 的直线，
使得所有其他染色点都在这条直线的一侧．如果 $A$ 和 $B$ 中有一个红点，
则可以和上述情形1那样进行操作，如果 $A$ 和 $B$ 都是蓝点，则可以和上述情形2那样进行操作．
证法二
我们给出 $2013$ 条直线就可以达到要求的另一个证明．事实上，我们有更一般的结论：
如果在平面上有 $n$ 个标记点，没有三点共线，任意地染红色或者蓝色，那么用 $\lfloor n/2 \rfloor$ 条直线就可以满足题目的要求．
我们对 $n$ 归纳．如果 $n\leqslant 2$，那么结论是显然的．下面假设 $n\geqslant 3$，考虑一条过两个染色点 $A$ 和 $B$ 的直线 $l$，使得所有其他染色点都在这条直线 $l$ 的一侧．例如全体染色点的凸包的一条边就是这样的直线．
暂时把 $A$ 和 $B$ 从我们考虑的范围内除去．由归纳假设，余下的点可以用 $\lfloor n/2 \rfloor -1$ 条直线达到要求，现在重新把 $A$ 和 $B$ 点加回去．有三种情况．
情形一：
如果 $A$ 和 $B$ 同色，那么我们可以作一条和 $l$ 平行的直线，把 $A$ 和 $B$ 与其他的染色点分隔开来．显然，这样得到的 $\lfloor n/2 \rfloor$ 条直线可以达到要求．
情形二：
如果 $A$ 和 $B$ 不同色，但是它们之间由某条已经画出的直线分隔开，那么这样上述和 $l$ 平行的直线同样满足要求．
情形三：最后假设 $A$ 和 $B$ 不同色，且在作出上述 $\lfloor n/2 \rfloor -1$ 条直线以后，位于同一个区域内．由归纳假设，
至少有一种颜色，在该区域中不会有另外的染色点．不失一般性，假设该区域中唯一的蓝点是 $A$．那么我们只要作一条直线把 $A$ 和其他所有染色点分隔开来即可．
这样我们就完成了归纳步骤．
注：我们可以问一个更一般的问题，把 $2013$ 和 $2014$ 替换为任意的正整数 $m$ 和 $n$，不妨假设 $m\leqslant n$．记相应的问题的解为 $f(m,n)$．
我们可以按照解法一的思路得到 $m\leqslant f(m,n)\leqslant m+1$；而且如果 $m$ 是偶数，那么 $f(m,n)=m$．另一方面，对于 $m$ 是奇数的情形，存在一个 $N$，使得对于任意的 $m\leqslant n\leqslant N$，$f(m,n)=m$，而对任意的 $n>N$，$f(m,n)=m+1$．
答案是 $k=2013$．
首先，我们举一个例子说明 $k\geqslant 2013$．在一个圆周上顺次交替标记 $2013$ 个红点和 $2013$ 个蓝点，在平面上另外任取一点染上蓝色．这个圆周就被分成了 $4026$ 段弧，每一段的两个端点都被染了不同的颜色．这样，如果题目的要求被满足，那么每一段弧都要和某条画出的直线相交．因为每条直线和圆周至多有两个交点，所以至少要有 $\frac{4026}{2}=2013$ 条直线．
下面证明用 $2013$ 条直线总能满足要求．首先，我们注意到对于任意两个同色的点 $A$ 和 $B$．都可以用两条直线把它们和其他的点分离．具体的做法是在直线 $AB$ 的西侧作两条和 $AB$ 平行的直线，只要它们足够接近 $AB$．它们之间的带状区域里就会只有 $A$ 和 $B$ 这两个染色点．
现在设 $P$ 是所有染色点的凸包．有以下两种情况：
情形一：假设 $P$ 有一个红色顶点，不妨仍记为 $A$．那么我们可以作一条直线，把 $A$ 和所有其他的染色点分隔开来．这样余下的 $2012$ 个红点可以组成 $1006$ 对，每对可以用两条平行直线和所有其他的染色点分隔开来，所以总共用 $2013$ 条直线可以达到要求．
情形二：假设 $P$ 的所有顶点都是蓝的．考虑 $P$ 上的两个相邻顶点，
不妨记为 $A$ 和 $B$．那么用一条直线就可以把这两个点和其他所有染色点分隔开来．这样余下的 $2012$ 个蓝点可以分为 $1006$ 对，每一对可以用两条直线和其他所有染色点分隔开．这样总共也用了 $2013$ 条直线．
注：我们可以不考虑凸包，而只考虑一条过两个染色点 $A$ 和 $B$ 的直线，
使得所有其他染色点都在这条直线的一侧．如果 $A$ 和 $B$ 中有一个红点，
则可以和上述情形1那样进行操作，如果 $A$ 和 $B$ 都是蓝点，则可以和上述情形2那样进行操作．
证法二
我们给出 $2013$ 条直线就可以达到要求的另一个证明．事实上，我们有更一般的结论：
如果在平面上有 $n$ 个标记点，没有三点共线，任意地染红色或者蓝色，那么用 $\lfloor n/2 \rfloor$ 条直线就可以满足题目的要求．
我们对 $n$ 归纳．如果 $n\leqslant 2$，那么结论是显然的．下面假设 $n\geqslant 3$，考虑一条过两个染色点 $A$ 和 $B$ 的直线 $l$，使得所有其他染色点都在这条直线 $l$ 的一侧．例如全体染色点的凸包的一条边就是这样的直线．
暂时把 $A$ 和 $B$ 从我们考虑的范围内除去．由归纳假设，余下的点可以用 $\lfloor n/2 \rfloor -1$ 条直线达到要求，现在重新把 $A$ 和 $B$ 点加回去．有三种情况．
情形一：
如果 $A$ 和 $B$ 同色，那么我们可以作一条和 $l$ 平行的直线，把 $A$ 和 $B$ 与其他的染色点分隔开来．显然，这样得到的 $\lfloor n/2 \rfloor$ 条直线可以达到要求．
情形二：
如果 $A$ 和 $B$ 不同色，但是它们之间由某条已经画出的直线分隔开，那么这样上述和 $l$ 平行的直线同样满足要求．
情形三：最后假设 $A$ 和 $B$ 不同色，且在作出上述 $\lfloor n/2 \rfloor -1$ 条直线以后，位于同一个区域内．由归纳假设，
至少有一种颜色，在该区域中不会有另外的染色点．不失一般性，假设该区域中唯一的蓝点是 $A$．那么我们只要作一条直线把 $A$ 和其他所有染色点分隔开来即可．
这样我们就完成了归纳步骤．
注：我们可以问一个更一般的问题，把 $2013$ 和 $2014$ 替换为任意的正整数 $m$ 和 $n$，不妨假设 $m\leqslant n$．记相应的问题的解为 $f(m,n)$．
我们可以按照解法一的思路得到 $m\leqslant f(m,n)\leqslant m+1$；而且如果 $m$ 是偶数，那么 $f(m,n)=m$．另一方面，对于 $m$ 是奇数的情形，存在一个 $N$，使得对于任意的 $m\leqslant n\leqslant N$，$f(m,n)=m$，而对任意的 $n>N$，$f(m,n)=m+1$．
答案
解析
备注
