反证法证明任意6人中必有3人互相认识或不认识。

2024-11-28 16:25:59

推荐回答（1个）

回答1：

证明：设这6个人是A,B,C,D,E,F，按顺序标成6个点（可以标成6边形的样子）。若两人认识，则用游蔽实线将两点连起来，否则，用虚线连起来。
假设这6人中存在3人不相互认识，且不存在3人相互不认识，在关系图中，相当销嫌于：不存在实线三角形，也不存在虚线三角形。
因此：图中比存在实线，也必存在虚线。
由于在6边形中任取3个顶点作三角形，共有C(3,6)=20个三角形，而两个顶点的连线共有C(2,6)=15条。每条连线会出现在4个三角形中。
由于8条连线必能组成一个三角形，而实线和虚线的数目不能同时小于等于7条神斗州，矛盾。
因此，假设不真，则原命题成立。