加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

六人相识问题

(2011-10-27 13:11:40)
标签:

拉姆赛

数学符号

组合数

表示

红色

分类: 自然奇趣

    著名的“六人相识问题”(它是拉姆赛(Ramsey)定理的特例):

    任何6个人中必可从中找出3人,他们要么彼此都相识,要么彼此都不相识。

    把这个抽象的问题演化成“点”与“染色直线”,从而巧妙地解答它,这不能不说是“符号”的一大功劳(要知道6人相互关系的可能组合数为32768)。

    把“人”用“点”表示,人与人的“关系”用“红、蓝两色线”表示:红线表示他们彼此相识,蓝线表示他们彼此不相识。这样六个人A,B,C,D,E,F中的某个人,比如A,他与其他5为的关系由于只有两种颜色表示,其中必有一种颜色的线不少于3条,无妨设AB,AC,AD三条,且他们为红色。

    接下去考虑B,C,D三点间的连线,若他们全为蓝色,即:BC,CD,BD均为蓝色,那好,B,C,D三点为所求(他们代表三个人彼此都不相识);若三点间连线至少有一条为红色,设它为BC,这时AB,AC,BC均为红色,则A,B,C三点为所求(他们代表三个人彼此都相识)。问题得证。

    其实我们还可以有进一步的结论:上述(彼此都相识或彼此都不相识的)“三人组”在六个人中至少存在两组。

    顺便讲一句:若要彼此相识或不相识的人数是4,则总人数要增至18;若前者人数是5(这时有10^200(表示10的200次方)种组合方式),而后者人数涨至43人——49人之间(具体人数至今不详);若前者人数是6,而后者人数将达102——165之间,确定它们是人们目前尚不可及的事。

    上面的事实,再次证明数学符号的威力,没有它至少问题的叙述会变得复杂而困难,或者根本无法表达清楚。

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有