“对应”在数学竞赛解题中的应用

●

(嘉兴市第一中学 浙江嘉兴 314050)

“对应”，又称“对应关系”，反映的是2个集合元素之间的关系，通过“对应”可以将各种类别、各种范围、各种层次的对象联系起来，呈现出它们之间的若干属性，通过这些属性的研究使得各种对象之间互相结合、互相转化．

“对应”既是指2个集合的关系，更是一种重要的思想方法．从思想方法的角度来说，“对应”指的是人们在解决某个范畴的数学问题时，通过寻找恰当的对应关系，把原问题转化为另一个范畴的数学问题，再在这个范畴中求解，从而达到解决原问题的思维方法．

在数学竞赛中，应用“对应”有利于提高学生观察问题和分析问题的能力，在解题中也能起到四两拨千斤的效果．下面从几个定理出发，探讨“对应”在数学竞赛中的一些应用．

定理1定义f是从集合X到Y的一个映射，则

(1)如果f为单射，则card(X)≤card(Y)；

(2)如果f为满射，则card(X)≥card(Y)；

(3)如果f为一一映射，则card(X)=card(Y)；

(4)若X和Y是2个有限集，f为m倍映射，则card(X)=mcard(Y)．

定理3在直角坐标系中，设A(a,b)，B(c,d)为2个格点，从A到B的连线由最小格点正方形的对角线首尾相联结而成，而且任何平行于y轴的直线与这条连线最多只有一个交点，把这条连线叫做联结A,B的折线，点A称为这条折线的起点，点B称为终点．

1 “对应”：集合问题的“桥梁”

“对应”反映的是2个集合元素之间的关系，通过“对应”可以实现任何2个集合的沟通与联系，这要求我们在解题时大胆构造，造好“桥梁”．

例1已知集合S={1,2,3,…,2 000}，若S的41元子集中的所有元素之和能被5整除，则该子集称为S的好子集，求S的好子集个数．

f(A)={a1+k,a2+k,…,a41+k}.

当aj+k>2 000时，用aj+k-2 000代替,容易证明f是一一映射，故

|S0|=|Sk| (1≤k≤4).

评注在本题中，将S的所有子集按照所有元素之和被5除的余数进行分类，通过构造“对应”，进而证明其为一一映射，发现|S0|=|Sk|(1≤k≤4)是关键．

例2设n为正整数，记Sn={1,2,…,2n}，定义Sn的2个子集：An={A⊂Sn|card(A)=n,A中的各元素之和为偶数}，Bn={B⊂Sn|card(B)=n,B中的各元素之和为奇数}，对每个n，求card(An)-card(Bn)．

card(An)-card(Bn)=0．

当n为偶数时，将1,2,3,…,2n分组：

(1,2n),(2,2n-1),…，(n,n+1).(1)

此时，对任意X⊂Sn,|X|=n-1,分组(1)中必有一组数据都不属于X．例如1,2n∉X,则X∪{1}与X∪{2n}分属于An和Bn.这表明凡由上述方式构成的An与Bn的元素具有相同的个数．

综上所述，对正整数n，有

评注这里通过构造映射，在An与Bn中的大部分元素之间建立起一一对应，直接定出了card(An)-card(Bn)的值．当然也可以分别求出card(An)与card(Bn)的值，再求出card(An)-card(Bn)．

2 “对应”：函数问题的“基石”

在高中数学中，映射、函数的概念是从“对应”开始的，对一些函数的构造性证明就是寻找“对应”的例子．函数(曲线方程)与函数图像(曲线)就是点与有序数对的对应，这种对应同时可以拓展到一般的数形结合，进而使得代数几何化、几何代数化成为常用的转化方法．

例3分别构造出这样的函数f(x),g(x)，定义域为(0，1)，值域为[0，1]，且

(1)对于常数a∈[0,1],f(x)=a有且仅有一个根；

(2)对于常数a∈[0,1],g(x)=a有无穷多个根．

评注本题用到的是2个无穷集合之间的“对应”，第(1)小题可以联想到著名数学家希尔伯特的“无穷房间问题”，第(2)小题涉及到“多对一”、“无穷对一”映射．本题是复旦大学的自主招生试题，答案不唯一，要有相关函数的模型才能迅速解答．

例4设正实数a,b,c满足

求a,b,c的值．

(2014年浙江省高中数学竞赛试题)

图1

解如图1，以点O为出发点，作长度为a,b,c的3条线段OA，OB，OC，使得∠AOB=90°,∠AOC=120°，那么∠COB=150°．由余弦定理知

于是∠CAB=90°．

过点O作OE⊥AC，OF⊥AB,设AE=m,OE=n，由∠ABO=∠OAE，得

(2)

(3)

3 “对应”：计数问题的“利器”

前文提到的3个定理在计数问题中有着广泛的应用，一大批计数问题都可以通过“对应”来转化：转化为与之可构造一一对应的另一集合、转化为不定方程解的组数、转化为折线的条数等．

例5在世界杯足球赛前，F国教练为了考察A1,A2,…,A7这7名队员，准备让他们在3场训练比赛(每场90分钟)都上场．假设在比赛的任何时刻，这些队员中有且仅有一人在场上，并且A1,A2,A3,A4每人上场的总时间(以分钟为单位)均被7整除，A5,A6,A7每人上场的总时间(以分钟为单位)均被13整除．如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况？

