发新话题
打印【有0个人次参与评价】

[求助] 题目求助

至少3人,染色然后反复使用抽屉原理,拉姆塞定理的应用。

[ 本帖最后由 smartwxc 于 2008-12-10 10:34 编辑 ].

TOP

3人是必然的,4是可能不成立的,证明如下:
把9人看成9点v1,v2,v3,v4,v5,v6,v7,v8,v9
如两人会同一种语言就在两点间联线并染相应的颜色。如此构成一个简单图(每三点至少有一边),不失一般性地用点V1讨论,
分两种情况分析:
1)v1与其他8点都相邻(即有连线),由抽屉原理(至多三种语言)得至少有两边同色,不妨设为(V1,V2),(V1,V3)。显而易见v1、v2、v3为同色三角形。即1,2,3三人讲同一语言。
2)点V1与其他8点中至于少一点(设其为v2)不相邻,因每三点至少有一边。故V3......V9发出到v1 或V2的边至少有7条,且至少有4条是连接同一点。设此点为v1,边为(v1,v3),(v1,v4),(v1,v5),(v1,v6)。因为从v1出发的边至多有三种颜色,故上述4边必有两条同色。设为(v1,v3),(v1,v4),则三角形v1v3v4为同色。1、3、4三人讲同种语言。把图画一下看起来会简单些。.

TOP

按我证明的思路可以画一个反例,不会用画图工具,不好意思,您自己试一下。.

TOP

发新话题