IBM Ponder This #011 · 1999 年 3 月

如果一个人认识另一个人，则这种认识关系是双向的。这里的 clique 指四个人组成的集合，且其中任意两人都互相认识。

A 问

舞厅中有 $100$ 人，每个人至少认识其中另外 $67$ 人。

证明一定存在一个四人 clique。

B 问

舞厅中的 Joe 和 Grace 互相认识。

是否一定存在一个同时包含 Joe 和 Grace 的四人 clique？

C 问

实际上舞厅中有 $101$ 人，每个人仍至少认识另外 $67$ 人。

A 问的结论是否仍然成立？

解答

认真尝试后再打开

题解

待补充。