竞赛数学中的组合数学问题.doc

计数问题1、计数中求最大值：第一步：分类讨论 （1）情况一，推出目标数 f ≤m1；（2）情况二，推出目标数 f ≤m2；…（s）情况s，推出目标数 f ≤ms；第二步：m0=max{m1，m2，…，ms}，则f ≤m0；第三步：构造模型使计数恰好等于常数 m0，则常数 m0 即为最大值另一种叙述:第1步：由目标数 f ≤m推出可以符合条件；第2步： 由f =m+1推出是不能符合条件；所以 fmax = m 2、计数中求最小值：第一步：分类讨论（1）情况一，推出目标数 f ≥m1；（2）情况二，推出目标数 f ≥m2； …（s）情况s，推出目标数 f ≥ms；第二步：m0=min{m1，m2，…，ms}，则f ≥m0；第三步：构造模型使计数恰好等于常数 m0，则常数 m0 即为最小值另一种叙述:第一步：由目标数 f ≥m推出可以；第二步：由目标数f =m－1推出不能；所以 fmin =m 例1、由9位裁判给参加比赛的12名运动员评分每位裁判对他认为的第一名运动员给1分，第二名运动员给2分，…，第12名运动员给12分最后评分结果显示：每名运动员所得的9个分数中高低分之差都不大于3分。

设各运动员的得分总和分别为e1，e2，e3，…，e12，且e1≤e2≤e3≤…≤e12，求e1 的最大值分析：含1分的格子最多有4列，此4列的每格数字平均不超过22.5，3列呢？2列？1列？解：对9个1分布的列数进行讨论：（1）1分分布在同一列，该列的和为9，e1= 9；（2）1分恰在两列中，列中数字不超过4，两列的和最大为5×9=45，较小的列和≤45÷2，是整数，则较小的列和≤22，故最小的列和e1≤22(21)；（3）1分恰在三列中，列中数字不超过4，三列的和最大为8×9=72，同理 e1≤24；（4）1分恰在四列中，列中数字不超过4，四列的和最大为10×9=90，同理 e1≤22；（5）1分恰在5列中，5列45个数都只能取1、2、3、4，9个裁判只能给出9个1、2、3、4，共36个，填不满5列；同理，1分不能分布在比5更多的列中所以，1最多能在4列中故 e1≤24若前三列中，每列三个1、三个3、三个4，每列的和都是24，第四列5个2，4个5，和为30；第五列4个2，5个5，和为33；以后第k列填9个k，和为9k≥54则 e1=24所以e1 的最大值为24例2、有两副扑克牌，每副牌的排列顺序是：第一张是大王，第二张是小王，然后是黑桃、红桃、方块、梅花4种花色排列，每种花色的牌又按A，2，3，…，J，Q，K的顺序排列。

某人把按上述排列的两副扑克牌上下叠在一起，然后从上到下把第一张丢掉，把第二张放在最底层，把第三张丢掉，把第四张放在最底层……，如此下去，直至最后剩下一张牌则所剩的这张牌是什么？我们先来看下面这道题，是一个小学的竞赛题，称为“做数学”依顺时针方向将数字1，2，3，4，5，6，7写在圆周上首先将数字1删除，然后每次跳过一个未删除的数，删除被跳到位置上的数，依此方法继续进行直到最后只剩下一个数为止例如，删除数字1，跳过数字2；删除数字3，跳过数字4； 删除数字5，跳过数字6； 删除数字7，跳过数字2； 删除数字4，跳过数字6； 删除数字2，所以，剩下最后的一个数是6 图4如果依顺时针方向将1，2，3，…，2004写在圆周上，并依照上述规则操作，试问最后剩下的一个数为 解：第一圈:从1开始，删去所有奇数，余下2k型数：2，4，6，8，…，2002，2004；第二圈:从2开始，删去所有4k-2型数，余下4k型数：4， 8，12，16，…，2000，2004；第三圈:从4开始，删去所有8k+4型数，余下8k型数： 8，16，24，…，1992，2000；第四圈:从16开始，删去所有16k型数，余下16k-8型数：8，24，40，…，1976，1992；第五圈:从24开始，删去所有32k-8型数，余下32k-24型数：8， 40，72…，1960，1992；第六圈:从8开始，删去所有64k-56型数，余下64k-24型数： 40，104，…，1896，1960；第六圈:从8开始，删去所有64k-56型数，余64k-24型数： 40，104，…，1896，1960；第七圈:从104起，删去所有128k-24型数，余128k-88型数：40，168，296，424，552，680，808，936，1064，1192，1320，1448，1576，1704，1832，1960；第八圈:从40起，删去所有256k-216型数，余256k-88型数：168， 424， 680， 936， 1192， 1448， 1704， 1960；第九圈:从168起,删去所有512k-344型数，余512k-88型数：424， 936， 1448， 1960；第十圈:删去424，1448，余下：936， 1960；最后，删去936，余下1960 。

