haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

20012002年国内外数学竞赛题选解二

发布时间:2013-12-22 14:41:46  

中等数学

2001--2002年国内外数学竞赛题选解(二)

0l

李建泉

尺津44J范太学数学科学学院.30f]074)

张茗

娄姗姗

(中等数学杂志编辑部.300020)

(天津市实骑中学.300074)

二、组合部分

1.往?次国际会议上.有四种官方语言任意两名会议代表可以用这四种语言之一进行I寸论证明:至少有60%的会议代表能讲同一种语言

(2{)(】2.罗马尼亚为IMO和巴尔千地区数学奥林匹克选拔考试供题(第二轮))

证明:假设这四种语言分别为l,2,3,4.

(1)若存在一名会议代表只会一种语言.则显然其他代表均会这种语言.

(2)每名会议代表至少会两种语言.且只讲两种语占的代表中没有公共语言.因此,对称地将会i义代丧分成如下的8类:

(】.2),(J,3),f2,3).(J,2.3).(J,2.4),(1,3,4),(2,3.4),(I,2.3,4)

如果能讲语占1,2.3的会议代表少于00%,用x。表示会讲语言i.,,…的会议代表的数目.则有

“+”+“,+m+m+。。c寻∑~,

+X

+X

+rⅥ

+Ⅳ

3—5

X+X+z+X

H+rH+』m

3亨

v∥∑m

以_匕二式相加得

2∑~+m+r.。<{∑~,

l,

‘’J+

即11∑%+Ⅶ3+%N<o.

矛盾

(3)每名会议代表至少会两种语言,只讲两种语言的代表中有一种语言是公共的类似地,将会议代表分成如F的8类:

(1,2),(1.3),“,4).(1,2.3).(J,2.4).(1.3,4),(2,3,4),(1.2,3.4).

若结论j;成立,则有

