有一个怪怪的奥数题题：对世界上任何六个人来说,其中至少有三个人,他们要么互相都认识,要么互相都不认识.请说明这是为什么?
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/06 02:15:05
有一个怪怪的奥数题题：对世界上任何六个人来说,其中至少有三个人,他们要么互相都认识,要么互相都不认识.请说明这是为什么?
有一个怪怪的奥数题
题：对世界上任何六个人来说,其中至少有三个人,他们要么互相都认识,要么互相都不认识.请说明这是为什么?
有一个怪怪的奥数题题：对世界上任何六个人来说,其中至少有三个人,他们要么互相都认识,要么互相都不认识.请说明这是为什么?
因为“至少有三个人,他们要么互相都认识,要么互相都不认识."这句话包含了所有的情况
如果6个人都不相互认识,那么6>3,符合至少三个都不认识的
如果2两个人相互认识,那么4个人相互不认识,符合至少三个都不认识的
如果3个互相认识,符合至少3个相互认识的
如果4个或5个或6个相互认识,都是符合至少3个互相认识的
这道题是Ramsey定理，是一道简单的图论问题。
证明如下：
首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设：如果两个人识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。由抽屉原则可知：这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若BC或CD为红色，则结论显然成...
全部展开
这道题是Ramsey定理，是一道简单的图论问题。
证明如下：
首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设：如果两个人识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。由抽屉原则可知：这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若BC或CD为红色，则结论显然成立。若BC和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识。
收起
这不是奥数！