分析：下面我们回顾刚才那道题，也来“做数学”解：依次把牌编为1，2，3，…，108；第一圈:从1开始，删去所有奇数，余下2k型数：2，4，6，8，…，108；第二圈:从2开始，删去所有4k-2型数，余下4k型数：4，8，12，16，…，108；第三圈:从4开始，删去所有8k-4型数，余下8k型数： 8，16，24，…，104；第四圈:从8开始，删去所有16k型型数，余下16k-8数：8，24，40，56，72，88，104；第五圈:从8开始，删去8，40，72，104，余下 24， 56，88；第六圈:删去56，余下24，88；再删24，最后留8888=54+2+13×2+6，第88号牌为第二副牌中的方块6有没有更好的处理方法？我们发现，当牌数为4张时，最后留下的是4号牌；当牌数为8张时，最后留下的是8号牌；当牌数为2k张时，最后留下的是2k号牌；现在共有108张牌，取掉44张时，恰好余64张；按约定先去掉44张牌，第44张是开始排列中的第87号牌，而第88号牌被放到余下的64张牌的最后，故最后留下的是第88号牌请用此方法计算1，2，…，2004余下的最后的数？因为2004－1024=980，所以第980个被去掉的数是第一轮中的1959(980×2－1) ，第981个被去掉的数是1961，从这儿按规则数最后的数是前面的1960。

从1，2，3，…，2004中任选k个数，使得所选的k个数中，一定可以找到能构成三角形边长的3个数(这里要求三角形三个边长互不相等)试问：满足条件的k的最小值考虑等价命题：1，2，3，…，2004中存在k－1个数，其中任意3个数均不能构成一个三角形的3条边长 (这里要求三角形三个边长互不相等)求满足此条件的k的最大值 分析：从小的数开始，找尽量多的数，使之不能构成三角形——两小边之和不大于第3边：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597， 16个数！再增加数一定会有两小边之和大于第3边了，所求的k的最大值为17——怎样表达？ 解：按条件an-2+ an-1≤an≤2004构造递增的正整数数列{an }，并使得an值最小n最大：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，共16个数！其中任意3个数 ai、aj、ak (i＜j＜k )，总有 ai+ aj≤ak-2+ ak-1≤ak ，两小数之和大于第3数，不能成为三角形的3条边对于任意的、项数不少于17且每项值不超过2004的、递增的正整数数列{bn } ，若存在bi、bj、bk (i＜j＜k ＜17)满足bi+ bj＞bk，则此3个数可以成为三角形的3边边长；否则，bk≥ak (k＜17)， b15+ b16 ≥ a15+ a16＞2004≥ b17，b15，b16，b17可以成为三角形的3边边长 。

即所求的k的最小值为17 例3、在2×3的矩形方格纸上，各个小正方形的顶点称为格点以格点为顶点的等腰直角三角形有（ ）个A．24 B．38 C．46 D．50解： （1）直角边为1的三角形有4×6=24个；（2）直角边为2的三角形有4×2=8个；（3）直角边为的三角形有4×2+6=14个； 图5（4）直角边为的三角形有4个；运用分类计数原理与分步计数原理分类计数原理与分步计数原理（即加法原理与乘法原理）是关于计数的两个基本原理，是解决竞赛中计数问题的基础例4、已知两个实数集合与，若从A到B的映射f使得B中每个元素都有原象，且，则这样的映射共有（ ）个A）、 （B）、 （C）、 （D）解：设按从小到大排列为（因集合元素具有互异性，故其中不含相等情形）将A中元素分成50组，每组依次与B中元素对应．这里，我们用，表示， ，…考虑，容易得到，这就是说只能写在的右边，故只需在之间的99个空位“”中选择49个位置并按从左到右的顺序依次填上从而构成满足题设要求的映射共有个因此选D例5、有人要上楼，此人每步能向上走1阶或2阶，如果一层楼有18阶，他上一层楼有多少种不同的走法？解法1：此人上楼最多走18步，最少走9步。

这里用分别表示此人上楼走18步，17步，16步，…，9步时走法（对于任意前后两者的步数，因后者少走2步1阶，而多走1步2阶，计后者少走1步）的计数结果考虑步子中的每步2阶情形，易得，，，…，综上，他上一层楼共有种不同的走法解法2：设表示上n阶的走法的计数结果显然，，（2步1阶；1步2阶）对于起步只有两种不同走法：上1阶或上2阶因此对于，第1步上1阶的情形，还剩阶，计种不同的走法；对于第1步上2阶的情形，还剩阶，计种不同的走法同理：，，…，例6、在世界杯足球赛前，F国教练为了考察这七名队员，准备让他们在三场训练比赛（每场90分钟）都上场假设在比赛的任何时刻，这些队员中有且仅有一人在场上，并且每人上场的总时间（以分钟为单位）均被7整除，每人上场的总时间（以分钟为单位）均被13整除如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况解：设上场的总时间分别为分钟根据题意，可设，，其中令，，其中，，且易得其一个整数特解为，又因，故其整数通解为再由，得，故整数从而其满足条件的所有整数解为对于的正整数解，可以写一横排共计33个1，在每相邻两个1之间共32个空位中任选3个填入“+”号，再把3个“+”号分隔开的4个部分里的1分别统计，就可得到其一个正整数解，故有个正整数解；同理有个正整数解；从而此时满足条件的正整数解有个。

因此满足条件的所有正整数解有个，即按每名队员上场的总时间计算，共有42244种不同的情况2、运用容斥原理容斥原理，又称包含排斥原理或逐步淘汰原理顾名思义，即先计算一个较大集合的元素的个数，再把多计算的那一部分去掉它由英国数学家J.J.西尔维斯特首先创立这个原理有多种表达形式，其中最基本的形式为：设是任意n个有限集合，则例7、由数字1，2，3组成n位数，且在这个n位数中，1，2，3的。