证明:在任何10个人的小组中,或者有3个人互相不认识,或者有4人互相认识.
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/08/31 03:15:50
证明:在任何10个人的小组中,或者有3个人互相不认识,或者有4人互相认识.
例3 连接圆周上九个不同点的36条直线染成红色或蓝色,假定有九点中每三点所确定的三角形都至少含有一条红色边,证明存在4点,其中每两点的连线都是红色的.(第八届加拿大数学奥林匹克,1976年)
分析:这个问题等价于以下命题:在二染色完全图K9中,要么存在所有边被染为蓝色的完全图K3,要么存在所有边被染为红色的完全图K4.更直接地说,就是证明R(3,4)≤9.这又是一个典型的拉姆赛型问题.
因为从一点引出的8条直线被染成红蓝两色,故至少有四条直线同色.
ⅰ 若有一点(设为A)引出的蓝色直线大于等于4条,并设A向点A1、A2、A3、A4引出了蓝色直线.此时,若A1A2、A1A3、A1A3、A2A3、A2A4、A3A4中任一条为蓝色,那么K9中便存在蓝色完全图K3;若A1A2、A1A3、A1A3、A2A3、A2A4、A3A4中每一条都为红色,那么就形成了一个以点A1、A2、A3、A4为顶点的红色完全图K4.所以,这种情况下命题成立.
ⅱ 每一点至少连出5条红色直线.若每一点都只连出5条红色直线,那么这九个点连出的红色直线数就不是整数,故至少有一点连出了6条红色直线.设该点为B,并设点B向点B1、B2、B3、B4、B5、B6引出了红色直线.
在考虑从点B1引出的五条直线B1B2、B1B3、B1B4、B1B5、B1B6,则至少有三条同色,设为B1B2、B1B3、B1B4.如果这三条都是蓝色的,那么以B、B2、B3、B4为顶点的完全图K4所有边都为红色,命题成立;如果这三条都为红色,考虑△B2B3B4,若每条边都为蓝色,那么就存在蓝色完全图K3;若有一边为红色,设为B2B3,则以B、B2、B3、B4为顶点的完全图K4符合要求,命题成立.
综上所述,原命题成立.
分析:这个问题等价于以下命题:在二染色完全图K9中,要么存在所有边被染为蓝色的完全图K3,要么存在所有边被染为红色的完全图K4.更直接地说,就是证明R(3,4)≤9.这又是一个典型的拉姆赛型问题.
因为从一点引出的8条直线被染成红蓝两色,故至少有四条直线同色.
ⅰ 若有一点(设为A)引出的蓝色直线大于等于4条,并设A向点A1、A2、A3、A4引出了蓝色直线.此时,若A1A2、A1A3、A1A3、A2A3、A2A4、A3A4中任一条为蓝色,那么K9中便存在蓝色完全图K3;若A1A2、A1A3、A1A3、A2A3、A2A4、A3A4中每一条都为红色,那么就形成了一个以点A1、A2、A3、A4为顶点的红色完全图K4.所以,这种情况下命题成立.
ⅱ 每一点至少连出5条红色直线.若每一点都只连出5条红色直线,那么这九个点连出的红色直线数就不是整数,故至少有一点连出了6条红色直线.设该点为B,并设点B向点B1、B2、B3、B4、B5、B6引出了红色直线.
在考虑从点B1引出的五条直线B1B2、B1B3、B1B4、B1B5、B1B6,则至少有三条同色,设为B1B2、B1B3、B1B4.如果这三条都是蓝色的,那么以B、B2、B3、B4为顶点的完全图K4所有边都为红色,命题成立;如果这三条都为红色,考虑△B2B3B4,若每条边都为蓝色,那么就存在蓝色完全图K3;若有一边为红色,设为B2B3,则以B、B2、B3、B4为顶点的完全图K4符合要求,命题成立.
综上所述,原命题成立.
证明:在任何一个10人的小组中,或者有3人互相不认识,或者有4人互相不认识.
图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中
证明6个人中或者存在3个人相互认识,或者存在3个人相互不认识
求证世界上任意六个人中,一定有三个人互相认识,或三个人互相不认识
1.一天,颐和园知春亭中有6位游客,请证明:他们之中必有三名互相认识或者互相不认识.
比喻两个人互相眼神看的词语有什么
有11个人,其中任何3人中有2人认识,证明在这11人中至少有一人认识其余10人中的5个人
介绍两个人互相认识,应该说---- 有三个选择,1:This is Betty 2:I am Betty 3:He is
如何证明世界上6个人中任意3个认识或不认识
如何从眼神看出两个人互相有好感
史上无人能解的数学题世界上的六人中,求证其中必有三人,他们之间互相认识或不认识
写人与人互相关爱 最好一件事例就可以表现两个人在互相关爱,事例不要是让座或者什么老土的材料,新鲜一点,而且一定要是有是事