昨天收到一封邮件:
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 这名字怎么这么熟悉呀…… 仔细一看还是上同一个论坛的……
我好像是可以证明的。只要证明不全部共线的N个红点所能构成的直线有N条,那么至少有N个绿点,反过来就说明红点和绿点都只可能是N个,然后再分析这一种特殊情况就是了……
只是感觉这种证法不美……
M67大神,最近我在校内上也有发跟数学和逻辑有关的帖子,希望大神有空来捧一下场哦~~隔壁清华的,黄昆
若有一直线无红点 则为所求直线 若都有红点 则两直线各取一红点其连线即所求
当有且最多有a-m个绿点在一条直线l上