证明:任何9人中总有3人互相认识,或4人互相不认识.
来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/10/10 03:22:36
证明:任何9人中总有3人互相认识,或4人互相不认识.
证明:
首先证明如下命题:
任何6人中总有3人互相认识,或3人互相不认识.
证明命题:
假设命题不成立.
在六人中选取一人出来,设为:A
则,在剩下5人中,A不能认识他们中超过2个人.
否则,如果A认识3个人,那么根据假设他们之间必然相互不认识.这与假设矛盾.
另一方面,他们中A不认识的不能超过2个人.
否则,如果三个人都不认识A,那么他们之间必然两两认识.
这与假设矛盾.
总共5人,A不认识和认识的和得小于等于4人,矛盾.
所以命题得证明.
再回到原来命题的证明.
假设命题成立.
在九人中选取一人,
剩下的8人中.
A不能认识他们中超过3个人.
理由如上.
另一方面:
他们中A不认识的不能超过5个人.
否则,如果有6人不认识A
根据上面命题,他们中有三人相互不认识,加上A则有四人相互不认识,矛盾.
所以8个人中,A至少认识3个,最多认识3个,只能认识
3个
所以对于每个人来说,都认识其余八人中的三人.
考虑,9个人组成一个图,认识关系为边.
则该图每个点的度为3
总度数为:9*3=27是奇数,因为总度数等于边数2倍.
所以矛盾!
所以原命题得证.
首先证明如下命题:
任何6人中总有3人互相认识,或3人互相不认识.
证明命题:
假设命题不成立.
在六人中选取一人出来,设为:A
则,在剩下5人中,A不能认识他们中超过2个人.
否则,如果A认识3个人,那么根据假设他们之间必然相互不认识.这与假设矛盾.
另一方面,他们中A不认识的不能超过2个人.
否则,如果三个人都不认识A,那么他们之间必然两两认识.
这与假设矛盾.
总共5人,A不认识和认识的和得小于等于4人,矛盾.
所以命题得证明.
再回到原来命题的证明.
假设命题成立.
在九人中选取一人,
剩下的8人中.
A不能认识他们中超过3个人.
理由如上.
另一方面:
他们中A不认识的不能超过5个人.
否则,如果有6人不认识A
根据上面命题,他们中有三人相互不认识,加上A则有四人相互不认识,矛盾.
所以8个人中,A至少认识3个,最多认识3个,只能认识
3个
所以对于每个人来说,都认识其余八人中的三人.
考虑,9个人组成一个图,认识关系为边.
则该图每个点的度为3
总度数为:9*3=27是奇数,因为总度数等于边数2倍.
所以矛盾!
所以原命题得证.
求证世界上任意六个人中,一定有三个人互相认识,或三个人互相不认识
图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中
证明:在任何一个10人的小组中,或者有3人互相不认识,或者有4人互相不认识.
两道六年级奥数问题第一道某班有60人,任意两人要么互相不认识,要么互相认识.证明,这60人中,必有两人认识的人数相同.第
有11个人,其中任何3人中有2人认识,证明在这11人中至少有一人认识其余10人中的5个人
1.一天,颐和园知春亭中有6位游客,请证明:他们之中必有三名互相认识或者互相不认识.
史上无人能解的数学题世界上的六人中,求证其中必有三人,他们之间互相认识或不认识
怎么证明任意三个人中就有两个是同性别的?任意五个人中有三个人识认的或有三个人不认识?
一道图论题:一个旅行团中任意4位中至少有一个旅客认识另外3人,证明任意4人中有1人他早就认识旅行团中其余的每个人
人与人之间关爱作文最好是不认识的人之间互相关心的,急
如何证明世界上6个人中任意3个认识或不认识
请问,地球上的任何物质都能在固体,液体,气体3者间互相转换吗?比如说,水,泥 或 有生命的物质,