(2002年全国高中数学联赛试题)

解设这7名队员上场的时间为7k1,7k2,7k3,7k4,13k5,13k6,13k7分钟，设7k1+7k2+7k3+7k4=7x,13x5+13k6+13k7=13y,则这7名队员上场的每种时间分布情况与不定方程

7(k1+k2+k3+k4)+13(k5+k6+k7)=270

的一组正整数解{k1,k2,…,k7}之间可建立一一对应．

对于不定方程7x+13y=270,由

解得

解方程组

42 244.

图2 图3

解设正三角形点阵的凸包为正△ABC，边长为n-1．

如图3，将AB,AC分别延长到点B′,C′，使得BB′=CC′=1．将B′C′分成n等份．

对正三角形点阵内任一点X，过X作AB,AC的平行线，与B′C′的交点分别记为Xc,Xb．下面分2种情形讨论：

评注当计数对象的特征不明显或混乱复杂难以直接计数时，我们就设法去寻找一个便于计数的集合，本题将三角形对应到边B′C′上的有序点列，化难为易．

4 “对应”：不等问题的“良方”

不等式证明或求解的方法很多，但也可以用“对应”来解决.在定理1中，发现对于单射和满射可以得到不等式，又比如可以对线段的长度、面积和体积的大小进行比较，这就引导我们去寻求原问题与它们之间的“对应”．

例7设n∈N,若在集合{1,2，…，2n-1}中至少有一个i，使得|xi-xi+1|=n，我们说集合{1,2，…，2n}的一个排列(x1,x2,…,x2n)具有性质P．求证：对于任何n，具有性质P的排列的个数多．

(第30届国际数学奥林匹克竞赛试题)

分析令A和B分别表示具有性质P和不具有性质P的所有排列的集合，C表示恰有一个i∈{1，2，…，2n-1}，使得|xi-xi+1|=n的所有排列的集合．显然，C是A的真子集，由此可见，若能证明card(B)≤card(C)，问题就解决了．

为证明card(B)≤card(C)，在B与C之间建立一个对应如下：对任何y=(y1,y2,…,y2n)∈B，显然有|y1-y2|≠n，因此存在k>2，使得|yk-y1|=n．令排列对应于

f(y)={y2,y3,…,yk-1,y1,yk,yk+1,…,y2n}，

这就是给出了一个由B到C的映射．不难证明这个映射是单射，于是

card(B)≤card(C)

评注本题不要求建立双射，只要是单射就可以了，这显然可用于集合元素个数的估计．

图4

评注本题通过观察题设条件蕴涵的几何意义，构造一个几何图形，将三角和几何实现了对应，使欲证不等式一目了然．

5 “对应”：数列问题的“奇兵”

数列中的对应其实也是比较常见的，解题的手段是通过构造一个与原数列有对应关系的新数列，并通过研究这个数列来探讨原数列的性质．

例9在数列1,9,81，…，92 000中删去最高位数字是9的项，余下的数列有多少项？

解若数列中某项的首位数字是9，则前一项首位数字为1，且相邻2项位数相同．反之，若数列中相邻2项位数相同，则这2个数的首位数字必是一个为1另一个为9．删去最高位数字是9的项，相当于在每对位数相同的项中删去1项．余下数列中每个数的位数恰好为1,2,3，…，t，共有t项，其中t为92 000的位数．易知

t= [lg92 000]+1=[4 000×lg3]+1=

[4 000×0.477 12]+1=1 909．

评注本题很难求出最高位数字是9的那些项，也没有必要求出，考虑到这些项与首位数字是1的项的对应关系，问题便迎刃而解．

例10设an为下述自然数N的个数：N的各位数字之和为n且每位数字只能取1，3或4，求证：a2n是完全平方数，这里n=1,2,…．

解记各位数字之和为n且每位数字都是1或2的所有自然数的集合为Sn，并记card(Sn)=fn，则f1=1,f2=2，且当n≥3时,

fn=fn-1+fn-2．

作映射：f:M→M′(其中M∈Sn，全体M′的集合为Tn)如下：现将M的数字中自左到右的第一个2与它后邻的数字相加，其和作为一位数字；然后再把余下数字中第一个2与它后邻的数字相加，所得的和作为下一个数字；依次类推，直到没有数再相加为止，所得的新自然数M′除最后一位可能为2之外，其余各位数字均为1,3,4．易知f是Sn到Tn的双射，从而

card(Sn)=card(Tn)+card(Tn-2)=fn，

且fn=fn-1+fn-2(n≥3)．

(4)

另一方面，对于任一数字和为2n、各位数字均为1或2的自然数M，必存在正整数k，使得下列的2条之一成立：

(1)M的前k位数字之和为n；

(2)M的前k位数字之和为n-1，第k+1位数字为2，

(5)

由式(4)，式(5)可知

(6)

评注本题有众多的解法，而巧妙运用对应方法，流畅、快捷地解决问题，不失为一种好方法．

数学中的“对应”无处不在，数学的解题实质上就是把一个问题不断转化为另一个与之对应的较易解决的问题．可以说，数学解题始终贯穿着对应思想，充分运用对应思想可以使解题游刃有余．问题间的“对应”有的较为明显，有的深藏其中，需要我们去细心探求、深入挖掘、大胆构造．