早教吧作业答案频道 -->数学-->
证明至少2个人的聚会中存在2个人认识其他人的人数是相等的应该是存在至少2个人认识其他人的人数是相等的
题目详情
▼优质解答
答案和解析
这问题应该属于拉姆塞理论的范畴,是数学中严格证明起来难度极高的一类问题,最早由英国天才数学家拉姆塞提出,也是通常所说的"抽屉原理"的基础.
拉姆塞定理是说:在一个聚会中,当聚会人数大于或等于6时,则必定有3个人彼此认识或者彼此都不认识
拉姆塞定理的证明通常用图论的方法,大体思路就是用六个点代表参加聚会的六个人,将相互认识的两个人用红线连接,不认识的用蓝线连接,这样就得到一个由六个点以及六个点之间的15条线构成的图形.结果是,不论你怎么连接,总能够出现一个三边全为红线或者三边全为蓝线的三角形,说明六个人中总有三个人互相认识或者互相不认识,这就证明了拉姆塞定理.
上面都是废话,关键是介绍了一种证明方法,看看就行,因为具体到你的问题就简单多了,用一般的抽屉原理就行.
你的问题是:至少两人的聚会中,总有两人认识其他人的数目相同.
证明:用N≥2个点表示参加聚会的人,将相互认识的两个人用红线连接,不认识的用蓝线连接,那么任意一个点都至少发出一条红线;因为如果连接某个点的线全是蓝色的,说明这个人跟其他所有人都不认识,其他所有人也都不认识他,在一个聚会中是不可能存在这种人的,所以不存在全由蓝线连接的点.
共有N个点,容易知道,每个点都发出N-1条线,且这N-1条线中最多有N-2条蓝线.
只要证明存在两个点,这两个点发出的蓝线的条数相等就可以了(蓝线条数相等,则红线条数比必然相等,两者之和总为N-1),采用抽屉原理一下子就出来了.
假设从任意两个点出发的蓝线条数都不一样,已知有N个点,这就要求蓝线的条数有N种情况,但是前面已经证明蓝线至多有N-2条,不能提供N种情况,所以"从任意两个点出发的蓝线条数都不一样"的假设不成立,并且至少存在两个点,从这两点出发的蓝线数目一样,红线数目也一样,从而证明至少两人的聚会中,总有两人认识其他人的数目相同
拉姆塞定理是说:在一个聚会中,当聚会人数大于或等于6时,则必定有3个人彼此认识或者彼此都不认识
拉姆塞定理的证明通常用图论的方法,大体思路就是用六个点代表参加聚会的六个人,将相互认识的两个人用红线连接,不认识的用蓝线连接,这样就得到一个由六个点以及六个点之间的15条线构成的图形.结果是,不论你怎么连接,总能够出现一个三边全为红线或者三边全为蓝线的三角形,说明六个人中总有三个人互相认识或者互相不认识,这就证明了拉姆塞定理.
上面都是废话,关键是介绍了一种证明方法,看看就行,因为具体到你的问题就简单多了,用一般的抽屉原理就行.
你的问题是:至少两人的聚会中,总有两人认识其他人的数目相同.
证明:用N≥2个点表示参加聚会的人,将相互认识的两个人用红线连接,不认识的用蓝线连接,那么任意一个点都至少发出一条红线;因为如果连接某个点的线全是蓝色的,说明这个人跟其他所有人都不认识,其他所有人也都不认识他,在一个聚会中是不可能存在这种人的,所以不存在全由蓝线连接的点.
共有N个点,容易知道,每个点都发出N-1条线,且这N-1条线中最多有N-2条蓝线.
只要证明存在两个点,这两个点发出的蓝线的条数相等就可以了(蓝线条数相等,则红线条数比必然相等,两者之和总为N-1),采用抽屉原理一下子就出来了.
假设从任意两个点出发的蓝线条数都不一样,已知有N个点,这就要求蓝线的条数有N种情况,但是前面已经证明蓝线至多有N-2条,不能提供N种情况,所以"从任意两个点出发的蓝线条数都不一样"的假设不成立,并且至少存在两个点,从这两点出发的蓝线数目一样,红线数目也一样,从而证明至少两人的聚会中,总有两人认识其他人的数目相同
看了证明至少2个人的聚会中存在2个...的网友还看了以下:
从1909年到1911年,卢瑟福等人无数次用α粒子流轰击金箔,发现了原子的内部结构.关于原子的结构 2020-04-06 …
据统计,在某银行的一个营业窗口等候的人数及其相应的概率如下:排队人数题0人1人2人3人4人5人及5 2020-04-11 …
甲数等于2*3*5*a,乙数等于2*3*7*a,那么当a等于()时,甲乙两数的最大公应数是30?当 2020-04-27 …
1、学校合唱团比舞蹈队多24人·,合唱团人数的2/5等于舞蹈队人数的6/7,问合唱团和舞蹈队各有多 2020-05-16 …
1、4分之3于5分之2的和等于一个数的8分之3,这个数是多少?2、甲数的百分之25等于乙数的3分之 2020-05-16 …
1.人数相等的甲乙两组工人,在一天中甲组工人全部出勤,加工零件100个,乙组缺勤2人,加工零件64 2020-05-20 …
据统计,在某银行的一个营业窗口等候的人数及其相应的概率如下:排队人数题0人1人2人3人4人5人及5 2020-06-13 …
六2班数学测验中有2人不及格,是良等人数的六分之一,良等人数是优等人数的三分之一,优等生有几名 2020-06-22 …
我遇到一个数学题不会做,一次数学单元测试,五(2)班的同学都取得了C等以上的成绩(A为优秀,B为良 2020-07-18 …
红星小学举行科技制作比赛,获一.二.三等奖的人数分别占获奖总人数的6分之1.3分之1和2分之1,已知 2020-12-16 …