本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/articles/16151398.html

关于多人中3人相认识或4人相不认识研究报告

作者：张霆希

时间：2022.4.15

题目

求至少任意多少个人，必有3个人全都互相认识或者4个人全都互相不认识，不存在A认识B但B不认识A的情况

3个人全都互相认识

4个人全都互相不认识

连通块：假如A认识B，B认识C，则A，B，C在一个连通块里，A和C的关系不确定.

连通块的大小：连通块里的人数成为连通块的大小.

连通块的 $k$ 值：连通块互不认识的人数.

因为3个人不能同时认识，所以假如一个连通块大小为 $n$ ，最多且至少有 $n-1$ 个互相认识关系.

对于任意一个连通块，假设其大小为 $n$ ，它的 $k$ 值最少为 $\left\lceil\frac{n}{2}\right\rceil$ .

我们可以用黑白染色法来证明。

对于一个黑点，与其相邻的必定是白点。对于一个白点，与其相邻的一定是黑点。我们可以根据引理1来证明.

此时 $k$ 为黑点和白点中的较大值。

要使 $k$ 尽可能少，就要是黑白点的数量尽量接近，假设黑点数量大于等于白点数量，则黑点数量为 $\left\lceil\frac{n}{2}\right\rceil$ ，白点数量为 $\left\lfloor\frac{n}{2}\right\rfloor$ .

显然，当连通块构成一条链时，上面情况成立。

根据引理2，要使人数最多，而 $k$ 尽可能少，则每个连通块的大小一定为偶数.

综合定理1和定理2可以得出，连通块具有两个特点是最优的：

我们称符合上面特点的联通块为最优连通块.

那么一个最优连通块的 $k$ 则为 $\frac{n}{2}$ . （因为 $n$ 必然为偶数，所以 $\frac{n}{2}$ 必然为整数）

根据定理2可知，对于一个大小为 $n$ 的最优连通块，其状态唯一.

根据定理1，最优连通块必然满足条件1.

假设一个最优连通块大小为 $a$ ，一个最优连通块大小为 $b$ ，则他们的 $k$ 值之和为:

$\frac{a}{2}+\frac{b}{2}=\frac{a+b}2$

等价于一个**大小为 $a+b$ **的最优连通块。

也就是说，最优连通块的个数与最终结果无关。

根据定理4，我们可以假设这个图为一个单独的最优连通块（因为这是等价的）.

根据定理3，我们要求至少任意多少个人（假设为 $n$ ），可列出不等式：

$\frac n 2\geqslant 4$

$n\geqslant 8$

因此，至少为8个人。