Question

帮忙解决一道数学题,急！！！

有n(n>=5)个人聚会。已知：（1）每个人至少同其中[n/2](取整数部分)个人互相认识；（2）对于其中任意[n/2](取整数部分)个人，或者其中有2人认识，或者余下的人中有2人相识。证明：这个人中必有3人两两相识。
补充：抱歉，写错了，n>5而不是n>=5.

Answer 1

这个题有问题，
我找到一个反例：
假设n=5，5个人组成一个环，每个人只和他相邻的两个人互相认识，
显然满足条件(1)和(2)，但是找不到3个人两两相识。

n>=6，以下用图论语言，将人看成顶点，两人互相认识看成两点之间存在一条边。
求证该图中存在三角形。
用反证法，假设图中不存在三角形，

当n为偶数时，n>=6,[n/2]=n/2>=3,n/2-1>=2
从n个点中任取一点P，由条件(1)知，P至少和n/2个点相连，
在与P相连的点中任取n/2个点，构成集合A，设除去点P和集合A剩下的(n/2-1)个点构成集合B，
由于不存在三角形，因此A中任意两点不相连，否则这两点和P构成三角形，
在A中任取一点，该点与P相连，与A中其他点不相连，而B共有(n/2-1)个点，为了满足条件(1)，该点必须与B中所有点相连。
对集合A来考虑条件(2)，显然A中任意两点不相连，剩下的n/2个点，每个点都和A中任意点相连，为避免形成三角形，剩下的点也无两点相连，这与条件(2)矛盾，
因此当n为偶数时，图中必存在三角形。

当n为奇数时，n>=7,[n/2]=(n-1)/2>=3,(n-1)/2-1>=2,
同样，任取一点P，由条件(1)知，P至少和(n-1)/2个点相连，
在与P相连的点中任取(n-1)/2个点，构成集合A，设剩下的(n-1)/2个点构成集合B，同理，A中任意两点不相连，
对集合A来考虑条件(2)，A中任意两点不相连，因此剩下的点P和集合B中，必有两点相连，
分两种情况讨论：
1、相连的两点其中一点为P，另一点Q在B中，
在A中任取一点，该点与P相连，与A中其他点不相连，且不能和Q相连，否则该点与P、Q形成三角形，而B除去点Q剩下(n-3)/2个点，为了满足条件(1)，该点必须与B中除去Q的所有其他点相连。
设B去掉点Q加上点P构成集合C，对集合C来考虑条件(2)，
首先，集合C内任意两点不相连，否则这两点与A中任意一点构成三角形，
其次，集合C外的其他点，即集合A以及点Q，显然集合A内任意两点不相连，且Q与A任意一点不相连，否则这两点与点P构成三角形，
因此条件(2)不满足，矛盾。
2、相连的两点Q、R都在B中
首先，若P与B中任意一点相连，则由刚才的讨论可得出矛盾，因此以下假设P与B中任意一点不相连，
以下证A中任意一点必与Q或R相连，且不能同时与Q和R相连，
若A中任意一点与Q和R均不相连，显然该点与A内任意其他点不相连，除去集合A和P、Q两点，剩下(n-3)/2个点，无法满足条件(1)，故A中任意一点必与Q或R相连，因为Q、R相连，因此该点不能同时与Q和R相连，否则构成三角形。
设B去掉点P和Q剩下的(n-1)/2-2=(n-5)/2个点构成集合D，
A中任意一点与P相连，与Q、R中仅有一点相连，为满足条件(1)，该点必与D中所有点均相连，
若点Q与D中任意一点相连，则点Q与A中任意一点不相连，否则构成三角形，此时Q只能和R以及D中点相连，最多能连1+(n-5)/2=(n-3)/2条边，无法满足条件(1)，
因此Q与D中任意一点不相连，同理R与D中任意一点不相连，
且P、Q不相连，P、R不相连，A中任意一点仅与P、Q中一点相连
考虑以Q为端点的边与已R为端点的边的和d(Q)+d(R)=1+1+(n-1)/2=(n+3)/2，
但由条件1可知，d(Q)>=(n-1)/2且d(R)>=(n-1)/2，所以d(Q)+d(R)>=n-1，
当n>=7时，n-1-(n+3)/2=(n-5)/2>0，因此d(Q)+d(R)>=n-1>(n+3)/2=d(Q)+d(R)，矛盾
因此当n为奇数时，图中必存在三角形。

综上所述，图中必存在三角形，得证。