组合数学 第三章学习资料

3.1某甲参加一种会议,会上有6位朋友,某甲和其中每一个人在会上各相遇12次,每两人各相遇6次,每3人各相遇4次,每4人各相遇3次,每5人各相遇2次,每6人各相遇1次,1人也没遇见的有5次,问某甲共参加几次会议?解:设A为甲与第i个朋友相遇的会议集.i=1,2,3,4,5,6.则│∪A│=12*C(6,1)-6*C(6,2)+4*C(6,3)-3*(6,4)+2*(6,5)-C(6,6)=28甲参加的会议数为28+5=333.2：求从1到500的整数中被3和5整除但是不能被7整除的数的个数。解：设 A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合所以|A7=|A5∩A=5003×5-5003.3n个代表参加会议，试证其中至少有2个人各自的朋友数相等解：每个人的朋友数只能取0，1，…，n－1．但若有人的朋友数为0，即此人和其他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只有n－1种可能．，根据鸽巢原理所以至少有２人的朋友数相等．×3.4试给出下列等式的组合意义证明：（1）从n个不同元素中取k，使得其中必含有m个特定元素的方案数为。设这m个元素为a1,a2,…,am,Ai为包含ai的组合（子集），i=1,…,m.（2）把l个无区别的球放到n个不同的盒子，但有m个空盒子的方案数为令k=n-m，设Ai为第i个盒子有球，i=1，2，…k（3）设Ai为m+l个元素中去m+i个，含特定元素a的方案集；Ni为m+l个元素中取m+i个的方案数。则：3.5设有3个7位的二进制数试证存在整数和，使得下列之一必然成立：解：应用鸽巢原理，在每一个纵列中，含有三个元素，分别都只由两种选择0或1，应用鸽巢原理所以必有中至少一个必然成立；成立的时候取值的不同可以有这样几种情况：=6种，而每一横行共有七个元素，再次用鸽巢原理，必有两列是相同的即：之一必然成立3.6在边长为1的正方形内任取5点，试证其中至少有两点，其距离小于。证明：分别连接对边的中点，这样正方形被均匀的分成四个域，在正方形内任取5点，根据鸽巢原理，至少有两点在同一个域中，而一个域内两点的最远距离小于，所以至少存在两点其距离小于。3.7在边长为1的等边三角形内任取5点，试证至少有两点距离小于。证明：将边长为1的等边三角行分成4等份，如图。则至少有两个点在同一个小三角行中，每个小三角形的边长为，所以至少存在两个点见的距离小于。3.8．任取11个整数，求证其中至少有两个数它们的差是10的倍数。解：易知任意整数的个位数的可能取值只可能为，共10种可能，而利用鸽巢原理，任取的11个整数中，其中至少有两个整数的个位数相同，这两个个位数相同的整数的差显然是10的倍数。即证。×3.9把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍。解：用反证法。设存在划分，Pi中没有数是两数之和，即Pi中没有数是两数之差。设1到326中至少有个元素属于P1，并设为，不妨设，若A中存在一个元素是某两个元素之差，则满足要求。否则，令，令，显然B中的元素仍然是1到326之间的数，即。根据假定B中无一属于P1，否则与假定矛盾。所以B的元素属于P2，P3，P4，P5。与前面讨论类似，设B中至少存在属于P2的个元素。设为。令。根据假定，C中没有数是两数之差。令，，那么，对于所有。易知存在整数使得。所以，D中的元素不属于P1，也不属于P2，只能属于P3，P4，P5。故根据鸽巢原理，设至少存在个元素属于P3。设为。令。根据假定，F中不存在元素是某两个元素之差，令。显然G中的元素不属于P3。且，对于gi存在使得。故G中的元素也不属于P1和P2。则G中的元素属于P4，P5。对于G中的5个元素，根据鸽巢原理，设至少存在个属于P4。设为。令。令。显然，T中的元素不属于P1，P2，P3，P4，故T的元素属于P5。但根据假定，令，则且u不属于P5。同样，u不属于P1，P2，P3，P4，即存在一个整数，不属于P1，P2，P3，P4，P5。这与将1至326之间的整数任意分为5部分的假定相矛盾。A,B,C三种材料用作产品1，2，3的原料，但要求1禁止用B和C作原料，2不能用B作原料，3不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）。解：此问题为有禁区的排列可转化为棋盘多项式求解如图所示：P=R（）=XR（）+R（）=1+4x+4+=4,=4,=1根据定理：n!-(n-1)!+(n-2)!-(n-3)!……故方案为：3！-4（3-1）！+4（3-2）！-1=13.11n个球放到m个盒子中去，，试证其中必有两个盒子有相同的球数。题解：设m个盒子的球的个数是a1,…,am，各不相等，且有0≤a1＜a2＜···＜am．则有a2≥1、am≥m－1，故

