发新话题
打印【有6个人次参与评价】

[数学] 奥数题可以难到这种程度-2007年IMO结局

浙江是全国出数学家最多的地方之一,但在imo方面,二十多年才出了第一个IMO国家队队员沈才立。这跟浙江的高中数学竞赛训练体制有关,浙江的数学竞赛训练主要是针对高中数学联赛,而非cmo和imo,所以浙江参加冬令营的的选手虽多(和上海差不多),但成绩相当差,和上海不能比,更不要说湖南和湖北了,至今没有拿过cmo第一名和陈省身杯。今年机会相当好,浙江前两个考的相当好,第三个只要考81分就可以了,结果浙江剩下的第三高分只有六十几分。
今年的第三题并不是很难,这题我就想了十分钟,这么多人没考好,我想主要是现在数学竞赛对图论不太重视有关。我想下半年的高中数学联赛不出意外,二试肯定会有组合题。.

TOP

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,矛盾。.

TOP

发新话题