2007-12-19 11:49| 
13 Comments | 本文内容遵从昨天收到一封邮件：
Matrix67：
我最近发现了一个我无法解决的问题。题目如下：
平面上有n(n>=3)个点不全共线，一部分是红色的，其它是绿色的，是否一定存在一条直线满足：
(1) 通过这些点中至少两个；
(2) 它通过的点颜色全部相同。
我在百度知道上发过此问题两次，告诉了学校的N个人，但还未能解决，希望你能帮助我。
一位痴迷于数学的网友
我当然不大可能会做出来，毕竟我也只是一个数学爱好者，不是搞MO的。因此把题目发到这里，大家可以一起来讨论。
这道题和我之前看过的一道经典题目很相似：若n个点不全共线，则必存在一条直线恰好穿过两个点。证明方法很巧妙，画出所有两点确定的直线，作出每一个点到每一条直线的垂线，找出这些垂线中最短的一条，然后你会发现，假设每条直线上都有至少三个点的话，我总能找到比这条垂线段更短的垂线（大家可以自己试试看）。注意到，这个题目要求证明“若任何两点的连线上都有另一个点，则所有点共线”，而上面的题目则要求证明“若任何同色两点的连线上都有另一个异色点，则所有点共线”。这两个问题间有没有什么联系？我感觉，区分颜色的话命题似乎更强一些。我曾尝试找反例，每一次都是只差那么一点就成功了，但对于我提到的老问题，即使想找出一个很“悬”的情况也不太容易。
这道题是原创的吗？如果是原创的话就真的强了。
我正看到起你就更新了嗦
简单看下,没看明白
平面上如果只有3点,那么必然有2点共线.
颜色也必存在相同的呀.
回复：如果点的位置足够特殊，同色点的连线上可能总存在异色点
极限情况是 n(无穷)时,n个点以线的形式将平面布满,其中最中间的点为R颜色,之后一个圈的G颜色点将其紧紧围住,之后外圈在放一个圈的R颜色点将内圈紧紧围住...依次类推,直到布满整个平面...
没怎么明白.
n>=3，必然有一个颜色至少有两个啊，于是肯定成立的。。
matrix牛再讲讲？
回复：有可能连线上有别的点，而点的颜色恰好又与那两个点的颜色不同
设a个绿点b个红点 a>=b
当有且最多有a个绿点在一条直线上 显然成立
当有且最多有a-1个绿点在一条直线上 也不难证明
当有且最多有a-2个绿点在一条直线上
若直线与直线外两点组成的直线交于一红点则
若两直线外无红点 则两直线各取一绿点其连线即所求 若有红点则其与交点的连线即所求
若直线与直线外两点组成的直线交于一红点则
若有一直线无红点 则为所求直线 若都有红点 则两直线各取一红点其连线即所求
当有且最多有a-m个绿点在一条直线l上
若直线l上无红点 则直线l为所求
若有 则连接该红点与直线外的点做n(n<m)条红绿直线 若有红点在这些红绿直线外 则两红点连线为所求
若没有 则取任取两绿点做绿绿直线 若这些直线中存在没有红点的直线则为所求
若没有 红点的个数至少为
f 写不下去了 以后再说吧
jjymhkx0820 举的反例似乎已经证明您的问题不可能了吧
haha 不是的哈, 当点的个数由可数趋于无穷的时候,命题的性质会发生质的变化.所以极限情况下不成立，并不一定一般非无穷情况下也不成立哈.
以上@!!!!!!!!!
我觉得这题可以用极端原则证出来……
思考ing。
还是一个想法（最近有点搞不懂什么是正确的）
n个点一共能构成C(n, 2)条线（共线的重复计算）
设有k个红点，则(n - k)个绿点
随便找一个红点和一个绿点，组成的直线有k * (n - k)条，最多有(n * n / 4)条
当n>=3时 (n * n / 4) 比 C(n, 2) 小
不知道对不对
(n * n / 4) 比 C(n, 2) 小能说明什么问题呢？
能说明肯定存在两个同色点能连线？
怎么保证他们不穿过异色点？
我在书上看到了完整的证明~~~用欧拉公式证明的~~~看这里：
http://fwjmath.spaces.live.com/blog/cns!6A37A2A4F21FF4DE!856.entry
It is called Motzkin-Rabin theorem. Look here:
http://citeseer.ist.psu.edu/cache/papers/cs/27665/http:zSzzSzmaths.unisa.ac.zazSz~swanekjzSzmotzkin-rabin.pdf/pretorius02algorithmic.pdf
But the proof by fwjmath is much easier and more interesting.
看 fwjmath 这名字怎么这么熟悉呀…… 仔细一看还是上同一个论坛的……