映射与计数在解竞赛题中的应用

《映射与计数在解竞赛题中的应用》由会员分享，可在线阅读，更多相关《映射与计数在解竞赛题中的应用（9页珍藏版）》请在装配图网上搜索。

1、学科：奥数本周教学内容：映射与计数在解竞赛题中的应用年级：高一（内容综述】利用映射来解决计数问题，确实是通过成立集合A与另一集合B之间的映射，把对集合A的计数转移到对集合B的计数。实现这种转移的关键是：（1）选择适当的便于计数的集合；（2）成立集合间的映射关系。设f：A-B是集合A到集合B上的映射，那么（1）若f为单射，则团。（2）若f为满射，则国2团。（3）若f为一一映射，则国二团。【例题分析】例1从祖x弘的棋盘中，掏出一个由三个小方格组成的L形，有多少种不同取法？那个地址潴内棋盘是指m条横线与n条竖线所组成的棋盘。解每种取法，都有一个点与它对应，那个点确实是所取L形中三个小方格的公共点（如

2、图1）,它是棋盘上横线与竖线的交点，且不在棋盘的边界上。从图2可看出，每一个点对应于4种不同取法,这4种取法组成一个“田”字形。而每一个“田”字形都有唯一的中心。（例如点B）,即映射f：“田”字形一“田”字形中心，是棋盘上由小方格组成的“田”字集合到棋盘内横线与竖线的交点集（不包括边界上的点）的映射。显然棋盘内横线与竖线的交点有CL=（刑-2*-2）个，因此，共有文以一2）（典-2）种不同取法。例2求n元集合A的所有子集的个数解设集合A的所有子集的集合为P（A）,B为集合A到集合0）的全部映射的集合，关于任意的MuEU）,可唯一确信一个从集合A到集合侦1的映射做：jl,若awM撷=5若必祯（版

3、通常称为集合M的特点函数），即有唯一的痴wE与M对应。反过来,对于任意的即5，有唯一的集合MmE4户1o显然MuEU）,且隐确实是叫因此，映射f：Ml榴是集合P（A）到B的映射。由于n元素集A到集合仙力的映射的个数为尸,即忸依照对应原理说明一样地，集合x=X，X2,Xm到集合y=yi，丫2,，ym的所有映射的个数为小。例3中日围棋擂台赛，双方各派6名队员按预定顺序出场，直到最后一方取胜，问可能出现的比赛过程种数有多少种？解设中国队员对应红球，日方队员对应白球。将被淘汰队员对应的球按被淘汰的时间顺序一一排列出来。负方队员全部被淘汰，则相应球全部排出，然后将胜方所剩队员对应的球依次排在后面。由于双

4、方队员出场顺序己定，故可设同色球之间无区别，于是一种比赛过程就对应于6个红球和6个白球的一种排列；反之，6个红球和6个白球的一种排列对应着一种比赛过程，即球的不同排列与不同比赛过程之间存在一一对应关系。6个红球和6个白球的不同排列数为Gt此即所求竞赛进程种数。说明在某种映射下，两个集合元素间一一对应，该映射即为一一映射，所以对于明显的一一映射只须指出两集合间的一一对应关系，就可运用对应原理。例4求m元方程/十寸f伽工同）的正整数解的组数。解法一由于数组上中各数能够重复，且大小无序，因此作如下映射巴%=而，色=七十，A=xi+x2显然1M乃丁27初-14尸魔=厘且（不程,/）与（丁1必,.必）对

5、应，因此，映射期（xi/ziuGOb乃，为）是一一映射。因为，满足的数组有个，因此所求方程解的组数为c蓑：解法二考虑长度为n的线段AB。方程的任一组解对应于把线段分成m节的一种分法，其中第一节的长度为修，第二节的长度为热，第m节的长度为仆，而每一种分法又对应于线段长n-l个分点中掏出m-1个分点的一种取法。反过来，线段n-l个分点中掏出m-1个分点的任一种取法，都把线段AB分成m节。令xKim）依次取m节的长度，就取得方程的一组解。所以，原方程解的组数就是线段AB上n-l个分点中取出m-1个的不同取法的种数,曹:。说明若把问题改为：求m元方程勺十与十十分二用的非负整数解的组数，只要令必=玉十彘

