在协会上有九个人,其中任意三个人总有两个相互认识.求证:其中总有四个人,他们相互认识.

来源：学生作业帮编辑：神马作文网作业帮分类：数学作业时间：2024/11/20 16:09:19

证:用平面上无三点共线的九个点A1,A2,A3,……,A9表示9个人,9点间两两相连,现对这些线段染色,若两人相互认识,则把对应两点间的连线染成红色,否则染成蓝色,得到二色完全图k9,现只需证明必存在红色k4.
由题设知二色完全图k9中无蓝色三角形.
现任取一点,由抽屉原理知,此点与另八点所连的8条线段中,至少有4条同色.
⑴若由任意点出发的8条线段中有4条蓝色线段,不妨设A1出发的四条线段A1A2,A1A3,A1A4,A1A5为蓝色,由于不存在蓝三角,故A2,A3,A4 ,A5组成的完全图k4为红色.
⑵若由任意一点出发的八条线段中至多有三条蓝色线段,即其中至少有5条线段为红色.又因为k9中红色线段边数不可能为9×5/2,所以从此点出发的八条线段中至少有6条是红色.不妨设A1出发的6条线段A1A2,A1A3,A1A4,A1A5,A1A6,A1A7为红色,考察此6点在,其组成的二色完全图比存在同色三角形,又由于不存在蓝三角形,所以同色三角必为红三角形,所以必存在红色完全图k4.
综上所述,其中总有4人,他们相互认识.

在协会上有九个人,其中任意三个人总有两个相互认识.求证:其中总有四个人,他们相互认识. 求证世界上任意六个人中,一定有三个人互相认识,或三个人互相不认识问答题：有五十个人,其中有一个人说假话,这五十个人中任意两个人中总有一个人说真话,问说真话的有几人有100个人,其中至少有1个人说假话,这100个人里任意2个人总有1个说真话,问说真话的有多少人? 有一个团体会议,有n人参加,在其中任意m人中(n>m),至少有a个人认识其它b个人,问该团体中认识其它所有人的成员至少有有100个人,其中至少有1人说假话,这100人里任意2个人总有1个人说真话,问说真话的有多少人有100个人,其中至少有1人说假话,这100个人任意两个人总有1个说真话,说真话几个人,假话几个人?望快解有100个人,其中至少有1人说假话,这100个人任意两个人总有1个说真话,说真话几个人,假话几个人? 证明6个人中或者存在3个人相互认识,或者存在3个人相互不认识有11个人,其中任何3人中有2人认识,证明在这11人中至少有一人认识其余10人中的5个人有100个人,其中至少有一人说假话,这100个人中任意两个人中总有一个人说真话.问：说真话的有多少人?说假话的有多少人? 有三个人认识,某天他们各自乘火车外出,若火车有10节车厢,那么至少有2个人在同一车厢的概率是