2014年第55届IMO试题

• 知识点

  >

  二试组合部分

略

本题的故事说来话长．我们从下面三个解答一步一步来看．
证法一
（$c=\sqrt{\dfrac{1}{2}}$ 的情形）．记这族直线为 $L$．考虑 $L$ 的一个（在集合包含意义下）极大子集 $B$，使得当我们把 $B$ 中的直线都染成蓝色时，没有边界全为蓝色的有限区域．记 $|B|=k$，我们来证明 $k\geqslant\lceil\sqrt{\frac{n}{2}}\rceil$．
我们首先把 $L\backslash B$ 中的所有直线染成红色．把两条蓝色直线的交点称为是一个蓝点．这样我们共有 $\binom{k}{2}$ 个蓝点．
现在我们来考虑一条红色直线 $l$．由 $B$ 的极大性，存在至少一个有限区域 $A$，使得其唯一的红边在 $l$ 上．因为 $A$ 至少有三条边，
所以它必有一个顶点是蓝点．我们把一个这样的蓝点与 $l$ 关联起来．
因为每个蓝点至多是四个有限区域的顶点，它至多和四条红色直线相关联．这样红色直线的总数就不超过 $4\binom{k}{2}$．于是我们就有不等式 $n-k\leqslant 2k(k-1)$，即 $n\leqslant 2k^2 -k \leqslant 2k^2$．
从而我们得到 $k\geqslant\lceil\sqrt{\dfrac{n}{2}}\rceil$，证毕．
这是预选题中的原题，选题委员会认为这是一个中等难度的组合问题（在总共 $9$ 个组合题中排在第 $5$ 个）．另外一点是原题是证明对于 $n\geqslant 3$，结论都成立．
然后选题委员会在预选题的脚注里给出了下面两个改进的解答：
证法二
（$c=\sqrt{\dfrac{2}{3}}$ 的情形）我们略微改变一下蓝点和红线的关联方式：对于一条红色直线 $l$，有一个有限区域 $A$ 的唯一的红边是红色直线 $l$ 的一部分．如果 $A$ 是 $k$ 边形，那么 $A$ 就有 $k-2$ 个顶点都是蓝点．把它们都和直线 $l$ 相关联．我们规定，对于其中每一个蓝色顶点和 $l$ 的关联，我们都记其权重为 $\dfrac{1}{k-2}$．这样所有的关联的权重之和恰为 $n-k$．
容易验证，每个蓝点 $v$ 最多是四个有限区域的顶点，且其中最多有两个区域是三角形．这就意味着和 $v$ 相关的所有蓝点--直线关联的权重之和不超过 $1+1+\dfrac{1}{2}+\dfrac{1}{2}=3$．
这样我们就有 $n-k\leqslant 3\binom{k}{2}$，即 $2n\leqslant 3k^2 -k<3k^2$．由此可得 $k\geqslant \lceil\sqrt{\dfrac{2n}{3}}\rceil$．
证法三
（$c=1$ 的情形）称一个点是红点，如果它是一条红色直线和一条蓝色直线的交点．对于一条红色直线 $l$，有一个有限区域 $A$ 的唯一的红边是红色直线 $l$ 的一部分．按顺时针方向记其顶点为 $r',r,b_1 , \ldots , b_k$，
其中 $r$ 和 $r'$ 在 $l$ 上．这样 $r$ 和 $r'$ 是红点，$b_1 , \ldots , b_k$ 都是蓝点．我们把红色直线 $l$ 和红点 $r$ 以及蓝点 $b_1$ 关联起来．我们注意到对于每一个形如 $(r,b_1 )$ 的（红点，蓝点）对，最多有一条红色直线可能和它们关联，因为至多有一个有限区域可以使得 $r,b_1$ 是其边界上顺时针方向的相邻顶点．
现在我们来证明，对于每一个蓝点 $b$，至多有两条红色直线可以与之关联
（如果这条性质成立，那么我们就有 $n-k\leqslant 2\binom{k}{2}\Leftrightarrow n\leqslant k^2$．
用反证法．若不然，设红色直线 $l_1 , l_2$ 和 $l_3$ 都和蓝点 $b$ 相关联．设相应的红点为 $r_1 ,r_2$ 和 $r_3$（这显然是互异的三点）．从蓝点 $b$ 引出四条蓝色的射线，这三个红点是其中三条上和 $b$ 最接近的交点．因此我们不妨设 $r_2 , b$ 和 $r_3$ 共线，而 $r_1$ 在另一条直线上．
在我们来考虑把 $(r_1 , b)$ 与红色直线 $l_1$ 关联起来的区域 $A$，这样 $A$ 的边界上顺时针方向依次有 $r_1 , b$ 和 $r_2$ 或 $r_3$（不妨设为 $r_2$）．因为 $A$ 只有一条红边，所以它只能是三角形 $r_1 b r_2$．但这样一来红色直线 $l_1$ 和 $l_2$ 就都要经过点 $r_2$，而且 $r_2$ 还要在一条蓝色直线上．与任意三线不共点的假设矛盾．证毕．