题目

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

提问时间：2021-03-31

答案

证明,这个是说法是错的
题有问题.应该是“有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定理,是图论里比较有名的一个结论.