作业帮 > 数学 > 作业

证明 至少2个人的聚会中 存在2个人认识其他人的人数是相等的

来源：学生作业帮 编辑：拍题作业网作业帮 分类：数学作业 时间：2024/05/27 21:26:52
证明 至少2个人的聚会中 存在2个人认识其他人的人数是相等的
应该是存在至少2个人认识其他人的人数是相等的
这问题应该属于拉姆塞理论的范畴,是数学中严格证明起来难度极高的一类问题,最早由英国天才数学家拉姆塞提出,也是通常所说的"抽屉原理"的基础.
拉姆塞定理是说：在一个聚会中,当聚会人数大于或等于6时,则必定有3个人彼此认识或者彼此都不认识
拉姆塞定理的证明通常用图论的方法,大体思路就是用六个点代表参加聚会的六个人,将相互认识的两个人用红线连接,不认识的用蓝线连接,这样就得到一个由六个点以及六个点之间的15条线构成的图形.结果是,不论你怎么连接,总能够出现一个三边全为红线或者三边全为蓝线的三角形,说明六个人中总有三个人互相认识或者互相不认识,这就证明了拉姆塞定理.
上面都是废话,关键是介绍了一种证明方法,看看就行,因为具体到你的问题就简单多了,用一般的抽屉原理就行.
你的问题是：至少两人的聚会中,总有两人认识其他人的数目相同.
证明：用N≥2个点表示参加聚会的人,将相互认识的两个人用红线连接,不认识的用蓝线连接,那么任意一个点都至少发出一条红线；因为如果连接某个点的线全是蓝色的,说明这个人跟其他所有人都不认识,其他所有人也都不认识他,在一个聚会中是不可能存在这种人的,所以不存在全由蓝线连接的点.
共有N个点,容易知道,每个点都发出N-1条线,且这N-1条线中最多有N-2条蓝线.
只要证明存在两个点,这两个点发出的蓝线的条数相等就可以了(蓝线条数相等,则红线条数比必然相等,两者之和总为N-1),采用抽屉原理一下子就出来了.
假设从任意两个点出发的蓝线条数都不一样,已知有N个点,这就要求蓝线的条数有N种情况,但是前面已经证明蓝线至多有N-2条,不能提供N种情况,所以"从任意两个点出发的蓝线条数都不一样"的假设不成立,并且至少存在两个点,从这两点出发的蓝线数目一样,红线数目也一样,从而证明至少两人的聚会中,总有两人认识其他人的数目相同
有11个人,其中任何3人中有2人认识,证明在这11人中至少有一人认识其余10人中的5个人 n个人在一起聚会,其中至少有一个人没有和其他所有人不握手,聚会中可能和每个人都握手的人数最大值是多少? 4个人中,至少有2个人的生日同月的概率是________ 证明6个人中或者存在3个人相互认识,或者存在3个人相互不认识 证明：任意28个人中,至少有3个人的属相相同. 用反证法证明13个人中至少有两个人的生日在同一个月 图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中 有三个人认识,某天他们各自乘火车外出,若火车有10节车厢,那么至少有2个人在同一车厢的概率是 50个人中,至少有2个人生日相同的概率为多少? 任意13个人中,至少有2个人在同一个月岀生的.为什么? 4个人中,至少有2人的生日是同一个月的概率是? 某次会议有25人参加,每人至少认识1个人.在这25人中至少有两人认识的人数相同你知道为什么吗?