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

Answer 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条,矛盾.
因此,假设不真,则原命题成立.