求证10人中必有3人两两认识或4人两两不认识.

来源：学生作业帮助网 编辑：作业帮 时间：2024/11/06 05:15:12

求证10人中必有3人两两认识或4人两两不认识.
求证10人中必有3人两两认识或4人两两不认识.

求证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符合要求,命题成立.
综上所述,原命题成立.

求证10人中必有3人两两认识或4人两两不认识. 反证法证明任意6人中必有3人互相认识或不认识. 史上无人能解的数学题世界上的六人中,求证其中必有三人,他们之间互相认识或不认识 证明四人相识有10个人,其中任意3人中有2人相互认识.证明这10人中必有4人相互认识对于东海凤楚的回答：可以证明甲认识其他三人，也可以推出甲认识的这三人中两人相识。可是不能证明这 求证世界上任意六个人中,一定有三个人互相认识,或三个人互相不认识 证明：任何9人中总有3人互相认识,或4人互相不认识. 9个人见面～每3个人中必有两个相识～证明九个人中必有4个人彼此相识 试说明：在任意的6个人中必有3个人,他们或者相互认识,或者相互不认识. 有11个人,其中任何3人中有2人认识,证明在这11人中至少有一人认识其余10人中的5个人 一次集会随意邀请10人参加,证明；其中必有2人,他们在这10人中认识的人一样多 求证世界上六个人中,有三个人互相认识,否则就有三个人互相不认识! 集合数学难题一组人中每2个人或者彼此认识或彼此不认识,那么必须有多少人才能满足一定有3个人彼此都认识?4个人彼此都认识?N个人彼此都认识?,这个问题好像是一个未解数学题.有位朋友知 如何证明世界上6个人中任意3个认识或不认识 有关组合的由5个人组成一个公司,其中任意3人中总有2人彼此认识,总有2人彼此不认识.求证：此5人可以围桌而坐,使每人两旁都是认识的人. 任意6个人中,证明总有至少3个人认识或至少3个人不认识?只要符合其中一个条件 证明六个人中,总有三个人互相认识或互相不认识 证明任意的9个人中一定有3个人互相认识或者有4个人互相不认识.我现在学的离散数学中的题,要用到图论基础.思路估计是把人设为结点,而认识或不认识关系设为边... 九个人见面‘每三个人中必有两个相识～证明九个人中必有四个人彼此相识