图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中
来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/09/25 03:22:29
图论的证明题
证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识
题目取自《图论与袋鼠结构》的习题中
证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识
题目取自《图论与袋鼠结构》的习题中
(1).有某人认识的人少于5个,不认识的人至少有4个,如A不认识B,C,D,E.
如果B,C,D,E中有2人不认识,则他们与A,3个人互相不认识;
如果B,C,D,E都认识,则他们4人互相认识.
(2).每个人认识的人不少于5个.
首先,9个人认识的人数的总和一定是偶数,因为若A,B认识,这个关系A在记数是计了1次,B在计数时也计了1次.每个关系对总和的贡献都是2.如果每个人恰认识5人,则9个人认识的人数的总和等于9*5=45,矛盾.
所以,至少有1个人A认识6人.由熟知的结果,这6人中或有3人互相不认识,或有3人互相认识,这3人与A,4人互相认识.
这是图论中的拉姆赛问题,本题就是证明拉姆赛数R(3,4)=9.
6人中或有3人互相不认识,或有3人互相认识,是拉姆赛数R(3,3)=6.
如果B,C,D,E中有2人不认识,则他们与A,3个人互相不认识;
如果B,C,D,E都认识,则他们4人互相认识.
(2).每个人认识的人不少于5个.
首先,9个人认识的人数的总和一定是偶数,因为若A,B认识,这个关系A在记数是计了1次,B在计数时也计了1次.每个关系对总和的贡献都是2.如果每个人恰认识5人,则9个人认识的人数的总和等于9*5=45,矛盾.
所以,至少有1个人A认识6人.由熟知的结果,这6人中或有3人互相不认识,或有3人互相认识,这3人与A,4人互相认识.
这是图论中的拉姆赛问题,本题就是证明拉姆赛数R(3,4)=9.
6人中或有3人互相不认识,或有3人互相认识,是拉姆赛数R(3,3)=6.
图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中
证明:在任何一个10人的小组中,或者有3人互相不认识,或者有4人互相不认识.
证明:任意28个人中,至少有3个人的属相相同.
用反证法证明13个人中至少有两个人的生日在同一个月
有11个人,其中任何3人中有2人认识,证明在这11人中至少有一人认识其余10人中的5个人
求证世界上任意六个人中,一定有三个人互相认识,或三个人互相不认识
证明 400个人中至少有两个人生日相同
55个人参加一次考试,共有4道选择题,每题有3个选项.证明:必有3个人中有2个人的答案至少有3题相同.
证明6个人中或者存在3个人相互认识,或者存在3个人相互不认识
一道图论题:一个旅行团中任意4位中至少有一个旅客认识另外3人,证明任意4人中有1人他早就认识旅行团中其余的每个人
平面上有8条互相不平行的直线,证明:在所有的交角中,至少有一个角小于23度
4个人中,至少有2个人的生日同月的概率是________