2楼xyq2100
(......)
发表于 2007-7-31 21:40
显示全部帖子
3.(俄罗斯)数学竞赛的一些参赛者是朋友.朋友关系是相互的.若一组参赛者中每两个都是朋友,称为一个团.(只含一个人的组也是团).团中的人数称为团的规模.已知某次竞赛中最大团的规模为偶数,证明,可以安排在两间考室进行考试,使得一间所含的最大团的规模等于另一间所含的最大团的规模。
思路是差不多的,策略是图论中的调整法。
解答:我们记r(A)= A中最大团的规模.设全体参赛者为G,最大团的规模=2k,我们选取一个最大团C,将C分为相等的两部分A和B,将G中不属于C的成员放入B中。
如果r(A)<r(B)-1,我们就从B中移动一个属于C的成员A,一直到第一次出现r(A)>= r(B)-1。如果r(A)=r(B),命题得证。
如果r(A)=r(B)-1=p,设B中属于C的成员为D,如果B中某个p+1团X不包含D中所有的成员,那么将D中不属于X中的成员移至A中,此时r(A)=p+1=r(B),命题得证。
此时B中任意一个p+1团X都包含D中所有的成员,记B中属于某个p+1团的所有元素为Y,B其中的一个p+1团为X,由于D的元素个数<=k<p+1,因此我们可取X中不属于D的任意一个成员z,我们将Y-X+z移入A中,此时r(B)=p,如果此时r(A)>p,设其中一个最大的团为U,由于A中的成员与D都认识,r(U+D)>r(C)=2k,矛盾。.