6、=12），那么化为求方程必十乃十二左十清的正整数解的组数，由例4可知所求解的组数为%泡T。例5设j=023,%,%,%（劭%）为A的三元子集，假设知足的2e+32%+6,则称包，的,的为A的“好子集，求A的“好子集”的个数。解令8=1,2,2-4）=01，出，出）出,%外工，%-%23,%一出23*=出色也肉也，与w瓦瓦b2b3作映射/：（%）-Qi再也），这里（如%）0式4=/也=%-2也=%一4。f是小到上的一一映射。事实上,当.时,%一。223月EC瓦=囱1+1%-2=的一1M%-4=&题-41%。242a2一%23&j143?b3-4另一方面，若1M瓦与马二同-4,那么1a1=b2=a

7、2-2Z）3=a3-41必一%23鼻-a2375于是由对应原理，=B1=cL,即a的“好子集”有c个。例6设n为正整数，若123,，2n的一个排列如均外）中存在和再明使同一卜盟成立，那么称该排列具有性质P。证明：具有性质P的排列比不具有性质P的排列多。证明设A是由不具有性质P的排列构成的集合，B是恰有一对小飞】知足上一餐】上”的排列组成的集合，C是具有性质P的所有排列组成的集合，显然BuC,从而因口。设（小孙叼丹）&J其中必有一个均，使卜再卜”于是调整演的位置如下（称孙心口和小%）,该排列仅有一对相邻数勺不知足,幻从而（马盾一，巧nJe方。上述调整组成了一个A到B的映射，因此，口设区。又因的，

8、故团冏，即具有性质P的排列比不具有性质P的排列多。例7已知2+IF,i=L2为，而且毛十工2十十20,2=2;二2力一勺十十十X=0求区,马”.，小）的个数。解由知（和和，小）中有n个+1,n个T,如此的有序数组有力个。下面考虑如此的有序数组（和孙，称）中有多少不符合，设其个数为4o如果（和马,一小）不符合，那么必然存在最小的自然数s（sSn）,知足（1）勺+X?十十人为.2=0；（2）/4=-1将f2,，/-1通通改变符号，这一对应/:（孙工27?山无2户/2）（一才马?一心弓,7工2我）改成n+1个+1,nT个-1组成的有序数组。反之，对于任何一个n+1个+1,nT个-1组成的有序数组（巧

9、五）,由于+1多于一1,必然存在一个最小的自然数s,知足将（和石,白口孙?,5）变成（一7一七7,勺川才25，,一R）,就取得一个n个+Ln个-1组成的不符合的有序数组，因此，f是一一映射，由对应原理知4等于n+1个+1,n-1个-1组成的有序数组的个数,即理。因此，符合题目条件的有序数组的个数为例8已知数列怎知足%=再十（7）中川,:题1卬对每一个整数求知足条件的下标n的个数。解将满足涉*2卬的自然数n用二进制表示为=（和3.瓦）2,那个地址底=1内0口皿=0,12能够证明“3,.哂十（一1严1）事实上，若是公十/为偶数，那么想三0,3（曲）4）,均有为偶数，且叩片”）；若是公f为奇数，那么

10、钎1,2-H4）,均（+1）产_1、有为奇数，旦LR-.年IK因此式成立。反复利用式可知褊。）（7严。上式右边为k个+1或-1的和。因此，当k为奇数时，的右边为奇数，可不能等于0,这说明，当k为奇数时，知足条件的下标n的个数为0。kk当k为偶数时，若=,那么式右边恰有5个+1,亍个-1。设/=心用2叩，的二进制表示为为=g%F）2LR=由+1或-1构成的耳元有序数组,式确信了一个A到B的映射巴加一%）2fH产成，（-产f，（T严飞）。由于A中任意两个元素的二进制表示首位都为1,设的=（而忆勺）2多=（顺丘瑞2心=1。并设j为使XK的最大下标。那么（一1户厘“（7）%叫0这说明声是A到B的单射。又易知恒上网=2;因此产又是A到B的满射，从而产是A到B的一一映射。k故满足2t靛2卬，且题=0的下标n的个数为B中恰有亍个-1的有序数组的个数，即c*。综上所述，当上为奇数时，知足条件的下标n的个数为0；当k为偶数时，知足条件的下标n的个数为产。运用映射法解决计数问题，关键在于建立映射关系，将难于计数的集合化为易于计数的集合来计数。这项工作具有较强的技巧性，需在平时学习中多体会，多实践。