网上找的一些数学基础组合1

1、第二章 从鸽笼原理到Ramsey理论鸽笼原理n+1个鸽子飞回n个鸽笼至少有一个鸽笼含有不少于2只的鸽子也有人将鸽笼原理称为抽屉原理。鸽笼原理抽去具体的“鸽笼”、“抽屉”等物理属性，从数学上看，就是把m个元素分放到n个盒子中去，当不能均匀分放时，总有一个盒子内元素数目要超过“平均数”，由此得出鸽笼原理的基本描述： m(m1)个元素分成n个组，那么总有一个组至少含有元素个数为 m/n注： 为“上整数”记号，其中当m表示为mnq+y(0=y=n-1)时 q+1 当 y0m/n= q 当 y=0例4 设qi是正整数(i1,2,.,n)，q=q1+q2+qn-n+1。如果把q个物体放入n个盒子中去，则存

2、在一个i，使得第i个盒子中至少有qi个物体。 证明：用反证法。假设结论不成立，每个盒子都装不到应装的数。即对每一个i，第i个盒子至多放有ni个物体，ni=q1+q2+qn-n+1矛盾，从而结论成立。显然鸽笼原理是qi2(1=5=r(p,g)时，任何一个2色完全图kn，或者含有红色完全图kp(即kp每条边都是红的)，或者含有蓝色完全图kg，两者必居一，而当nr(p,g)时，存在2色完全图kn，它不含红色完全子图kp和蓝色完全图kg。数r(p,g)叫做Ramsey数。 我们还可以换一种更一般化的说法：一对常数p和g对应一个常数n，使得n个人中或有p个互相认识，或有g个互不认识，这个n的最小值用r(

3、p,g)表示。 显然r(1,g)1，r(2,g)g，r(p,g)r(g,p)。例 某俱乐部有个约定，4人围坐在圆桌旁一起打桥牌，必须每人和两旁的人曾合作过，或者都不曾合作过。证明只要俱乐部里有6名成员，就一定能凑集4人在一起打桥牌，如果俱乐部只有5名成员，结论成立吗?证明：我们将俱乐部成员作为图的顶点，若两人曾合作(或不曾合作)删在相应商顶点之间连一条边。根据每人和两旁的人曾合作(或不曾合作)的规则，4人打桥牌可组成两种四边形C4，见图。组合问题的基本解题方法我们从各区域的顶点总数和所有区域的内角和的总和两个角度进行分析： 设：Nk区域中k边形的个数。 角度1：各区域顶点总数(包括重复计算的数

4、目)的等式为 3N3+4N4+mNm4C(n,4)+n(n-2) 其中m是各区域边数的最大值，n是凸多边形的顶点数。组合问题的基本解题方法左式表示的各区域顶点总数来自两个方面： 由于每两条对角线(或四个顶点)决定一个内部区域的顶点，因此区域的顶点数是4C(n,4)，即每个内部顶点在左式中计数4次(总是四个区域公共一个顶点)。又因为在计算中，凸多边形的每个顶点(为n-2个三个角形的公共顶点)重复计数n-2次，因此左式的计算中，n个顶点被计数为n(n-2)，由此得出等式。组合问题的基本解题方法角度2：所有区域的内角和的总和的等式为 1800N3 N4 Ns+(m-2)1800Nm C(n,4)36

5、00+(n-2)1800左式表示的所有区域的内角和的总和来自两个方面：(1)各内部顶点处区域内角和(3600)的总和为C(n,4)3600；(2)凸多边形的内角和为(n-2)1800由此得出等式。 组合问题的基本解题方法 等式2两边同除以1800，得出 N3+2N4+(m-2)Nm2C(n,4)+(n-2) 殊途同归。由等式(1)两边同时减去等式(2)两边，可得出区域总数： N3+N4+N5+NmC(n,4)+C(n-1,2)这就是说，所求的区域总数为C(n,4)+C(n-1,2) 组合问题的基本解题方法数论方法：应用奇偶性、整除性等数论性质进行存在性问题的分析推理。例 设n位客人，在晚会上每

6、人与他人握手d次，d是奇数。证明n是偶数。 证：由于每一次握手均使握手的两人各增加一次与他人握手的次数，因此，n位客人与他人握手次数的总和nd是偶数握手次数的2倍。根据奇偶性质，已知d是奇数，那么n必定是偶数。L形骨牌形状如图 L形骨牌的完全覆盖，是指互不重叠的L形骨牌对图形的无间隙的覆盖，并且没有任何一块骨牌伸出图形之外。 (1)证明54、66的矩形不可用L形骨牌完全覆盖； (2)证明，如果一个mn矩形是可用L形骨牌完全覆盖的话，那么所用的骨牌必定是偶数； (3)证明，若m、n均大于3，并且8整除mn，那么mn矩形可用L形骨牌完全覆盖。注意两个事实1. 24矩形是L形骨脾可完全覆盖的，2.

7、58矩形也是L形骨牌可完全程盖的。 现设m可被4整除，n可被2整除(或n可被4整除，m可被2整除)那么，矩形可分为若干个24矩形，从而明显可被L形骨牌所覆盖；又若m(或n)可被8整除，n(或m)为奇数，那么矩形可分为若干个28矩形和一个58矩形，所有这些矩形都是可用L形骨牌完全覆盖的。综上所述，当m,n均大于3，且可用8整除mn时，mn矩形可用L形骨牌完全覆盖。(3)证明，若m、n均大于3，并且8整除mn，那么mn矩形可用L形骨牌完全覆盖。延伸结论(1) L形骨牌完全覆盖的一个充分必要条件:mn矩形可用L形骨牌完全覆盖，当且仅当mn可被8整除(2)如果矩形不能被L形骨牌完全覆盖的话，我们可根据

8、上述推论结果，分析得出由m、n值确定的最少空格数STEP：若m*n能被4整除而不能被8整除的话，则STEP4否则 STEP(m*n)除以4的余数。例 对于任意一个mn的矩阵，求L形骨牌覆盖后所剩方格数最少的一个方案。我们定义结点的状态为骨牌覆盖后的矩阵状态。一个L形骨牌覆盖某方格，该方格值为1，否则为0。经过旋转或翻转使之吻合的两种L形骨牌算是同一形状，共得L形骨牌的八种形状，见图。例 对于任意一个mn的矩阵，求L形骨牌覆盖后所剩方格数最少的一个方案。结点的算符为L形骨牌的形状序号。试放当前骨脾时，不是所有形状的骨牌都适用。若形状i(1=i=8)的骨牌放入以某空格为左下角的33的方阵后，伸出矩

9、形之外或者与其它骨牌重叠，那么算符i显然是不适用的，应当舍去。因此，不产生越界和重叠是算符采用的约束条件。例 对于任意一个mn的矩阵，求L形骨牌覆盖后所剩方格数最少的一个方案。扩展结点时参与运算的变量主要有四个1搜索的方格坐标x，y我们按自上而下，由左至有的顺序逐格搜索。若某格(x,y)为空格，就在以其为左上角的33方阵内，逐一试放形状1形状8的骨脾；例 对于任意一个mn的矩阵，求L形骨牌覆盖后所剩方格数最少的一个方案。 2当前骨牌覆盖后所剩的空格数Blank 搜索前，我们根据m，n值预先确定最少空格数Step，以此作为槛值。在搜索过程中，若当前的Blank超过这个边界值，则废弃最后一个L形骨

10、牌的放法，回溯至上一格，重新试放下一形状的L形骨牌，直至满足空格数为Step的覆盖方案产生为止。例 对于任意一个mn的矩阵，求L形骨牌覆盖后所剩方格数最少的一个方案。3.已用的骨牌数Lt 由于是按顺序逐格搜索第Lt块骨脾的放入位置，因此，每搜索一格需递归调用一次。若当前格被覆盖，则递归搜索下一格(x,y)时，Blank和Lt不变；若任何形状的L形骨牌未能放入某空格对应的33方阵，则递归搜索下一格(x,y)时，Blank+1，Lt不变，若当前空格对应的33方阵放入某形状的骨牌，则递归搜索下一格(x,y)时，B1ank不变，Lt+1。例 对于任意一个mn的矩阵，求L形骨牌覆盖后所剩方格数最少的一个

11、方案。显然：搜索过程与上述四个变量的当前值密切相关，因此我们将它们作为递归过程Run的四个值参。Run(x,y,Blank,Lt)Run(x,y,Blank,Lt)begin if BlankStep then Exit; if 搜索了矩阵的所有格子 then 打印结果并退出程序; if (x,y)已覆盖 then Run(x,y,Blank,Lt) else begin 在(x,y)对应的33方阵中试放形状1.形状8的骨牌 if 未能放入所有形状的骨牌 then Run(x,y,Blank+1,Lt) else begin 在(x,y)对应的33的方阵内放入某形状的骨牌； Run(x,y,B

12、lank,Lt+1); 恢复第Lt+1块骨牌放入前的矩阵状态； end;end;练习： 1一个售货亭前排着2N个人的队伍等候购物，假定他们都购买价值5元的同一货物。其中N个人持5元货币，N个人持10元货币，而售货员开始发售货物时没有零钱。问有多少种排队方式可使得售货员能依次顺利出售货物，而不出现找不出钱的局面。练习： 2现有一个NN的棋盘，按由左至右、由上而下的顺序编号(如图)。12nn+1n+22nn2其中棋盘上的若干格被挖空。 假设一块多米骨牌恰覆盖棋盘两格，问是否可用这种骨牌互不重选地将这张残缺的棋盘完全覆盖(没有一格未被覆盖，也没有骨牌伸出棋盘或盖住挖空处)。若不能完全覆盖，则给出一个

13、未覆盖的棋格数最少的方案。 输入： 棋盘规模N； 挖去的格子数M； 以下M行为M个被挖空的格子的编号。 输出： 使用的骨牌数X； 以下X行为X个骨牌所覆盖的棋格位置的编号。练习： 3输入MN个士兵的身高，输出一个满足下列性质的M行N列的行军队列：每一行从左到右身高递增；每一列从前到后身高递增。练习： 4现有N个黑棋和N个白棋，将这2N个棋子放入一个NN棋盘，使每行每列都有一个黑棋和一个白棋。求满足上述要求的所有布棋方案。练习： 5有一座大楼，大楼有N层，共居住M个人。已知每个人的出发层和目的层现有最多可乘K人的电梯1部，电梯从l楼出发，求一个最佳方案，在这个方案下，M个人顺利到达目的地且电梯经过的路程数(以一层为一路程单位)最少。练习： 6在NAJ方格棋盘中，有莱一方格不布棋于，其它方格都布上棋子。跳棋规则如下： (1)每枚棋子在跳动时，其相邻方格(有公共边的方格)必须有一枚棋子为垫子才能起跳； (2)棋子只能沿水平或垂直方向跳动一格； (3)棋子跳过垫子进入垫子相邻方格同一方向的空格，并把垫子取出棋盘 编程实现 (1)由键盘输入一个空格位置； (2)棋子按规则跳动，使棋子余下最少； (3)输出方式直观，易于查对。练习： 7对于题6的棋盘 编程实现 (1)求出一个空方格最少的初始状态，能使棋局依跳棋规则跳动时，棋盘棋子只余下一枚，并演示跳