Question

证明：在任何一个10人的小组中,或者有3人互相不认识,或者有4人互相不认识。

Answer 1

题有问题。应该是“有3人互相不认识，或者有4人互相认识”或者“有三人互相认识，或者有4人互相不认识”。
两个等价的，只需证第一个
首先，一个基本的引理是：6个人中必有三人互相认识或互相不认识
依据上面引理，考虑组中任意一个人A。如果A认识6个人的话，这6个人中要么有3个互相认识，要么有3个互相不认识。如果是后者，显然符合题意；如果有3个互相认识，这三人0加上A一共4个人互相认识，也合题。
如果A认识的人数不够6个，则不认识的人数不少于9-5=4个。这4人中若有两人不认识，此两人加上A三人间互相不认识，合题；若4人两两相识，也合题。
综上，总能找到3人互相不认识，或4人互相认识

比这个更宽的结论叫ramsey定理，是图论里比较有名的一个结论。