图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/07/04 00:34:23
图论的证明题
证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识
题目取自《图论与袋鼠结构》的习题中
证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识
题目取自《图论与袋鼠结构》的习题中
![图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中](/uploads/image/z/5331732-60-2.jpg?t=%E5%9B%BE%E8%AE%BA%E7%9A%84%E8%AF%81%E6%98%8E%E9%A2%98%E8%AF%81%E6%98%8E9%E4%B8%AA%E4%BA%BA%E4%B8%AD%E8%8B%A5%E9%9D%9E%E8%87%B3%E5%B0%91%E6%9C%894%E4%BA%BA%E4%BA%92%E7%9B%B8%E8%AE%A4%E8%AF%86%2C%E5%88%99%E8%87%B3%E5%B0%91%E6%9C%893%E4%B8%AA%E4%BA%BA%E4%BA%92%E7%9B%B8%E4%B8%8D%E8%AE%A4%E8%AF%86%E9%A2%98%E7%9B%AE%E5%8F%96%E8%87%AA%E3%80%8A%E5%9B%BE%E8%AE%BA%E4%B8%8E%E8%A2%8B%E9%BC%A0%E7%BB%93%E6%9E%84%E3%80%8B%E7%9A%84%E4%B9%A0%E9%A2%98%E4%B8%AD)
(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个人的生日同月的概率是________