2n 人中，每人至少与 n 人认识，证明：其中必有四人，围桌而坐时，左右都是认识的人

wilsony

谁能证明？

luyuanhong

题 2n（n≥2）人中，每人至少与 n 人认识，证明：其中必有四人，围桌而坐时，每个人左右都是认识的人。

证  如果 2n 人，每个人都与其他 2n-1 人认识，则本题结论显然成立。下面考虑其他的情形。

    如果不是每个人都与其他 2n-1 人认识，则至少可以找到两个互不认识的人，设这两人是 A 与 B 。

    根据已知条件，可知 A 至少与 n 人认识，显然这 n 人中不包括 A,B 。

    B 也至少与 n 人认识，显然这 n 人中也不包括 A,B 。

    A 认识的 n 人，与 B 认识的 n 人，加起来共有 2n 人，其中不包括 A,B 。

    而总人数 2n 人去掉 A,B 后只有 2n-2 人，可见 A 认识的 n 人，与 B 认识的 n 人，至少有两人重复。

    设在 A 认识的 n 人与 B 认识的 n 人中，重复的两个人是 C,D 。

    让 A,B,C,D 围桌而坐，A,B 两人面对面，C,D 两人坐在 A,B 左右两边，这样，每个人左右都是认识的人了。

wilsony

    多谢陆老师指教！