“¨3+%+%j+№+m+‰Ⅵ<{∑~,

“+“J+1(12。+JH+ⅦM<{、-.d、~.

万 

方数据%¨1]+铀+z“+x12-‘53姜H,‰岫。蝎。+x。蝎小吾∑小.

将第一个不等式乘2再与其他采每头相加,得

3(z12+J13+≈14)+4(zl∞+xlM+J1H)4-

3x2_+5zI删<3>:%,

l+』

zI∞4-zl“+x1N+2#1删<0.

2设A是集合{1,2,3,….16}的一个k元子集,(I)汪明:t≤5;

(2)求集合A的元索之和的最大值和最小值(2002,保加利亚冬季数学竞赛)

证明:(1)因为A有2‘个子集(包括空集),且任若k≥7,则2‘。1>16k,不可能.

若k=6.考虑A的一、二、三、四元子集,共有

若l∈A,则最大的和是16+14+12+9=51(其若2∈A,则最大的和是16+15+12+9=52,最若J亡A,2岳A,则在[3.57J中至多有55个和,

故t《5

解:(2)若,i-}n,.n:.…,a。{元素的和小于16,即矛盾

且A的任意两个子集的元素之和互不相等.而对于集合:1,2.3.-...L6.的包舍集合A的任意☆+I觅了-集B.则存在B的两个子集.它们的元素之和相等.

意两个子集的元素之和互不相等,所以A的元素之

和至少有2‘一1个

q+《+瑶+《=56个不同的和.且最小的和是1,鼹大的和是j6十15十14+12=57(其中16+13=J5+14,故这4个数不能同在A中).

中16=15+1,故这3个数不能同在A中;14=13+1,故这3个数不能同在A中;12=11+l。故这3个数不能同在A中;16+10=14+12,故这4个数不能同在A中),最多有5t个不同的和,矛盾.

多有51个不同的和,矛盾.

矛盾.

则集台{n.,n:,…,毗,16}中无元素的和相等的子

2003年第3期

集,与A的定义矛盾A=fI.2.4.91满址条件.其元素之和16足最小的.

若16∈A.则15+14+13+11+8=61

若16EA,15钲A.则16+14+13+12+8=63;若15EA.14年4,则16+15+13+II+7=62.

设{14,15.16cA,则13∈A.若12譬A,则16+15+14+11+8=64

若12∈A.由于11+16=12+15.10+16=12+

14.披设9∈A,因此.集合A={9.12.14,15.16.满足条件,其元索之和66是最大的.

3.已知平面直角坐标系加忆O为原点.A为整

点,叭的长度是一个奇索数的整数次幂.证明:以

nA为直径的圆周jj的整点中至少有一半满足它们任意两点之问的距离是整数

(2002,保加利亚春季数学竞赛)

证明:设OA=P”,P是大于2的素数,n是一个正整数.令A(,.y).且满足z2+y:=P“.则z是奇数.y是偶数或z是偶数,Y是奇数不妨考虑第一种情况

如图1.过n4的中

点(专,专)且与Ox平

行的直径设为MN.由于r是偶数,所以M、N的纵坐标为整数.易知M、

,v的横坐标』号£也为

整数.令MN=P4=d.在^州的同侧的圆周七取两个整点P、Q,其在MN上的垂足分别为P.、口.,则

MP。?NP。=孵.

由于MP。+NP.=矿,令(MP..NP。)=P4.则存在整数z、m,且(f,m)=1,使得MP.=矿f2,NP,=

矿m2于是胤P2=MP。?删,即

MP=f厂i,ⅣP=m、厂面.

同理,得邶l=p6:2,^Ql=pbt2.且岬=: ̄/一d.^Q=t ̄/矿d.

由托勒密(Plolemy)定理,得

—叼‘d+MP‘^Q=MQ‘PN

从而.JpD=(w—It) ̄/P”6若点P、口在MN的异侧,有

册=(,w+¨ ̄/,~.

因此.即是整数当且仅当o、b的奇偶性相同

万 

方数据而由假设,在圆周上的整点中至少有一半满足a、6是奇偶相同的故结论成立

4设正整数n≥3,(n.,n2,….n。)是任意n元不同的实数,且其和是正数.若它的一个排列(6-,

b一一,6。)满足对于任意的☆=1.2,…,n,均有6,+

b.+…+b。>0.则这个排列称为好的.求好的排列至少有多少个?

(2002,保加利亚国家数学奥林匹克地区级竞

赛)

解:设这n个数按顺时针放在正n边形的n个顶点j二.取s,使得q+以+,+…+a…是虽小的,其中下标取模n的余数,且假设,足最大的.于是.对

于tl≤,,则口…+…+Ⅱ…《0;否则,n。+以+l+…+Ⅱ…I<q+口川+…+吼…与和是最小的.

矛盾.于是,从a…+,开始,得到一个好的排列,即若某个和以…l十¨?+d…+★≤0,则n.+吼+I+…+Ⅱ…+‘≤n,+“,,I+…+Ⅱ…,-3和的最小及,的最大性矛盾

周此,对于n!个排列,jEn边形的顶点【每一种放法.按顺时针对应着n个排列,这n个排列中至少有一个是好的.所以至少有(n一1)!个好的排

列.

若i=1,2,….n—I时.仉<0.n.>0.则好的排(n一1)!个好的排列

所以,好的排列至少有(n一1)!个

5考虑一条由无穷多个正方形连成的纸带.有(i)若相邻的两个正方形,如第n一1个和第n个(ii)如果n≥3,且第n个正方形中有不少于两(1)证明:如上的操作是有限的:

(2)假设在前n个正方形的每一个中各有…枚(第19属伊朗数学奥林匹克(第一轮))

、证明:(1)由于硬币是有限的.则第一种操作的列只能从‰开始.其他一一1个数进行全排列.共有螳正方形里放着一些硬币.每次可以选择以下两种操作之一.

正方形里有硬币,则从这两个正方形的每一个中各取一枚.并将其中一枚硬币放人第n+J个正方形中;

枚硬币.则从第n个正方形中取出两枚硬币,放在第n+1个正方形中一枚.第n一2个正方形中一枚.

硬币,证明:无论怎样操作,在第n+1个正方形之后没有硬币出现.

次数是有限的没q为第i个正方形中硬币的数目.

32

s=>?/a,.经过一次第二种操作后s的值下降至膏

s一1.由于5是非负的.则第二种操作的数目也是有限的,所以操作是有限的.

(2)i殳斐波那契(Fiborl_aeci)数定义如F:

^=l√;=1√:=^,,+五2【n1>3).

易知∑,=,,+j—l?2t

设T=\:n。f,则经过每种操作之后,r的值不_

困开始时r的值为』+^+..+上=上.:一J,而第n+1个正方形之后若有硬币,则r的值~定大于等于‘+。.矛盾,所以,在第n+】个正方形之后没有硬币出现.

6.一个大学生在去年暑假用丁37天学习高等数学,并遵循如下规则:

(订每天至少学I小时;

(ii)每天按整/J、tl,j"学,且最多学12小时;

(iii)全部学习时间不超过60小时.

证明:此期阃存在洼续的若于天,该生学习时间的总和为13小时

(第19届希腊数学奥林匹克)

证明:设该生在第i天学了皿小时,则前i天学习的时间总和为A,=n。+n:+…+q,其中l≤Ⅱ。≤12.i=I.2,…,37.由题意可得

1≤41<如<…<A"《60,

J4≤』?+J3<A24-13<…<4”+】3≤73.

74个整数在1至73中,一定存在j、},使得a.=A‘+13.即A{一A^=13.

7.设平面上n(n≥4)个点A。,A:,…,A。,且任意三点不共线.每点至少与3个点之间有连线段.证明:在这n个点中存在不同的2女个点置.卫,…,置。(D1).使得置与x…之间有连线段,置t与x,之间有连线段、其中i≤1≤2,4一1.

(第19届巴尔干地区数学奥林匹克)

证明:设P=置如…置是最长的序列,其中置与五+.之间有连线段,i=I,2.….s一1.且置∈fA.,A2.….A。jE.x?≠x?,i≠i.

甘j于X,至少与3个点之间有连线段。设不同于x,的两个点为y和z.由于P是最长的,所以y、z万 方数据中等数学纛蠢薹田田。。:’竺至罢三墨笔篓璺_-列).那么,这两行(列)中任—广■]●广11意两个相邻格有着相同的颜?Ju一!竺警昱言董冀嚣要EIIZEItEIZ黑自格数日之差易见,第∈{墨,丘.….膏,{.设r=置,z=置.i(j.则c=

竺竺!竺!塑——————————!!一

数,则每个人得到—a,r+aj个问g;如果它足奇数.则

他们保留他们的问题.若所得问题数日仍不仝相同.则继续分配问用下断给定的值。若f次分配后能番使学生得手II的问题的数日全相同?

(I)n=8,N=80;

(2)11=10.Ⅳ=f00

(第53届门俄罗斯数学奥林肌电(决赛D类))解:将原命题改写为如F命题:

有n个非负整数之和为~.每一步选择任意两个具有相同奇偶性的数n-N6.均用!生芸』替换原来‘的。和6问若干步后是否有可能使所有的数均相

同?

(1)证明R=8,_|v=踟时答案是肯定的.假定数目的总和是0(因为我们町以将每个均

减去10)

使用L述步骤.我们验证能使昕有数目为。如果若干步以后不是所有数目为0,那么选择某一偶数n满足InI最大.因为这8个数之和为0,所以存

在偶数6将数n和6都用掣翟来替换.如果n≠6.

那么这步之后偶数的绝对值的最大值减小.

同洋的步骤也可用于奇数,重复这个过程可使所肓数目为0.

若当上述步骤不能减小绝对值的最大值时.一定彳1”,个奇数郁等J—n,8一m个偶数郜等于口I()<

Ⅲ<8)则钉

Ⅲ+(8-m)p=0.即m(p一口)=即

Iq为a一卢足奇数,r足m能被8整除,与0<

珊<8矛盾.

(2)答案是否定的.

例如:nl…‘:钆=11,口9=口Io=6.

10.~支球队参加曲棍球联赛,每支球队与其他球队只比赛一场,已知任意3支球队中不是每两支球趴之间均为平局.求平局场数的最大值

(第53届白俄罗斯数学奥林匹克(决赛c类))解:设d。为第i支球队平局的场数,设^=maxd.不失一般性,设d。=k,且第^T支球队与第i(1≤i≤^)支球队打平.

由已知条件.第i支球队与第』支球队(1≤i,』≤^)之间不能打平.于是,第女+1.?,,v一1支球队均蛀多打平^场.因此,平局的场数不超过k(Ⅳ一^).故平局场数的最大值为

万 

方数据吖:m““/v一∽

J≤』≤Y

fm2.当Ⅳ=2m,

2lm(m+1),当,v:2。+1

F面的例于表明M足可以达到的

tt第1,第2,…,第m点球队‘j第m+1.….第~支球队打乎.第p支球队赢第i支球队(1≤i‘P≤m),第q支球队赢第J支球队(m+l≤』‘q≤Ⅳ).满足平局场数为M,且满足条件.

1l有n支球队参加足球联赛,每支球队与其他球队只比赛一场,规定胜一场得3分,平一场得1分,负一场得0分.联赛结束后,有一些球队可能会被取消比赛资格.因此他们的比赛结果也会被取消

剩卜的球队将重新计算成绩,积分多的球队将会成为这次联赛的冠军(如果只有一支球队没被取消比赛资格,则他就是冠军).

设,(r)(i=1,2,….n)是在这次联赛r中使得第i支球队获得冠军,而被取消比赛资格的球队数目的最小值,又设,(,)=』(T)+石(,)+…+(第53届白俄罗斯数学奥林匹克(B类))解:因为f(r)≤n一1(i=1.2,….n),所以,(T)≤n(n一1).另外,在联赛R中,所有比赛都是平局.则第i支球队要得冠军,必须取消其他n一1支球队的比赛资格.所以f(R)=n一1

r是.

F(n)=Ⅱ(n一¨

用此,,(r)的最大值为,t(”I)

F面证明’’(r)的最小值为n

对j.联赛r.:第i支球队赢第i+1盘球队(i=1.2,-一,n一1),第n支球队赢第1支球队,其他球队如果在联赛r中没有一支球队比其他球队积如果在联赛r中有一支球队比其他球队积分若F(T)=n一1,则f(T)=1(i=1,2,…,n一上(T)对于n≥5.求F(T)的最大值和最小值.

之间的比赛均为平局.显然,取消第i一1支球队就能使第i支球队获得冠军(i=2,3.….n),取消第n支球队就能使第1支球队获得冠军,则f(五)=1,

于是F(T.)=n.

分多,则-,=(T)≥1(i=1,2,…,n),因此,(T)≥n;

多,不妨设为第n支球队比其他球队积分多.于是^(T)=0,上(r)≥I(i=1,2,…,n一1).所以,(r)

≥n—1.

1).上(T)=0设第i支球队获得冠军,被取消资格的是第口.支球队,则当i≠,时,嘶≠q.于是.第嘎

支球队一定输给r第n支球队(若nl≠n)所以第n支球队至少赢_rn一2场比赛.从而泼队得到氟≥3(n一2)分,且第i支球队(i=1.2,…,n—1)得到t≥k.一2分于是在联赛r中.所有球队得分之和为

∑^。=∑☆.+女。

≥>?(女。一2)+女。=nk。一2(n一1)

另一方面,奎t≤3.掣,所以,

≥3(n一2)n一2(n一1)=3n2—8n+2.

3,丛车型≥3n2—8n+2.

该不等式当n≥5时不成立.矛盾.因此,,(r)的最小值为n.也12个人围着桌子坐成一圈,有多少种握手方

法,使得6对握手的人胳膊不交叉?

(2001,英国数学奥林匹克(第一轮))

解:由题意,握手只在桌面上发生,而不会在其他人的背后.

设M表示2p个人围圆桌坐成一圈而无胳膊交叉握手的方法总数,且每人只握一次手.将每个人

看作一点,不失一般性将其中一人——亚瑟所在点

记作A.由于握手戚对发生,故在亚瑟及与他握手的人两侧的人数必为0或偶数.

i絮:巷鞲一@若有4个人,亚瑟可以和他

B4

dl<

)c

相邻的人(如图中

或)握\≮!∥

D手,但不能与对面的C握手,否则会发生交叉.故M=2.

若有6个人,亚瑟可以和他相邻的人(如图5中B或,)握手,余下的4人有肚种方法握4

手.亚瑟也可以和对面的D握手,在AD的两侧都有2个人,BC和Fig均有m种握手方法.故飓=2Ⅳ2+朋=5.

通过这种方法逐步求出%?

当有8个人时,亚瑟可与邻座(如图6中的B或圩)握手.余叭够即黟

下在~侧的6人有虬种握手方

围6

万 

方数据中等数学

式.亚瑟也可与D或F握手,则在一侧的2个人有jv,种握手方式.男一侧的4个人有肌种握手方式故儿=2儿+2NI×以=14

类似可得

肌=2N,+2N!×Nt+鹏=42.

N6=2Ns+2N4xN【+2N3

N2=132

所以,此题解为132

注:数列1,2.5.14,42.132,-??是著名的Catalan数.若定义No=1,则此数列通项为

^一1

Nk=>ItN,x矗

Nh,11.

13.在~次数学竞赛中,(i)竞赛题的数目为n(n≥4);(∽每道题恰由4人懈出;

(iii)对于任意两道题.恰有1人解出这两题若参赛人数大于等于4n,求n的晟小值.使得总存在一个人解出全部竞赛题.

(第15届韩国数学奥林匹克)

解:设n≥14,将每道题表示为一个矩形,其4个顶点分别表示4名解出此题的参赛者设P为任一问题.

每个不同于P的题目和P有一个公共顶点,因为n≥14,由抽屉原则知,有P的~个顶点记作S至少是4个(不同于P)矩形的顶点.

假设存在矩形P与P不在S共点,则至少有5个矩形以点S为顶点.且均和P只有一个公共顶点由抽屉原则.P的一个顶点S7至少是2个以S为顶点的矩形的顶点

若S≠S’。则有不少于2个矩形共点于P的S点和P的s’点,与条件(iii)矛盾.

敞S=S’.即所有矩形共点于S.

表1是n=13时,无人解出所有题目的一个例子.将竞赛题编号为】,2,…,13.将参赛者编号为1.者均没解出题目,第1行表示竞赛题的编号,第i列(1≤i≤13)表示解出第i道题的4名参赛者的编号.

衰1

竞赛厢编号

『1

12

13

——

44解出竞赛题的

115

67——

参赛学生峙码

一—9J210

89

——

10

13

12

13

】l

对于4≤n≤12,则可以通过去掉若干列(问题)注:题中条件n≥4可替换为n≥3但若n=2,

2,…在表1中,除1号至13号参赛者外的所有参赛

得到类似的例子.故所求最小值为14.

则最小值为2

足朋友要么是敌人一天.首领要求每位居民(包括

竺!竺!塑一——一——

14.岛f:居住着n个本地人,他们中每两人要么

:【墼掣]=【等]

种右头

注:参考第10题.

他自己)按以F原则自己做一条石头项链:每两个朋友问,他们的项链上至少有?块相同的石头;每两个

敌人间,他们的项链上的石头均不相同(一条项链上

可咀“无石头”).证明:要完成首领的命令需I筹1种不同的石头,并且当石头种数少于l等l时,此命令可

能无法实现(其中,[z】表示不超过z的最大整数)

(2002,克罗地亚国家数学竞赛)证明:用数学归纳法

当n=J和n=2时,显然居民可按规定做项链假设n=☆时结论成立,要证n=k+2时结论也成立.若每两位居民都是敌人,将不需要石头.现假设在居民中至少有两人是朋友,记作A和B由假

设知另外t个人至多用【等】种不同的石头做项

链.围为A与B是朋友.所以他们在制做项链时可以共同使用一种新石头

下面考虑女.在居民中的某人C,有以下3种可

能:

(1)c与A、B均是敌人;(2)c与A、B均是朋友;

(3)C是一人的朋友,是另一人的敌人.

在(1)中,不需要一种新石头;在(2)中,他们每人在项链上选一种新石头;在(3)中,仅c和他的朋友需选一种新石头.每种情况.他们都至多要用一种

新石头.综合起来,他们至多需要f等1+l+^种石

头(A和B需一种.余下k人中的每个人需一种).且

[等+…】=【粤掣】.

r一21

所以,I鲁1种石头满足条件.

F面证明.石头种数是不可减少的

若n是偶数.设n=2m,将居民分作相等的两组,使得任何同组的两人是敌人,任何不同组的两人

是朋友他们共需m2=专=【寺』种石头(因为有

m2对朋友,且在三个居民中至少有两个是敌人.所以这三人没有同一种石头).

若n=2m+J.将所有人分作m、m+1两组.如前面,任何同组的两人是敌人,任何不同组的两人是胴友此时,他们需要

m(m川=—4n2了+一4m=【缱±掣j

万 

方数据15.对于坐标平面上的格点盖,若线段Ox上不含其他格点,则称点X从原点0可见.证明:对任意

正整数n.存在面积为n2的正方形4肋.使得在此

正方形内部无从原点可见的格点

(2002,中国台湾数学奥林匹克)

证明:注意到格点(z,Y)从原点可见当且仅当x、Y互索.由此.闷题转化为求一个正方形.4BCD,使得其内部的每一格点(x,Y)满足。与Y不互素.没

J忡P…是一列不同的质数.在n×R的矩阵村中.

第l行的元素为前n个质数,第2行的元素为随后的n个质数,依此下去,设帆为M中第i行元素的乘积,M是M中第j列元素的乘积.则m。.m:,….

m.两两互素,M,,帆,…,帆两两互紊.下面,考虑

同余式

zE一1(roodml),

*;一2(rr州m2),

z§一n(nsxtm。).

由孙子定理,在roodm、m:…m。下有惟一鳃n类似地,同余式

Y2—1(modM,).

Y§一2(rood帆),Y;一n(rood孵).

在Ⅱ耐Ml鸲…帆=mlm2一m。下也有惟一解b.在以(Ⅱ.b)和(Ⅱ+n,b+n)为相对顶点的正方(Ⅱ+r,b+。).其中o(r<n,0<s(n.

∽r(mod只要证明这样的点从原点不可见.事实上,因为

mr),6三一5(roodM),所以,矩阵肘的

16.已知正壤数m、n,m《2

001,n<2

002,有

OOl×2002个不同的实数.将这些效放入2

OOl×

002的矩形棋盘(棋盘有2001行.2002列),使得每

(2002,越南数学奥林匹克)解:用P、口分别替换2

001、2

002(m《P,n≤

形中.其内部的格点满足

第r行s列的质数可以整除Ⅱ+r、6+j.由于n+r和b+s不互素.故格点(n+r,b+s)从原点不可见.

22

个格内有一个数.每个数都放在一个格内.当格内的数小于其所在列的至少m个数,也小于其所在行的至少n个数时,将这样的数所在的格称为“坏格”.对每种放法,记s为“坏格”的数目求s的最小值

—一——一——一——一———————————————————~

36

中等数学

q),将问题加强为对P+口进行归纳,证明

s≥(P—m)(口一n)

最小值为252;

硅然,当P+q=2,3.4时.不等式①成立

(2)满足善甚。2252的有胜一负的比赛可发生?

似没p+口=☆时,小等式①成立

当P+q=‘+I时,考虑(,’.q)一棋盘若仇=P或/7=q,不等式①品然成证.h所号虑m<PⅡn<q的情况如粜格内数字小r其所在行(或列)的至少n个数(或m个数),那么,将棋盘f.这样的格叫做坏行格(或坏列格)

往(P,目)一棋赶内,如果每个坏列格也是坏行格,且每个坏行格也是坏列格,那么易得

s=(P—m)(口一n)

因此不等式①成立

假设在(P,g)一棋盘内存在格仅是坏行格或坏列格设n是写在这类格中最小的数,不妨没n是坏行格.那么,位于n所在列的所有(p—m)个坏列格中的数比n小,因此一定是棋盘内的坏格.去掉n所在列,则(p.口一】)一棋盘的格是坏格,在先前假设的(p,g)一棋盘中也是坏格.因为P+g一1=^.由归纳假设知,在(P.q—1)一棋盘中坏格数不少于(p—m)(q一1一n).因此.在(p.q)一棋盘中坏格数

不少于

(P—m)(q一1一n)+(P—m)=(P—m)(q—H).由此.不等式①成立

现在(P,q)一棋盘中给出一种放法.使得坏格数等于(p—m)(口一n):将,“q个数按递增顺序从乍向打依次放人格内

这样.一。。=(p—m)(q叫).敞所求最小位为(2(】1)1一Ⅲ)(2f11)2Ⅷ)

17.14人进行?种H本棋循环赛,每个人都’4另外13人对弈,在比赛中无乎局求“三联角”的蛀大值(这里,“三联角”指三个人之间进行的比赛,每人均一胜一负).

(2002,日率数学奥林匹克(第一轮))

解:将这14个人分别用^.,A:.…,A。表示,没d.胜r嵋局.在任酋二:人中(即从】4人中选出3人

为?组),抒尤“二联角”.则啶有+人胜r”外两

14

人.所以不构成“三联角”的三人组的数目为>:仨.口‘

(这里.定义a=程=0).则“鼍联角”数为c毛一

14

¨

∑q,即求∑q的最小值.

已知\:叱=味=91下面证明:

14

(1)整数札≥o,且满足∑机=91则∑(之的

万 

方数据首先,证H爿(1).由丁_对每个t仅自有限种可能

值?故≥C:。的最小值存在?设仃往1≤,、,≤14使得

』。一z.≥2定义

r』,一1

(^=i).

,。={■+I(t=J).

。≈

(^≠i、J)

则n≥o,∑儿=91.且

善叠。一善《。2气+气一仨。一,一气?t

=掣+玉掣一盟挚型一

(』,+1)J,

——r一

=x。一x,一1>0.

故善气不是最小值?因此?使得苫嚷达到最

小值的机应满足:对所有l≤i、,≤14.h一一f≤I.{xt.02,…,x¨}

=i6。6,6,6,6,6,6.7,7,7,7,7.7,7f

从而.∑E。的最小值是碟x7+仁x

7=251,

卜曲m州i2).

献{lf;蚪的肚一次情M如丧!

裹2

’^也山山^^A,山山^loAI^¨^,A¨

A.,o

o口o

o●●●

A2●×o

ooo

o●?●●●?

A1●?x口oooo●?●●??

AJ???x

ooooo??

??

.45????×oooooo

??‘

^6???●?x

ooo??

A,??????_oooooo●

A3o??????x

ooooo

Aaoo???●??x?oooo

A10ooo?●●●?●xoooo

A11o

oo

o●●●?●●

ooo

A12

ooooo●●??●●-oo

Al,o

ooo??????x。

.{…o

oo

o。o????

??x

显然,

一竺!竺!塑——一————一

这里,在(i,J)表中,“。、”表示A,胜A,,“?”表

R“内,

承A,债A.,“×”表可;在A,和A,中没进行比赛.

所以,“,联角”个数的蛀人值对

(:j一252=112

(ii)对f纵坐标夫于4和C的菜点M.若其横

毕标小fD的横啦标.则M在日。内;分则,M在R。内

(iii)对j?菜点的纵坐标在A干¨c之间,则此点

存R。内

培已知在xr^半阿1.的2002个点组成的点集

记补。5,n一小任龃网点所连直线均1:’j书标轴平行埘}:s?f,曲个小目点P、Q.考虑以,JQ为埘角线,接边分别平行r坐标轴的镇形.峨。表HiS在此矩形内(水含P、O)的点的个数

当命题“S中的点无论在坐标f面上如何分布,在S中至少1竿在一对点P.O,满足阱。≥N”为真时,求Ⅳ的最大值.

(2002.口本数学奥林匹克(第二轮))

解:这里仅讨论边与坐标轴平行的矩形对F

这表HJ{在5个矩形R。、R。、R,¨RⅢ、/1,。中至少有?个矩形包含rS中的多于399个点.否则,s中至多有除A、B、C、D外的399×5=1995个点,这与已知S有2002个点矛盾.故(1)成立.

下面证明(2).

中的任意两点P、p,Rrv表示以加为对角线的矩

形,孵。表示S在矩形蜀。中点的个数.在此,P与Q小必相异;若P勺Q相同.则在矩形毋。内无点.记

配w=0.

”涩

——

猕怒}00够

mI

一——400

F面证明所求N的最大值为400.

(1)无论将S的2002个点如何放置,总存在P、Q∈S,满足%"≥4∞;

(2)若S中的2002个点按某种方式放置,则对

VP、p∈S.有IV,u咤<400

罔7

将S中的2002个点如图7放置,分为E、F、G、打、1这5个点组.则有

(i)埘任何一个矩形RⅢ(P、Q∈S)至多包含个点组;

(ii)此点组要么为/要么为至少包含P、Q之的某个点组.

这说明以S中两点的连线段为对角线的矩形至多包含s中的400个点.

(1)和(2)得证故~的最大值为400.

前先证明(1).给定点集S中有2002个点.记S中满址横世标最小、纵坐标最小、磺世标最大,纵坐标最大的4个点分别为A、8、C、D,此4点中的某2点町能柑同

故可断定S中异于A、B、C、D的任意一点(至

少l

998个)至少包含在矩形%、‰、月∞、乩.、风。

“)对于纵坐标小于A和C的某点肘.若肘的

之一的内部.此结论由以下三种情况得出

横坐标小于B的横坐标,则fIf在R。内;否则,M在

~~~

(未完待续)

;燮~二篓i篓==一篡|||~三=一=一~=

篓燮罗塑

万方数据 

一竺一=

间一

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com