第42届IMO预选题解答(上)
李建泉译
代数部分
1.设T表示由非负整数组成的三元数组
(p,q,r)所构成的集合.求所有函数f:T→R,使得
f(p,q,r)=
0,pqr=0,
1+16[f(p+1,q-1,r)+f(p-1,q+1,r)
+f(p-1,q,r+1)+f(p+1,q,r-1)pqr≠0,
+f(p,q+1,r-1)+f(p,q-1,r+1)],
其中R为实数集.
解:首先证明最多有一个函数满足所给的条件.
假设f1和f2均满足所给的条件,定h=f1-f2,
则h:T→R,且满足
h(p,q,r)=
0,pqr=0,
1
6[h(p+1,q-1,r)+h(p-1,q+1,r)
+h(p-1,q,r+1)+h(p+1,q,r-1)pqr≠0.
+h(p,q+1,r-1)+h(p,q-1,r+1)],
观察pqr≠0的情况可知,h(p,q,r)是h在
(p+1,q-1,r),(p-1,q+1,r),(p-1,q,r+1),
(p+1,q,r-1),(p,q+1,r-1),(p,q-1,r+1)这
六个点取值的算术平均值,其中这六个点是平面x+
y+z=p+q+r内以(p,q,r)为中心的正六边形的
六个顶点.
设n是正整数,考虑平面x+y+z=n在非负卦
限{(x,y,z)|x,y,z≥0}内的子集H,假设h在
(p,q,r)∈H∩T取得最大值.如果pqr=0,则h在
H∩T上的最大值为0;如果pqr≠0,h的平均的性质
表明,h在六个点(p+1,q-1,r),(p-1,q+1,r),
(p-1,q,r+1),(p+1,q,r-1),(p,q+1,r-1),
(p,q-1,r+1)的值都等于h(p,q,r),且这六个点
都在H中.特别地,h也在(p+1,q-1,r)取得最大
值.重复前面的过程(如果有必要),将(p+1,q-1,r)
看作正六边形的中心,有
h(p,q,r)=h(p+1,q-1,r)=h(p+2,q-2,r).
继续这一过程,可得h(p,q,r)=h(p+q,0,r)
=0.于是h在H∩T上的最大值为0.
对于函数-h=f2-f1,应用同样的方法可得-h
在H∩T上的最大值也为0.从而h在H∩T上的最
小值也是0,因此,在H∩T内的所有点处均有h=0.
当n取不同的正整数时,我们可得在T内的所
有点处均有h=0,即f1=f2.
对于定义在T上的任何函数f,定义函数A[f]为
A[f](p,q,r)
=16[f(p+1,q-1,r)+f(p-1,q+1,r)
+f(p-1,q,r+1)+f(p+1,q,r-1)
+f(p,q+1,r-1\]+f(p,q-1,r+1)].
则对于实数c,有
A[cf\]=cA[f],A[c+f\]=c+A[f].
我们只要求f,使得f=1+A[f].
设g(p,q,r)=pqr,则
A[g](p,q,r)=16[6pqr-2(p+q+r)]
=g(p,q,r)-p+q+r3,
A3p+q+r·g(p,q,r)
=3p+q+r·g(p,q,r)+1.
所以,f=3p+q+r·g(p,q,r)=3pqrp+q+r.
2.设a0,a1,a2,…是任意一个由正整数组成的
无穷序列.证明:存在无穷多个正整数n,使得
1+an>an-1n2.
证明:定义序列c0,c1,c2,…满足
c0=1,cn=an-11+a
n
·cn-1,n≥1,重写为
cn=an-1cn-1-ancn.
则c1+c2+…+cn=a0c0-ancn=a0-ancn.
由于{an}为正整数序列,则{cn}为正整数序列.
所以,c1+c2+…+cn
因此,原命题等价于证明存在无穷多个n,使得
cn
cn-1<2
-1n成立.
42中等数学
反证.假设存在正整数N,使得对于n≥N,均有
cn
cn-1≥2
-1n.
当n>N时,有
cn
cn-1·
cn-1
cn-2·…·
cN+1
cN≥2
-1n-1n-1-…-1N+1,
即cn≥cN·2-1N+1+1N+2+…+1n=C·2-1+12+13+…+1n,
其中C=cN·21+12+13+…+1N是一个正常数.
对于如上的n,存在正整数k,使得2k-1≤n<
2k,则
1+12+13+…+1n
≤1+12+13+14+…+17+…
+12k-1+…+12k-1
≤1+1+…+1=k.
所以,cn≥C·2-k,其中2k-1≤n<2k.
对于如上的N,存在正整数r,使得2r-1≤N<
2r.当m>r时,有
c2r+c2r+1+…+c2m-1
=(c2r+…+c2r+1-1)+(c2r+1+…+c2r+2-1)
+…+(c2m-1+…+c2m-1)
≥C(2r×2-(r+1)+2r+1×2-(r+2)+…
+2m-1×2-m)
=C(m-r)2.
这表明cn的和可以任意大,与c1+c2+…+cn
的有界性矛盾.所以,有无穷多个n,使得cnc
n-1
<2-1n
成立.
3.设x1,x2,…,xn是任意实数.证明:
x1
1+x21+
x2
1+x21+x22+…+
xn
1+x21+…+x2n
证明:由柯西(Cauchy)不等式,对于任意实数a1,
a2,…,an有
a1+a2+…+an≤n·a21+a22+…+a2n.
令ak=xk1+x2
1+…+x
2
k
,k=1,2,…,n.
只要证明
x1
1+x21
2
+x21+x2
1+x
2
2
2
+…+xn1+x2
1+…+x
2
n
2
<1.
当k≥2时,有
xk
1+x21+…+x2k
2
≤x
2
k
(1+x21+…+x2k-1)(1+x21+…+x2k)
=11+x2
1+…+x
2
k-1
-11+x2
1+…+x
2
k
.
当k=1时,x11+x2
1
2
≤1-11+x2
1
,因此,
∑
n
k=1
xk
1+x21+…+x2k
2
≤1-11+x2
1+…+x
2
n
<1.
4.求所有函数f:R→R,对任意x,y∈R,f满足
f(xy)(f(x)-f(y))=(x-y)f(x)f(y),
其中R为实数集.
解:令y=1,则
f(x)(f(x)-f(1))=(x-1)f(x)f(1),
即f2(x)=xf(x)f(1).
如果f(1)=0,则f(x)=0对所有x成立,满足已
知条件.
假设f(1)=c≠0,则f(0)=0.设G={x|x∈R,
且f(x)≠0}.显然0∈G,且对于所有x∈G,有f(x)
=xf(1).于是,满足已知条件的函数为
f(x)=Cx,x∈G,0,x∈G.(1)
下面确定G的结构,使得由式(1)定义的函数对
于任意实数x,y∈R满足已知条件.
易验证,如果x≠y,且x,y∈G,当且仅当xy∈G
时,由式(1)定义的函数满足已知条件.x,y∈G时,
由式(1)定义的函数也满足已知条件.由对称性,只考
虑x∈G,y∈G的情况.
当x∈G,y∈G时,有f(y)=0,则已知条件化为
f(xy)f(x)=0.
因为x∈G,所以f(x)≠0,于是f(xy)=0.从而
有xy∈G.
(i)如果x∈G,则1x∈G.
若1x∈G,则x·1x=1∈G,与1∈G矛盾.
(ii)如果x,y∈G,则xy∈G.
若xy∈G,由(i)知1x∈G,从而1x·xy=y∈G,矛
盾.
(iii)如果x,y∈G,则xy∈G.
522002年第5期
由(i)知1y∈G,由(ii)得xy∈G.
所以G包含1,不包含0,且关于乘法和除法是封
闭的.于是关于乘法和除法的封闭性表明了G的特
征.
我们最后写出这个问题的所有解:
f(x)=Cx,x∈G,0,x∈G.
这里C是任意一个固定常数,G是任意满足关于乘
法和除法封闭的R的子集.其中C=0时即为前面提
到的平凡解.
5.求所有正整数a1,a2,…,an,使得
99
100=
a0
a1+
a1
a2+…+
an-1
an,
其中a0=1,(ak+1-1)ak-1≥a2k(ak-1),k=1,2,…,
n-1.
解:设a1,a2,…,an是满足已知条件的正整数.
因为a0=1,所以a1≠1,否则a0a
1
=1>99100.即有a1≥
2,且a1>a0.假设ak>ak-1,ak≥2,则
ak+1≥a
2
k(ak-1)
ak-1+1>
a2k(ak-1)
ak-1≥
a2k
ak-1>ak.
综上所述,有
ak+1>ak,ak+1≥2,其中k=0,1,2,…,n-1.
将不等式(ak+1-1)ak-1≥a2k(ak-1)重写为
ak-1
ak(ak-1)≥
ak
ak+1-1,
即ak-1a
k
≤ak-1a
k-1
-aka
k+1-1
.
对于k=i+1,i+2,…,n-1,及an-1a
n
n-1
求
和可得
ai
ai+1+
ai+1
ai+2+…+
an-1
an<
ai
ai+1-1.
当i=0时,有
1
a1≤
99
100<
1
a1-1,
即10099≤a1<19999,则a1=2.
当i=1时,有
a1
a2≤
99
100-
1
a1<
a1
a2-1,
即20049≤a2<20049+1,则a2=5.
当i=2时,有
1a
3
≤1a
2
99
100-
1
a1-
a1
a2<
1
a3-1,
即5559≤a3<5559+1,则a3=56.
当i=3时,有
1
a4≤
1
a3
99
100-
1
a1-
a1
a2-
a2
a3<
1
a4-1,
即56×14×100≤a4<56×14×100+1,则
a4=78400.
当i=4时,有
1
a5≤
1
a4
99
100-
1
2-
2
5-
5
56-
56
78400=0,
不可能.
因此,a1=2,a2=5,a3=56,a4=78400是惟一
的解.
6.本届IMO第2题.
组合部分
1.设A=(a1,a2,…,a2001)是一个正整数序列,
m为3元子序列(ai,aj,ak)的数目,其中1≤i
≤2001,且满足aj=ai+1及ak=aj+1.考虑所有这
样的序列A,求m的最大值.
解:在序列A中考虑下列两个操作.
(1)如果ai>ai+1,交换这两项得到新的序列
(a1,a2,…,ai+1,ai,…,a2001).
(2)如果ai+1=ai+1+d,其中d>0,将a1,a2,
…,ai同时加上d,得到新的序列
(a1+d,a2+d,…,ai+d,ai+1,…,a2001).
显然,施行操作(1),则m的值不减,重复操作
(1),能使序列重排为非减序列.因此,可以假设m有
最大值的序列是非减序列.如果A是非减序列,施行
操作(2),则m的值不减,因此,任意有最大值m的集
合A具有下列形式.
(a,…,a
t1个
,a+1,…,a+1
t2个
,…,a+s-1,…,a+s-1
ts个
).
这里t1,t2,…,ts是每个子序列的项数,且s≥3,t1+
t2+…+ts=2001.对于这样的序列A,有
m=t1t2t3+t2t3t4+…+ts-2ts-1ts.
当s>4时,可将2001分成s-1个部分,而使m
增加,即
t2+t3+(t1+t4)+t5+…+ts=2001.
则t2t3(t1+t4)+t3(t1+t4)t5+(t1+t4)t5t6+…
>t1t2t3+t2t3t4+t3t4t5+t4t5t6+….
62中等数学
当s=4时,做如上的变化t2+t3+(t1+t4)=
2001,则m的值不改变.
于是,当s=3时,m有最大值.易知当t1=t2=
t3=20013=667时,m有最大值6673=296740963.
这个最大值当s=4时也能获得.设t1=a,t2=
t3=667,t4=667-a,其中1≤a≤666,则m的最大值
为6673=296740963.
2.本届IMO第4题.
3.定义一个“kO团”为一个k个人的集合,使得他
们中的每一对都互相认识.在某次集会上,每两个
“3O团”中至少有一个人是公共的,且不存在“5O团”.证
明:在这次集会上存在两个(或更少的)人,当他们离
开后,不再有“3O团”出现.
证明:为了方便起见,我们采用图论的语言,将集
会上的每个人用一个点来表示.如果两个人相互认
识,则在两个顶点之间连一条边.于是,一个“mO团”
对应着一个m个点的集合,每两个顶点之间连一条
边.换句话说,这样一个“mO团”存在,就意味着所给
图中包含一个有m个点的子图为完全图Km.特别
地,一个“3O团”对应着一个三角形(K3).我们需要证
明:
在任意一个图G中,任意两个三角形至少有一
个顶点是公共点,且不存在K5,则存在两个(或更少
的)点,移去这些点之后,不再有三角形出现.
设G是满足上述条件的一个图,如果在G中最
多有一个三角形,结论显然成立.
我们分两种情况讨论(如图1、2).
图1图2
(1)设T1={p,q,r},T2={r,s,t}.如果删去r,
则毁掉了所有的三角形.
如若不然,有第三个三角形T3,当删去r后没被
毁掉,这个三角形一定与T1和T2均有公共点,则这
样的三角形转化为情形(2)(如图2),且x=r,u∈
T1,v∈T2.
(2)设T1={u,v,x},T2={u,v,y}.如果删去
u,v,则毁掉了所有的三角形.
如若不然,则存在某个z∈{u,v,x,y},且三角形
图3
{x,y,z}出现.特别地,xy是
一条边,此时G包含下列子
图(如图3).我们证明删去
x,y后,毁掉了所有的三角
形.
假设没有全毁掉,则存
在一个三角形T与{x,y}无
公共点.因为T与{x,y,z}
有一个公共点,则T包含z.同理T也包含u和v.于
是T={z,u,v}.又因为G中没有K5,矛盾.所以,存
在两个(或更少的)点,移去之后不再有三角形出现.
4.由三个非负整数构成的集合{x,y,z}(x
z)被称为“历史”的,如果{z-y,y-x}={1776,
2001}.证明:所有非负整数构成的集合可以分成两
两不交的“历史”的集合的并.
证明:为方便起见,设a=1776,b=2001.实际
上,只要满足0
定义A={0,a,a+b},B={0,b,a+b},则A和
B都是“历史”的,且集合X是“历史”的,当且仅当X
=x+A或x+B,其中x是某个非负整数,而x+S=
{x+s|s∈S}.
实际上,若X=x+A或x+B,则X显然是“历
史”的;反之,若X是历史的,设X={x,y,z},且x<
y
若z-y=a,y-x=b,则X=x+B;
若z-y=b,y-x=a,则X=x+A.
我们将构造一个由两两不交的“历史”的集合组
成的无限序列X0,X1,X2,…使得:如果k是在X0到
Xm中没有出现过的非负整数中最小的一个,则让k
属于Xm+1.于是,这无限个集合的并包含了每个非负
整数.
设X0=A,假设我们已经构造了X0到Xm,设k
是在这些集合的并U=∪
m
i=0
Xi中没出现过的最小的非
负整数,若k+a∈U,则设Xm+1=k+A;否则设Xm+1
=k+B.
假设构造到Xm就无法构造了,由于X0到Xm中
每一个集合中最小的元素都小于k,所以元素k和k
+a+b均不在U中,故若构造失败,必有k+b∈U.
因为若k+a∈U,则可以继续构造Xm+1=k+A,所
以k+a∈U.从而取Xm+1=k+B.因为构造失败,且
k∈U,k+a+b∈U,则必有k+b∈U,且k+b一定
是某个Xj中最大的元素,其中j≤m.设l表示Xj中
722002年第5期
最小的元素,则
k+b=l+a+b.
所以k=l+a.因为k∈U,所以l+a∈U.于是有Xj
=l+B.但是我们前面已经约定,当l+a∈U时,Xj
=l+A,矛盾.
因此,构造可以无限地进行下去.
5.求所有的有限序列{x0,x1,…,xn},使得对每
个j,0≤j≤n,xj等于j在序列中出现的次数.
解:设{x0,x1,…,xn}是任意一个满足条件的序
列.因为每一个xj是j出现的次数,所以,数列中的每
一项都是非负整数,且x0>0.
设m表示x1,x2,…,xn中正数项的数目,设
x0=p≥1,于是xp≥1,从而有m≥1,且
∑
n
i=1
xi=m+1.
这是因为左边的和是这个序列全部正数项的数目(包
括x0>0)(若对于某个xi=j>0,则xj一定存在,且
至少有一个非i的值出现.如果i≠j,则j即为非i的
值;如果i=j,0即为非i的值).因为和式∑
m
i=1
xi中有
m个正项,所以只能是m-1项为1,1项为2,余下的
为0.因此,只有x0可以超过2.对于j>2,若xj>0,j
只能是x0.由于x1为1出现的次数,且x1最大为2,
所以有m-1≤2,即m≤3.
(1)m=1.在x1,x2,…,xn中有一个2,没有1,则
x1=0,x2=2,x0=2.于是,所求序列为{2,0,2,0}.
(2)m=2.在x1,x2,…,xn中有一个2,一个1.
若x1=2,则1出现2次,而x1,x2,…,xn中只有
一个1,故x0=1.从而0出现1次,x2=1,x3=0.于
是,所求序列为{1,2,1,0}.
若x2=2,则2出现2次,所以x0=2,0出现2
次,共5项,且x1=1.于是,所求序列为{2,1,2,0,0}.
对于j>2,xj≠2.因为j最多出现1次.
(3)m=3.在x1,x2,…,xn中有一个2,两个1.
若x0=1,则x1=3,不可能.
若x0=2,则x2=2,x1=2,不可能.
设x0=p,其中p≥3,则一定有xp=1,x1=2,x2
=1.于是,所求序列为{p,2,1,0,…,0
(p-3)个
,1,0,0,0}.
综上所述,满足条件的序列分别为
{2,0,2,0},{1,2,1,0},{2,1,2,0,0},
{p,2,1,0,…,0
(p-3)个
,1,0,0,0}.
6.对于一个正整数n,如果一个0-1序列有n
个0,n个1,则称这个序列是“平衡”的.对于两个平
衡序列a,b,如果你能移动a中的某一个数到其他位
置后得到b,则称a和b是“相邻”的.例如,当n=4
时,平衡序列a=01101001和b=00110101是“相邻”
的.因为a中的第3(或第4)个0移到第1(或第2)个
位置后即可得到b.证明:存在一个至多包含1n+1Cn2n
个平衡序列的集合S,使得每一个平衡序列要么等于
S中的一个序列,要么至少与S中的一个序列相邻.
证明:对于每个平衡序列a={a1,a2,…,a2n},
设f(a)是a中1所在位置的序数的和.例如,
f(01101001)=2+3+5+8=18.将Cn2n个平衡序列根
据f模n+1的剩余分为n+1类.设S是包含元素最
少的一类,则|S|≤1n+1Cn2n.我们证明:对于每一个
平衡序列,要么等于S中的一个序列,要么至少与S
中的一个序列相邻.
设a={a1,a2,…,a2n}是一个给定的平衡序列.
分两种情况讨论.
(1)a1=1.将a中左边起第一个1移到第k个0
的右边,得到的平衡序列b={b1,b2,…,b2n}满足
f(b)=f(a)+k(如果设am+1是a的第k个0,在从a
到b的过程中,最左边的1移动了m个位置,而am+1
前面的m-k个1向前移动了一个位置).于是得到
了n个与a相邻的平衡序列,且这n个平衡序列与a
共n+1个平衡序列,其f值构成了n+1个连续整
数.特别地,这n+1个平衡序列中的一个属于S.
(2)a1=0.将a中左边起第一个0移到第k个1
的右边,得到的平衡序列b满足f(b)=f(a)-k.
于是,每一个平衡序列要么等于S中的一个序
列,要么至少与S中的一个序列相邻.
7.以下二题选择一个.
(1)将n块鹅卵石堆放成一竖直列,并根据下列
规则进行操作.如果有一块鹅卵石在某一列的顶部,
且这一列鹅卵石的数目比其右边与其相邻的那列鹅
卵石的数目至少多两块,则这块鹅卵石可以移动(如
果其右边与其相邻的一列中没有鹅卵石,则认为这列
中有0块鹅卵石).每一次操作是在可移动的鹅卵石
中选择一块(如果有可移动的鹅卵石),将它放到其右
边与其相邻的那列的顶部.如果没有鹅卵石可以移
动,这一状态称为“最终状态”.对于每一个正整数n,
82中等数学
证明:在每一次操作中,无论怎样选择鹅卵石,“最终
状态”是惟一的,并描述“最终状态”鹅卵石的分布情
况.
(2)将2001块鹅卵石堆放成一竖直列,并根据下
列规则进行操作.如果有一块鹅卵石在某一列的顶
部,且这一列鹅卵石的数目比其右边与其相邻的那列
鹅卵石的数目至少多两块,则这块鹅卵石可以移动
(如果其右边与其相邻的一列中没有鹅卵石,则认为
这列中有0块鹅卵石).每一次操作是在可移动的鹅
卵石中选择一块(如果有可移动的鹅卵石),将它放到
其右边与其相邻的那列的顶部.如果没有鹅卵石可以
移动,这一状态称为“最终状态”.证明:在每一次操作
中,无论怎样选择鹅卵石,“最终状态”是惟一的.求非
空的列数c.对于每一个i(i=1,2,…,c),求在第i
列中鹅卵石的数目pi.这里第一列是最左边的那列,
第二列是在第一列右边与第一列相邻的那列,等等.
证明:(1)对于每一个状态,设pi是第i列中鹅卵
石的数目,i=1,2,…,其中第一列表示最左边的那
列,我们将证明在“最终状态”,对于所有的i,每一个
pi>0,除了最多一个i3满足pi3=pi3+1外,均有pi
=pi+1+1.
图4
这一状态如图4所示(n
=12时的“最终状态”),共有
c列非空,构成一个三角形
状态.特别地,设
tk=1+2+…+k
=k(k+1)2
是第k个三角形内所包含的鹅卵石的数目,则c是满
足tc-1
设s=n-tc-1,则在最大的一个三角形的斜边上
有s个鹅卵石,使得同样高的两列是第c-s与c-s
+1列(如果s=c,在这种情况中不存在两个非空列
是等高的),且
pi=c-i,i≤c-s,c-i+1,i>c-s.
要证明这一结论,我们先证明如下的三个命题.
(i)在每一个状态,均有p1≥p2≥…;
(ii)在每一个状态,不可能存在i
pi+1,pj=pj+1>0,且pi+1-pj≤j-i-1(即从第i+1
列到第j列每列鹅卵石的数目平均下降1个或更
少).
(iii)在每一个“最终状态”,pi-pi+1=0或1,最
多有一个i,满足pi>0,且pi-pi+1=0.
在证明(i)～(iii)的过程中,我们引用下列定义:
将一个鹅卵石由第k列移动到第k+1列,称为
一次“kO转换”.对于任意一列,不妨设为第i列,称pi
-pi+1为第i列的“减少量”.
证明(i)假设经过一系列有效的移动,在第j
次移动后首次产生pi
必定是一个“i2转换”,但这与已知条件第i列比第i
+1列至少多2个鹅卵石是矛盾的.因此,命题(i)得
证.
证明(ii)假设在某一状态,存在i
=pi+1,pj=pj+1>0,且pi+1-pj≤j-i-1,则在所有
可能的满足如上条件的状态中j-i将有最小值.假
设p1,p2,…是具有j-i为最小值的状态.
若j=i+1,则这一状态之前的一次移动一定是
对于i-1≤k≤i+2的一次“kO转换”.如果是这样的
话,转换之前的状态不满足命题(i).因此,有j>i+
1.考虑在这一系列的移动中,当第一次出现第i,i+
1,j,j+1列上鹅卵石的数目等于“最终状态”这四列
上鹅卵石的数目时,记为状态C.
注意到,在状态C,从第i+1列到第j列,每列
只减少1个鹅卵石.因为如果在某一列“减少量”大于
等于2,由pi+1-pj≤j-i-1,在这j-i列中一定存
在一列,其“减少量”为0.于是j-i不是最小的.因
此,从第i+1列到第j-1列,每列的“减少量”为1.
导致出现状态C的要么是一次“iO转换”,要么是一次
“jO转换”.
若是“iO转换”,这次移动之前,第i+1列与第i
+2列上鹅卵石的数目相同,与j-i为最小相矛盾;
若是“jO转换”,这次移动之前,第j-1列与第j
列上鹅卵石的数目相同,也与j-i为最小相矛盾.因
此,命题(ii)成立.
证明(iii)如果某一列的“减少量”大于等于2,
则操作还没有结束.于是,所有列的“减少量”都是0
或1.如果有两非空列的“减少量”为0,则与命题(ii)
相违.于是“最终状态”满足命题(ii),也满足命题
(iii).
(2)与(1)相同,直接计算可得2001=t63-15,所
以有63个非空列,“最终状态”满足
pi=63-i,i≤15,64-i,16≤i≤63.
8.本届IMO第3题.
922002年第5期
|
|
