设有 $n$ 人，任意两人在其他 $n-2$ 人中都至少有 $2016$ 位共同的朋友，朋友关系是相互的．求所有 $n$，使得在满足以上条件的任何情形下都存在 $5$ 人彼此是朋友．
【难度】
【出处】
2016年中国科学技术大学优秀中学生数学科学营数学试题
【标注】
【答案】
略
【解析】
显然 $n\geqslant 2018$．
当 $n\geqslant 4032$ 时，记这 $n$ 个人分别为 $1,2,\cdots,n$，把他们分为 $4$ 个小组\[\begin{split} P_1&=\{1,2,\cdots,1008\},\\
P_2&=\{1009,1010,\cdots,2016\},\\
P_3&=\{2017,2018,\cdots,3024\},\\
P_4&=\{3025,3026,\cdots,n\},\end{split}\]其中每个人不认识自己小组内的任何一个人，但认识自己小组外的所有人．这样不存在任何 $5$ 个人，他们彼此是朋友．
当 $n\leqslant 4031$ 时，考虑具有朋友关系的 $A,B$ 两人，$C$ 是他们共同的朋友，设 $A,B,C$ 的朋友组成集合分别为 $P(A),P(B),P(C)$，记 $P(AB)$ 为 $A,B$ 共同的朋友组成的集合，则由于\[{\rm Card}P(AB),{\rm Card}P(BC)\geqslant 2016,\]于是\[P(ABC)=P(AB)\cap P(BC)\]不是空集．设 $D\in P(ABC)$，考虑 $P(ABCD)$．若 $P(ABCD)$ 是空集，则 $P(ABC),P(BCD),P(CDA),P(DAB)$ 两两的交集为空集，从而\[{\rm Card}P(AB)\geqslant {\rm Card}P(ABC)+{\rm Card}P(ABD),\]进而\[\sum_{i,j\in\{A,B,C,D\},i\ne j}{\rm Card}P(ij)\geqslant 3\sum_{i,j,k\in\{A,B,C,D\},i\ne j,i\ne j,j\ne k}{\rm Card}P(ijk),\]简记为\[\sum_{i,j}{\rm Card}P(ij)\geqslant 3\sum_{i,j,k}{\rm Card}P(ijk),\]根据容斥原理，有\[n\geqslant {\rm Card}\bigcup_{i,j}P(ij)=\sum_{i,j}{\rm Card}P(ij)-2\sum_{i,j,k}{\rm Card}P(ijk)\geqslant \dfrac 13\sum_{i,j}{\rm Card}P(ij)=4032,\]矛盾．因此必然存在 $E\in P(ABCD)$，此时 $A,B,C,D,E$ 五人彼此是朋友．
综上所述，$n=2018,2019,\cdots,4031$．
当 $n\geqslant 4032$ 时，记这 $n$ 个人分别为 $1,2,\cdots,n$，把他们分为 $4$ 个小组\[\begin{split} P_1&=\{1,2,\cdots,1008\},\\
P_2&=\{1009,1010,\cdots,2016\},\\
P_3&=\{2017,2018,\cdots,3024\},\\
P_4&=\{3025,3026,\cdots,n\},\end{split}\]其中每个人不认识自己小组内的任何一个人，但认识自己小组外的所有人．这样不存在任何 $5$ 个人，他们彼此是朋友．
当 $n\leqslant 4031$ 时，考虑具有朋友关系的 $A,B$ 两人，$C$ 是他们共同的朋友，设 $A,B,C$ 的朋友组成集合分别为 $P(A),P(B),P(C)$，记 $P(AB)$ 为 $A,B$ 共同的朋友组成的集合，则由于\[{\rm Card}P(AB),{\rm Card}P(BC)\geqslant 2016,\]于是\[P(ABC)=P(AB)\cap P(BC)\]不是空集．设 $D\in P(ABC)$，考虑 $P(ABCD)$．若 $P(ABCD)$ 是空集，则 $P(ABC),P(BCD),P(CDA),P(DAB)$ 两两的交集为空集，从而\[{\rm Card}P(AB)\geqslant {\rm Card}P(ABC)+{\rm Card}P(ABD),\]进而\[\sum_{i,j\in\{A,B,C,D\},i\ne j}{\rm Card}P(ij)\geqslant 3\sum_{i,j,k\in\{A,B,C,D\},i\ne j,i\ne j,j\ne k}{\rm Card}P(ijk),\]简记为\[\sum_{i,j}{\rm Card}P(ij)\geqslant 3\sum_{i,j,k}{\rm Card}P(ijk),\]根据容斥原理，有\[n\geqslant {\rm Card}\bigcup_{i,j}P(ij)=\sum_{i,j}{\rm Card}P(ij)-2\sum_{i,j,k}{\rm Card}P(ijk)\geqslant \dfrac 13\sum_{i,j}{\rm Card}P(ij)=4032,\]矛盾．因此必然存在 $E\in P(ABCD)$，此时 $A,B,C,D,E$ 五人彼此是朋友．
综上所述，$n=2018,2019,\cdots,4031$．
答案
解析
备注
