六个人，两种关系
题面
聚会上有 个人。任意两人要么互相认识，要么互不认识，「认识」是相互的。证明：这六个人中总存在三个人两两认识，或者存在三个人两两互不认识。再证明：换成 个人时结论不成立。
- 「认识」是对称的：若甲认识乙，则乙也认识甲。
- 要找的是两种关系之一的三人组，而不是指定的那一种。
想一想
展开提示 1
挑一个人。从这个人出发有五条关系，而颜色只有两种——抽屉原理立刻给出三条同色。
展开提示 2
把六个人画成图、边染两种颜色，然后去找同色三角形。
解答
答案 的任意二染色都含同色三角形； 可以染成不含同色三角形，所以 。
推导
-
把聚会建成模型。
-
挑一个顶点。
-
分成两种情形。
-
处理另一种颜色。
-
举反例否定 。
-
给出结论。