$8$ 个人参加一次聚会。（1）如果其中任何 $5$ 个人中都有 $3$ 个人两两认识，求证：可以从中找出 $4$ 个人两两认识；（2）试问：如果其中任何 $6$ 个人中都有 $3$ 个人两两认识，那么，是否一定可以找出 $4$ 个人两两认识？
【难度】
【出处】
2006第5届CGMO试题
【标注】
【答案】
否
【解析】
（1）分情形讨论。 情形 $1$：如果存在 $3$ 个人两两互不认识，那么其余 $5$ 个人必然两两都认识。若不然，假如他们之中有 $2$ 人互不相识，则在他们与原来的 $3$ 个人一起构成的 $5$ 人组中就找不出 $3$ 个人两两认识，导致矛盾。所以，此时题中结论成立。 情形 $2$：在剩下的情形中，任何 $3$ 个人中，都有某 $2$ 个人互相认识。（I）如果 $8$ 个人中有 $1$ 个人 $A$ 至多认识 $3$ 个人，那么他至少不认识 $4$ 个人。显然，这 $4$ 个人中的任何 $2$ 人都彼此认识。若不然，这 $2$ 个人与 $A$ 一起构成的 $3$ 人组中就没有 $2$ 个人互相认识，导致矛盾。所以，此时题中结论成立。（II）如果存在 $1$ 个人 $A$ 至多认识 $5$ 个人，那么，这 $5$ 个人中有 $3$ 个人两两彼此认识，他们又都认识 $A$，所以，他们与 $A$ 一起即为所求的 $4$ 人。（III）只需再考虑每个人都恰好有 $4$ 个熟人，并且任何 $3$ 个人中都有 $2$ 个人相互认识的情形。 任取其中 $1$ 个人 $A$ 。假如 $A$ 的 $4$ 个熟人两两认识，那么，他们即为所求。否则，其中就有 $B$、$C$ 互不认识。此时，$A$ 有 $3$ 个不认识的人 $F$、$G$、$H$，而这 $3$ 个人中的任何 $2$ 个人都与 $A$ 构成 $3$ 人组，所以 $F$、$G$、$H$ 中的任何 $2$ 个人都相互认识。如果 $B$、$C$ 之一与 $F$、$G$、$H$ 中的每个人都彼此认识，那么此人与 $F$、$G$、$H$ 一起构成所求的4人组。否则，$B$、$C$ 分别不认识 $F$、$G$、$H$ 中的一个人。 易知 $B$ 和 $C$ 不可能不认识他们中的同一个人，否则，该人与 $B$、$C$ 所成的3人组中的任何2个人均互不认识，导致矛盾。这就表明 $B$ 和 $C$ 分别不认识 $F$、$G$、$H$ 中的两个不同的人，不妨设 $B$ 不认识 $F$，而 $C$ 不认识 $G$ 。现在把 $B$、$F$、$A$、$G$、$C$ 依次排在一个圆周上，于是任何两个相邻位置的人都互不认识。然而他们中的任何 $3$ 个人中都一定有在圆周上相邻的两个人，从而，他们之中找不到 $3$ 个人两两认识，导致矛盾。所以这种情况不可能存在。 综上所述，在一切可能的情况下，都能找出 $4$ 个人两两都彼此认识。（2）如果其中任何 $6$ 个人中都有 $3$ 个人两两彼此认识，则不一定可以找出 $4$ 个人两两彼此认识。例子：在正八边形中连出 $8$ 条最短的对角线。每个顶点代表一个人，有线段相连的顶点表示相应 $2$ 个人相互认识。不难验证，其中任何 $6$ 个人中都有 $3$ 个人两两彼此认识，但是却找不出 $4$ 个人两两彼此认识。
答案
解析
备注
