作业帮 > 数学 > 作业

求证世界上六个人中,有三个人互相认识,否则就有三个人互相不认识!

来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/06/23 16:13:39
求证世界上六个人中,有三个人互相认识,否则就有三个人互相不认识!
求证世界上六个人中,有三个人互相认识,否则就有三个人互相不认识!
我懂
再问: 说
再答: 认识等于不认识,不认识等于认识,说你认识其实也不认识,说你不认识其实还认识,最后你到底是认识还是不认识,你也想不明白你是不认识还是认识~~累~~~~
正经的说
这道题是Ramsey定理,是一道简单的图论问题。
证明如下:
首先,把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设:如果两个人识,则设这两个人组成的线段为红色;如果两个人不认识,则设这两个人组成的线段为蓝色。由抽屉原则可知:这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若BC或CD为红色,则结论显然成立。若BC和CD均为蓝色,则若BD为红色,则一定有三个人相互认识;若BD为蓝色,则一定有三个人互相不认识
再答: 采纳采纳采纳
再问: 谢了