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

第1页组合数学论文竞赛数学中的组合数学问题第2页竞赛数学中的组合数学问题组合数学是上个世纪五十年代后逐步建立和完善起来的一门数学分支，组合数学也称为组合学、组合论，组合分析。教科书上对组合分析的定义：按某种要求把一些元素构成有限集合的研究叫做组合分析。这种研究比传统的数学讨论的对象更广泛，在实际生活和实践活动中应用性更大。这种研究一般讨论以下问题：在一定的约束条件下，对象——构成的存在性（有与没有、能与不能）问题；构成的分类与计数；构成的方法（构造方法）及最优化方法。人们常把竞赛中某些问题称为杂题，又称为组合数学问题。为什么？中学数学竞赛中的一些问题，很难把它们归类为代数问题或几何问题，但它们涉及到的解题目标和解题方法可以归入组合问题和组合分析；当然一些组合数学的习题也直接用作竞赛题。初等数学竞赛中的组合问题与组合分析常用的方法有抽屉原理、递推（归）原理、容斥原理、染色方法等，这些原理方法都很一般，重要的是经验和技巧——应用的能力。本文重点研究竞赛数学中的组合数学计数问题。计数问题组合数学中的计数问题，数学竞赛题中的熟面孔，看似司空见惯，不足为奇．很多同学认为只要凭借课内知识就可左右逢源，迎刃而解．其实具体解题时，时常会使你挖空心思，也无所适从。对于这类问题往往首先要通过构造法描绘出对象的简单数学模型，继而借助在计数问题中常用的一些数学原理方可得出所求对象的总数或其范围。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推出可以；第3页第二步：由目标数f=m－1推出不能；所以fmin=m。下面我们从一道简单的组合问题说起：如图，每个正方体的六个面上分别写着数字1，2，3，4，5，6，并且任意两个相对的面上所写的两个数字之和都等于7。把这样的4个正方体一个挨着一个连接起来后，紧挨着的两个面上的数字之和都等于8。图中标着x的那个面上所写的数字是几？分析：拐角处正方体前后分别为4，3，则右侧面可能是1或6，而1不能使x面的对面数字为7，故只能为6，所以x的对面数字为2，所以，x=5。著名的赛题图1证明：任意六个人中，总有三个人，要么相互认识，要么相互不认识。同色分析三步：把实际问题转化为图形染色；抽屉原理；二分法推理。证明：圆上六个点A1A2A3A4A5A6表示六个人，两人相互认识，相应两点间连红线，两人不相识，相应两点间连蓝线，原命题即为证明存在三边同色的三角形。与A1相连的5条线分别染两种颜色，至少有三条线同色。不妨设至少有三条红线，且为A1A2、A1A3、A1A4。若A2、A3、A4三点间的连线有一条红线，则有红色三角形；否则，三条连线都是蓝线，存在蓝色三角形。图2例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；图3（5）1分恰在5列中，5列45个数都只能取1、2、3、4，9个裁判只能给出9个1、2、3、4，共36个，填不满5列；同理，1分不能分布在比5更多的列中。所以，1最多能在4列中。故e1≤24。第4页若前三列中，每列三个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。第5页分析：下面我们回顾刚才那道题，也来“做数学”。解：依次把牌编为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，最后留88。88=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的矩形方格纸上，各个小正方形的顶点称为格点。以格点为顶点第6页的等腰直角三角形有（）个A．24B．38C．46D．50解：（1）直角边为1的三角形有4×6=24个；（2）直角边为2的三角形有4×2=8个；（3）直角边为2的三角形有4×2+6=14个；图5（4）直角边为5的三角形有4个；1、运用分类计数原理与分步计数原理分类计数原理与分步计数原理（即加法原理与乘法原理）是关于计数的两个基本原理，是解决竞赛中计数问题的基础。下面提出的三个问题，注意结合排列与组合的相关知识，构造出相应的模型再去分析就可顺利求解。例4、已知两个实数集合12100,,,Aaaa与1250,,,Bbbb，若从A到B的映射f使得B中每个元素都有原象，且12100()()()fafafa≤≤≤，则这样的映射共有（）个。（A）50100C、（B）4899C、（C）49100C、（D）4999C解：设1250,,,bbb按从小到大排列为1250ccc（因集合元素具有互异性，故其中不含相等情形）。将A中元素12100,,,aaa分成50组，每组依次与B中元素1250,,,ccc对应．这里，我们用1231452aaacaac，表示1231()()()fafafac==，452()()fafac，…考虑12100()()()fafafa≤≤≤，容易得到10050()fac，这就是说50c只能写在100a的右边，故只需在123989910050aaaaaac□□□□□□之间的99个空位“□”中选择49个位置并按从左到右的顺序依次填上1249,,,ccc。从而构成满足题设要求的映射共有4999C个。因此选D。例5、有人要上楼，此人每步能向上走1阶或2阶，如果一层楼有18阶，他上一