6 人聚会的拉姆齐结论
Have We Met Before?
题目详情
证明：任意 6 人的聚会中，要么存在 3 个人两两互相认识，要么存在 3 个人两两互不认识。
Prove that in any party of 6 people, there is either a set of 3 people who all knew each other beforehand, or 3 people none of whom knew each other beforehand.
解析
取其中任意一人 P，观察其余 5 人。
P 与这 5 人之间的关系只有两类：认识或不认识。由抽屉原理，P 至少认识其中 3 人，或至少不认识其中 3 人。
- 若 P 认识 A,B,C：若 A,B,C 中任意两人彼此认识，则与 P 组成 3 人互相认识；若 A,B,C 彼此都不认识，则 A,B,C 本身构成 3 人互不认识。
- 若 P 不认识 A,B,C：同理得到 3 人互不认识或 3 人互相认识。
因此结论成立（即 ）。
Original Explanation
Consider one person. Among the other 5, either at least 3 of them are known to this person, or at least 3 of them are not known. In either case, look at those 3. If any two of them knew each other, or did not know each other, you form a triangle of either “all acquainted” or “all strangers.” By the pigeonhole principle, you can show you always get a triangle of mutual acquaintance or mutual strangers.