早教吧作业答案频道 -->数学-->
在协会上有九个人,其中任意三个人总有两个相互认识.求证:其中总有四个人,他们相互认识.
题目详情
在协会上有九个人,其中任意三个人总有两个相互认识.求证:其中总有四个人,他们相互认识.
▼优质解答
答案和解析
证:用平面上无三点共线的九个点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人,他们相互认识.
由题设知二色完全图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人,他们相互认识.
看了 在协会上有九个人,其中任意三...的网友还看了以下：
你觉得老师该是什么样儿?写下自己的看法答：我觉得老师该是这样的：有丰富的课外知识,有时候会给我们讲 2020-06-15 …
英语翻译很高兴会见你们.会议谈到的以下这款产品贵司想转给我们做.你们说单价太高了,那请给我们你们的 2020-06-17 …
一个个体工商户如果制假贩假的话，坑害的就不止是一个消费者了，他会对整个社会的诚信造成危机。这就告诉 2020-06-19 …
巴尔扎克说过：苦难是人生的老师。是它教会了我们坚强面对，教会我们勇往直前。也正是因为这些人生路上的 2020-06-29 …
英语翻译生命中总有一种力量,震撼着我们的心灵.总有一种感动,会让我们泪流满面.感动仅仅是一个人在一 2020-07-13 …
小李，小张，小朱三人参加等谜会，他们分别猜对了一条，二条，小东，小张，小朱三人参加灯他们各谜会，他 2020-07-23 …
跨入中学生活的门槛，我们要学会生活，进入角色。如果想让新集体接纳你，让新同学认可你，你就要学会掌握社 2020-11-03 …
帮忙改出语病一、在联欢会上,我们班表演了文艺节目和大合唱.二、我们开会通过并讨论了他的建议.三、我们 2020-12-23 …
英语翻译句子。1下周我会有个新书包2明天会有一次数学考试3后天是雨天4下个月我们城市会有一个花展5明 2020-12-24 …
没有太阳怎么会有我们这个美丽可爱的世界呢?换个说法使意思不变我们不会忘记他的恩情,换个说法没有太阳怎 2021-01-19 …