≥1+2+…+m－1＝，与相矛盾！所以必有两个盒子的球数相等．×3.12一年级有100名学生参加中文，英语和数学考试，其中92通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中，英文考试，54人通过中文和数学考试，45人通过英语和数学考试，求通过3门学科考试的学生数。题解：设A为通过中文的人数，B为通过英语的人数，C为通过数学的人数。试证1|B|=|B|-|AB|2|C|=|C|-|AC|-|BC|+|ABC|证：设全集为S|B|=|（S-A）B|=|SB|-|AB|=|B|-|AB|同理可证|C|=|C|-|AC|-|BC|+|ABC|3.14，求其中不被5和7除尽，但被3除尽的数的数目。解：设U表示全集，A3表示能被3除尽的数的集合，A5表示能被5除尽的数的集合，A7表示能被7除尽的数的集合。则所求的是。，，，，，同理，所以，3.15．，求其中被2，3，5，7中m个数除尽的数的数目，m=0,1,2,3,4.求不超过120的素数的数目。解：不超过120的素数数目即为：3.16解：3.17n除尽中至少一个数的除数，求n的数目解：A：的约数B：的约数C：的约数|A|=61×61=3721|B|=101×51=5151|C|=41×31=1271=61×51=3111=41×41=1681=41×41=1681=41×41=1681=5351×3.18求下列集合中不是形式的数的数目，。解：BC内元素为1…100000通过程序验证既是2次方又是3次方的即为所求解：即为所求3.19{1000，1001，…，3000}，求其中是4的倍数但不是100的倍数的数的数目。解：A为4的倍数的整数B为100的倍数的整数|A∩B|=|A|-|A∩B|=3000-10004×3.20在由a,a,a,b,b,b,c,c,c组成的排列中，求满足下列条件的排列数 （1）不存在相邻3元素相同 （2）相邻两元素不相同解：（1）设S为总共的排列数，为3个a相邻的排列，为3个b相邻的排列， 为3个c相邻的排列； 所以不存在相邻3元素相同为=（2）设S为总的排列数，为2个以上a相邻的排列，为2个以上b相邻的排列， 为2个以上c相邻的排列； 所以不存在相邻3元素相同为=×3.21：求从O（0，0）点到（8，4）点的路径数。已知（2，1）到（4，1）的线段，（3，1）到（3，2）的线段被封锁。解:由题意设 A1：从(0,0)点到(8,4)点经过(2,1)到(3,1)的线段.A2：从(0,0)点到(8,4)点经过(3,1)到(3,2)的线段.A3：从(0,0)点到(8,4)点经过(3,1)到(4,1)的线段.从(0,0)点到(8,4)点经过(2,1)到(4,1)的线段，根据乘法原理|A1|=C(1,2+1)*C(4-1,8-3+|A2|A3|A1|A1|A2|A1|A1∩A2∩A3|=C(4,12)-(|A1|+|A2|+|A=495-(168+84+140)+(105+63+0)-0=2713—22求满足条件x+x+x=20,3≤x≤9,0≤x≤8,7≤x≤17的整数解数目.解:作变量代换a=x-3,b=x,c=x-70≤a≤6,0≤b≤8,0≤c≤10则方程变为a+b+c=10设s为这个方程的非负整数解集合∣s∣=C(10+3-1,10)=66设p为性质a≥7,p为性质b≥9,p为性质c≥11令A为s中满足性质p(i=1,2,3)的集合,则问题归结为求∣A∩A∩A∣.可求得是方程a+b+c=10(a≥7,b≥0,c≥0)的整数解集合,通过作代换z=a-7,z=b,z=c可得∣A∣=C(3+3-1,3)=10,类似可得∣A∣=C(1+2,1)=3,∣A∣=0∣A∩A∣=0∣A∩A∣=0∣A∩A∣=0∣A∩A∩A∣=0∣A∩A∩A∣=66-13=533.23求满足下列条件X1+X2+X3=206<=X1<=15,5<=X1<=20,10<=X1<=25解：设y1=x1-6.y2=x2-5,y3=x3-10,则有y1+y2+y3=x1+x2+x3-21=19设r1=9-y1,r2=15-y2,r3=25-y3则有r1+r2+r3=49-(y1+y2+y3)=49-19=20即r1+r2+r3=20r1>=0,r2>=0,r3>=0解的数目为3．24求满足下列条件的整数解数目：，，，，解：设，，，，则有，，，则该问题的非负整数解S，，令S中具有的子集为，的子集为，的子集为，的子集为。问题转化为求。对于，相当于或具有性质的非负整数解的数目为同理，，，，，，，，，3.25证明满足下列条件：+++=r()的整数解数目为答案： 设为{} 由 得： 推出： = =3.26试证满足下条件：的整数解为证明：设∴∴整数解为×3.27求n对夫妻排成一行，夫妻不相邻的排列数。解：令=第i对夫妻相邻而坐的集合，，所问的问题为求=（圆桌）×3.28设p,q,p是奇数,现有pq个珠子,着q种颜色,每种颜色有p个珠子，假定相同颜色的珠子无区别，试分别求满足以下条件的珠子的排列数。同颜色的珠子在一起同颜色的珠子处于不同的块同颜色的珠子最多在两个块解：1）由于是同颜色的珠子放在一起，有q！种方案。2）3）3.29将r个相同的球放进n个不同的盒子，无一空盒，求方案数。根据可重复组合公式，组合意义即是，将r个相同的球放进n个不同的盒子，无一空盒，所以总方案数为(n+r-1r).×3.30

试证：证明：令表示第一个盒子为空；表示第二个盒子为空；表示第n个盒子为空表示从n个不同的盒子中取出i个为空盒，则剩下的n-i盒子不为空。=()表示的几何意义是R个相同的球放入n个不同的盒子中，不许有空盒。表示的几何意义是R个相同的球放入n个不同的盒子中，不许有空盒。几何意义相同所证成立。×3.31设B是A的子集，|A|=n,|B|=m,求A的子集中包含B的数目，设子集的元素数目为r,m≤r≤n。解：A的子集中包含B的那部分，即为在A-B中任取值的组合数，可为取1，2，3…….n-m个所以，A的子集中包含B的数目为。×3.32×3.33试证 （1） （2） 其中，定义为0. （3） （4） （5） （6） 是3.6节中推广了的错排。证明：此题可由组合含义证明。等式左边：相当于从ｎ个不同元素中取ｒ个进行排列，其中只有ｋ个元素在原来的位置这样的方案数，为。等式右边：相当于首先在ｒ个元素中取ｋ个元素，为，然后在n-r个元素中取r-k个，对r-k个元素进行完全错排，为，故总的方案数为。左右两端显然相等，证毕。（５）此题可由组合含义证明。从ｎ个不同元素中取ｒ个进行排列，其中只有ｋ个元素在原来的位置的方案数（）可以分为两种情况：即是否包含元素ａ（ａ为任意元素）。第一种情况是包含元素ａ，则只需在剩下的n-1个元素中取r-1个即可，然后进行只有ｋ个元素不变的错排，方案数为；第二种情况是不包括元素ａ，则需要在剩下的n-1个元素中取ｒ个元素，进行只有ｋ个元素不变的错排，方案数为。所以总的方案数为：，即，证毕。×3.34,设表示在{1，2，…，n}的全排列中，排除了k，紧随以k+1,k=1,2,…,k+1，试证：解：×3.35×3.36设Dn(k)=D(n,n,k),试证 （a）（b）Dn(0)-Dn(1)=(-1)n（c）…（d）其中r≤n。3．37

试证对于素数，，证明：根据定理若=是素数所证成立。×3.38试证：（1）n=∑d|nΦ(n)(2)Φ(m,n)Φ(n)=Φ(m)Φ(n)h,其中m,n∈N,h=(m,n)(3)n∈N,n>=3,Φ(n)通常是偶数。解：（1）因为Φ(n)=n∑d|nμ(d)/d所以Φ(n)=∑d|nμ(d)n/d所以我们设n=f(n),Φ(n)=g(n)根据反演定理，可得n=∑d|nΦ(n).（2）因为Φ(m,n)=mn∑d1,d2|m,nμ(d1,d2)/d1,d2根据第一问，可得必然存在一个中间的数h,使得Φ(m,n)Φ(n)=Φ(m)Φ(n)h,其中m,n∈N,h=(m,n)成立。×3.39n，证明若n有k个不同的奇偶因子，则（1）（2）（3），n是奇数，n是偶数解：此题不会。×3.40从集合中随机抽取28次，求出现块的几率。解：3.42一组有1990个人，每个人至少有1327个朋友，试证其中4位，使得彼此都是朋友。答案： 从1990中取出一个人a，剩下1989个人，则这个人a至少认识1989中的1327个人，定义为friend1，还剩下1989-1327=662个人不认识定义为strenge1。如果在a认识的1327个人中又存在一个人b，他也认识的人也为1327个，因为friend1中只有662个人所以，b认识的人中一定有至少两个在a认识的friend1里，所以至少有4位彼此是朋友！3．43边长为1的等边三角形内任意5个点，至少有两点，其间距离最多为1/2。解：把边长为1的等边三角形分成四个边长为1/2的等边三角形，如图所示则根据鸽巢原理，这五点中必有两点落在同一个边长为1/2的等边三角形中。而边长为1/2的等边三角形中任意两点间的距离都小于1/2。3—45边长为1的正方形内任取9点,试证存在3个不同的点,由此构成的三角形面积不超过1/8.解:如下图.把1×1的正方形分成四个(1/2)× (1/2)的正方形,根据鸽巢原理,((10-1)/4)+1=3,则这10点中必有三点落在同一个小正方形中,而小正方形内的任三点构成三角形面积最大为1/8.所以构成的三角形面积不超过1/8.3.46：给任何5个整数，试证必存在3个数的和被3除尽。解：所有整数可分为3类，mod3=0,mod3=1,mod3=2，分别标记为A,B,C.如果在这五个数中，任何一类的个数大于等于3，那么在这个类中任取三个元素，它们的和一定能被三整除。如果没有任何一类的个数大于等于3，那么只能是2，2，1的组合.如果A类元素只有一个，那么B类，C类各有2个元素。A，B，C各类各取一个，它们的和一定能被三整除。如果B类元素只有一个，那么A类，C类各有2个元素。A，B，C各类各取一个，它们的和一定能被三整除。如果C类元素只有一个，那么A类，B类各有2个元素。A，B，C各类各取一个，它们的和一定能被三整除。3.47A是n+1个数的集合，试证其中必存在两个数，它们的差被n除尽。 解：如果n+1个元素有相同的值，那么命题自然得证 如果每两个元素之间都有不同的值，那么如下假设a为集合中最小的数，现在有值为0，1，2，…，n-1个盒子，现在对于A中的每个数进行如下运算 K=把放入K值对应的盒子当中，所以根据鸽巢原理，必有一个盒子内有两个元素，不妨设为和，因为他们满足=，所以和满足，所以一定存在两个元素的差被n除尽3.48A={a1，a2，…，a2k+1}，k≥1，ai是正整数，k=1，2，…，2k+1，试证A的任意排列：恒有为偶数证明：另n=|A|=2k+1，则A中奇数和偶数个数不相等。如果中全为“奇数-偶数”或“偶数-奇数”的形式，则A中奇数和偶数个数相等，与前面矛盾。顾中必有“奇数-奇数”或“偶数-偶数”的形式，即为偶数。3.49A是中任意n+1个数，试证明至少存在一对，使下面结果成立：解：假设取出任意n+1个数，将它们每一个都拆成2的几次幂乘以一个奇数的形式；那么一共能拆出n+1个奇数（每个数对应一个奇数）。然而，在上述A集合之中，2n个元素一共只有n个奇数。所以根据鸽巢原理，能够得出上述n+1个奇数中至少有两个是相等的。而这两个数必然一个能被另一个整除。—〉得证。×3.51×3.52．空间2n个点，，试证用条线段任意连接这2n个点，必然出现一个三角形，并证明用条线连接，则可能不出现三角形。解：将这2n个点分成两个集合，,，则使得A中每个点都与B中每个点都有一条边相连，总的需要的边数为ab,易知当a=b=n时需要的边数最多且为,又因为总共有条线段，则在集合A,B中一定存在某两个点之间有边，即证必然出现一个三角形。当a=b=n时，用条线段相连时，上述情况则不出现三角形。×3.53三维空间中9个坐标为整数的点，试证在两两相连的线段内，至少有一个坐标为整数的内点。解：三维空间中，任意两坐标为整数的点，若这两点相连的线段内不存在坐标为整数的内点，则对于x,y,z这三个坐标轴，这两点至少在一个坐标上的差值正好是1。那么，在这9个坐标为整数的点中，任取一点，与这个点的三个坐标中，存在差值正好是1的共有7类，即：与x轴差值正好是1，与y轴差值正好是1，与z轴差值正好是1，与x,y轴差值都是1，与x,z轴差值都是1，与y,z轴差值都是1，与x,y,z轴差值都是1。那么，对于剩下的8个点，若存在一点a不满足这7种情况，那么a点与这个点相连的线段内必有一个坐标为整数的内点。若剩下的8个点都属于这7种情况之一，那么，运用鸽巢原理，则至少存在两个点属于这7种情况中的同一个情况，那么，这两点中必存在一个坐标为整数的内点。二维空间的（x,y）点的坐标x和y都是整数的点称为格点。任意5个格点的集合A，试证A中至少存在两点，它们的中点也是格点。解：集合A={（,）,(,),(,),(,),(,)},均为整数（,）有四种情况，分别是：奇偶，偶奇，奇奇，偶偶。问题就转化为（，）也为整数。即（,）也为整数5个点，4种情况，根据鸽巢原理必有两个点是相同类型又因为奇+奇=偶，偶+偶=奇，故得证。×3.55令A为从等差数列1，4，7，10…100中选择20个不同的数，试证其中至少存在两个数，他们的和为100.题解：假设20个数中任意两个数的和都不为104an+bm≠104即1+(n-1)3+1+(m-1)3≠104即n+m≠341≤n≤20,1≤m≤202≤n+m≤40即n+m可以为34即矛盾，成立。×3.56平面上6个点，不存在3点共一条直线，其中必存在3点构成一个三角形，有一内角小于30°。题解：这道题是Ramsey数的变形，三点构成一个三角，某个点对应的这个角度>30或<=30就相当于三个人之间是相互认识或是相互不认识.反证法:假设题设不成立.即所有构成的角度都>30度;假设1分别与23456(不妨设顺时针围绕在1周围)的夹角都>30度,则总度数>150;合理;继续:三角形124中1点的度数>60;又因为2>30且4>30则三内角和>180,矛盾,得证!×3.57n是大于等于3的整数，则下列数的集合{2-1，-1，-1，……，-1}中存在一数被n除进。答：此题出错，A集合中不满足被2的倍数的n除尽，例如n=6>3,但不满足题设。×3.58n个人的集体，试证存在两个人，在余下的n-2个人中，至少有个要么与二人互相认识，要么与这两个人均不认识。×3.59．,A和B是S的不相交子集。若A和B的元素之和不等，即属于A的元素之和不等于属于B的元素之和，试证×3.60下列m*n矩阵的元素是实数每行的最大元素与最小元素之差不超过d>0.对梅列元素重新排列成递减序列，即最大元素在第一行，最小元素在第m行，是证明经过重新排列后的矩阵，每行最大元素与最小元素之差仍然不超过d。3.61n个单位各派两名代表出席一个会议，2n位代表围着一圆桌坐下，试问各单位的代表并排坐着的方案有多少？各单位的两人互不相邻的方案数又等于多少？解：(1).（2）.令第i个单位的代表相邻而坐的集合，===故各单位的两人互不相邻的方案数：3.62一层书架有m层，分别放置m类不同种类的书，每层n册，现将书架上的图书全部取出清理，清理过程中要求不打乱所在的类别。试问：m类书全不在各自原来层的方案数有多少？解：m个对象的错排问题：每层的n本书都不在原来的位置上的方案数等于多少？解：如果某类书不在原来的层上，则对该层的n本书全排列即可；如果某类书在原来的层上，则对n本书进行错排即可：m层书都不在原来层次，每层n本书也不在原来位置上的方案数？解：3.63(m+1)行mm+12+1证：每列有(m+1)行，只有m种颜色，故一列中必有两格同色．同色的２个格子的行号有m+12种取法．有m种色，故有mm+12种同色模式，现有3.64两名教师分别对6名学生进行面试（每位教师各负责一门课），每名学生面试时间固定，试问共有多少种面试的顺序。 解：先对第一门课的学生进行排列，然后再排第二门课的顺序，那么第二门课程的排序就将成为一个错排问题，对每一个第一门课的排列，都对应一系列的错排，即如下第一门课的顺序有6!种；

第二门课的顺序有（根据例3-10，错排问题）：D6＝6!((1/2!)－(1/3!)＋(1/4!)－(1/5!)＋(1/6!))＝265;

故总顺序有6!×265种．3.65：X={0，1，2，3……9，10}从X中任意取7个元素，则其中必有两个元素之和等于10.解：|X|=11，分为6组{0,10},{1,9},{2,8},{3,7},{4,6},{5}.从这11个数中去7