《组合数学第三章习题解答》由会员分享，可在线阅读，更多相关《组合数学第三章习题解答（60页珍藏版）》请在金锄头文库上搜索。
1、第三章习题,3.1 某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议？,1解 设Ai为甲与第i个朋友相遇的会议集，i1，6则,共33次会议,2.求从1到500的整数中被3和5整除但不被7整除的数的个数.,解 设A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合,3. n代表参加会议，试证其中至少有2人各自的朋友数相等。,解：每个人的朋友数只能取0，1，n1以下分两种情况讨论。,若有人的朋友数为0，即此人和其他人都不认识
2、，则其他n-1个人的最大取数不超过n2必有两人认识人数相等。 若没有人的朋友数为0，则这n个人的朋友数的实际取数只有n1种可能所以至少有人的朋友数相等。,3.4 试给下列等式以组合意义,(a)从n个元素中取k个元素的组合，总含m个指定的元素的组合 数为C(n-m,k-m),设这m个元素为a1,a2,.,am.Ai为不含ai的组 合，i=1,2,.,m,( b )令knml个相同的球放入k个不同的盒子里每盒不空的方案数为C(n-m+l-n+m-1,l-n+m)=C(l-1,n-m-1)。设Ai为第i个盒子为空的方案集，i=1,2,k.,l个相同的球放入n个不同的盒子里，指定的m个盒子为空，其他盒
3、子不空的方案数为C(l-1,n-m-1),( c ) 设Ai为m+l个元素中取m+i个，含特定元素a的方案集；Ni为m+l个元素中取m+i个的方案数则：,3.5 设有3个7位的二进制数a1 a2 a3 a4 a5 a6 a7,b1 b2 b3 b4 b5 b6 b7,c1 c2 c3 c4 c5 c6 c7, 试证存在整数i和j，1ij7，使得下列之一必然成立： ai=aj=bi=bj,ai=aj=ci=cj,bi=bj=ci=cj,证明：,显然，每列中必有两数字相同，共有C(3,2)种模式，有或两种选择故共有C(3,2)2种选择。C(3,2)2=6现有7列，即必有列在相同的两行选择相同的数字
4、，即有一矩形，四角的数字相等,3.6 在边长为1的正方形内任取5点，试证其中至少有两点，其间 距离小于,证 把正方形分成四个相等的小正 方形如下图：,则这点中必有两点落在同一个小正方形内而小正方形内的任两点的距离都小于,证把边长为的三角形分成四个边长为的三角形，如下图：,则这点中必有两点落在同一个小三角形中,3.7 在边长为1的等边三角形内任取5点，试证至少有两点距离 小于1/2,3.8 任取11个数，求证其中至少有两个数它们的差是10的倍数。,证明：一个数是不是10的倍数取决于这个数的个位数是不是0，是 0就是10的倍数。 一个数的个位数只可能是0,1,.,9十个数，任取11个数，其中必 有
5、两个个位数相同，那么这两个数的差的个位数必然是0。,3.9 把从1到326的326个整数任意分为5个部分，试证其中有一部 分至少有一个数是某两个数之和，或是另一个数的两倍。,证明：用反证法，设存在划分。,设这66个元素为a1a2a3.a66,构造b1=a2-a1, b2=a3-a1, b65=a66-a1,令B=b1,b2,b65,这65个元素属于1到326，如果这65个元素有任何一个属于P1， 则定理得证。,否则：,(2)因为。,因此至少有一个集合含至少B中17个元素，设这个集合为p2。,设这6个元素为：,构造：,设C=c1,c2,c16,否则：,(3)因为。,因此至少有一个集合含至少C中6
6、个元素，设这个集合为p3。,设这11个元素为：,构造：,如果：,则定理得证,同样可证明d1和d2既可表示成p1中元素之差，也可表示成p2p3 中元素之差，,设D=d1,d2,d5,否则：,(3)因为。,因此至少有一个集合含至少D中3个元素，设这个集合为p4。,设这3个元素为：,构造：,如果：,则定理得证,同样可证明ei既可表示成p1中元素之差，也可表示成p2p3p4 中元素之差，,否则：,同样可证明e2-e1既可表示成p1中数之差，也可表示成p2p3p4中数之差。 e2-e1是1到326中的数，设f=d2-d1,因此：1到326的326个整数任意分成5部分，其中必有一部分其中有一个数是另两个数
7、之差，设ai=aj-ah,那么反过来： aj=ai+ah,构造：,3.10 A,B,C三种材料用作产品I,II,III的原料，但要求I禁止 用B和C作原料，II不能用B作原料，III不允许用A作原料，问 有多少种安排方案？,解 按题意可得如下的带禁区的棋盘其中有阴影的表示禁区,A B C,禁区的棋子多项式为：,R( )=R( ) R( )=(1+x)(1+3x+x2 )=1+4x+4x2 + x3,故方案数3!42!+4 1!1 0!1,3.11,n个球放到m个盒子中去，nm(m-1)/2,试证其中必有两个盒 子有相同的球数。,证明：用反证法,假如没有两个盒子的球数相同，那么m个盒子中最少需要
8、 0,1,2,.(m-1)共m(m-1)/2,因此必有两个盒子有相同的球数。,3.12,一年级有100名学生参加中文、英文和数学的考试，其中92 人通过中文考试，75人通过英语考试，65人通过数学考试；其中 65人通过中英文考试，54人通过中文和数学考试，45人通过英语 和数学考试，求通过三门学科考试的学生数？,3.13,试证,证明(a),3.15,N=1,2,.,120,求其中被2,3,5,7,m个数除尽的数的数目， m=0,1,2,3,4。求不超过120的素数的数目。,解 设A2：被2整除的数的集合A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合,素数为27-1+4
9、=30,3.16,求正整数n的数目，n除尽1040，2030中至少一个数。,解：,设A1为能除尽1040的数，A2为能除尽2030的数，,3.17,求正整数n的数目，n除尽1060，2050，3040至少一个数。,解：,3.18,求下列集合中不是n2，n3，形式的数的数目。,解：,3.19,求下列集合中是4的倍数，但不是100的倍数的数的数目。,3.20,在由a,a,a,b,b,b,c,c,c组成的排列中，求满足下列条件 的排列数， (a)不存在相邻三元素相同。 (b)相邻两元素不相同。,解a,设A1为至少存在三元素aaa相邻的排列集。A2为至少存在三元素bbb相邻的排列集。A3为至少存在三元
10、素ccc相邻的排列集。,解b,设A1为至少存在二元素aa相邻的排列集。A2为至少存在二元素bb相邻的排列集。A3为至少存在二元素cc相邻的排列集。,3.21,求从O(0,0)点到(8,4)点的路径数，已知(2,1)到(4,1)的线 路， (3,1)到(3,2)的线路被封锁。,解,设过(2,1)到(4,1)的线路的路径数是A1过(3,1)到(3,2)的线路的路径数是A2。,3.22,求满足条件x1+x2+x3=20,3x19,0x28,7x317, 的整数解数目。,解,设A1是满足x13的解，A2是满足x110的解，A3是满足x29的解，A4是满足x37的解，A5是满足x318的解，,A1的解等
11、价于(x1+4)+x2+x3=20,其解的数目为C(3+16-1,16),A2的解等价于(x1+10)+x2+x3=20,其解的数目为C(3+10-1,10),A3的解等价于x1+(x2+9)+x3=20,其解的数目为C(3+11-1,11),A4的解等价于x1+x2+(x3+7)=20,其解的数目为C(3+13-1,13),A5的解等价于x1+x2+(x3+18)=20,其解的数目为C(3+2-1,2),A1交A4的解等价于(x1+4)+x2+(x3+7)=20, 其解的数目为C(3+9-1,9),A1交A4交A2的解等价于(x1+10)+x2+(x3+7)=20, 其解的数目为C(3+3-
12、1,3),A1交A4交A3的解等价于(x1+3)+(x2+9)+(x3+7)=20, 其解的数目为C(3+1-1,1),A1交A4交A5的解等价于(x1+3)+x2+(x3+18)=20, 其解的数目为0,A1交A4交A2交A3的解等价于(x1+10)+(x2+9)+(x3+7)=20, 其解的数目为0,A1交A4交A2交A5的解等价于(x1+10)+x2+(x3+18)=20, 其解的数目为0,A1交A4交A3交A5的解等价于(x1+3)+(x2+9)+(x3+18)=20, 其解的数目为0,A1交A4交A2交A3交A5的解等价于(x1+10)+(x2+9)+(x3+18)=20, 其解的数
13、目为0,3.25,试证满足下列条件x1+.+xn=r,0xik 的整数解数目为。,设Ai是满足xik+1的整数解集合。,3.26,试证满足下列条件x1+.+xn=r,1xik 的整数解数目为。,设Ai是满足xik+1的整数解集合。,3.27,求n对夫妻排成一行，夫妻不相邻的排列数。,设Ai是第i对夫妻排在一起的排列集。,3.28,p,qN,p是奇数，现有pq个珠子，着q种颜色，每种颜色有p个珠子。假定相同颜色的珠子无区别，试分别求满足以下条件的珠子的排列数。 (a)同颜色的珠子在一起 (b)同颜色的珠子处于不同的块 (c)同颜色的珠子最多在两个块,解a,解b,3.29,将r个相同的球放进n个有
14、标志的盒子，无一空盒，求方案数。,解,两种算法：1,解2，设Ai为第i盒为空，其它盒任意的方案数。,3.30,由28题，两种算法应相等。,3.31,设B是A的子集。,求A的子集包含B的子集的数目，设子集的元素数目为r,mrn。,解：设B中元素为a1,a2,.,am。设A1是不包含a1的A的r个元素的子集数目。A2是不包含a2的A的r个元素的子集数目。.Am是不包含am的A的r个元素的子集数目。,另外一种算法，先从A中取出B的m个元素，然后在从剩余的n-m个元素中取出r-m,共C(n-m,r-m)=C(n-m,n-r),3.32,综合3.31两种情况可得3.32,3.44,单位圆周上任意n+1个
15、不相同的点至少存在两点，其间距 离不超过：,把圆周分成n等分，每份中的距离不超过,3.45,边长为1的正方形内任取9点，试证存在3个不同的点，由此 构成的三角形面积不超过1/8,解,将边长为1的正方形等分成四部分，由鸽鸽巢原理，必有 三点落在一个小正方形内，这三点形成的三角形的面积不超过 1/8,3.47,A是n+1个数的集合，试证其中必存在两个数，它们的差被 n除尽。,解,n+1个数除以n的余数为0,1,2,.,n-1。若有两个以上余数为 零，那么这两个数就是答案，否则，至少有n个数的余数非零， 根据鸽巢原理，必有两个余数相同，这两个数便是答案。,3.48,A=a1,a2,.,a2k+1,k
16、1,ai是正整数，k=1,2,.,2k+1, 试证A的任意排列：,恒有,为偶数,证明：A有2k+1个数，因此A中必有不少于k+1个奇数或不少于 k+1个偶数。,证明：设A有k+1个奇数，那么：,也有k+1个奇数。,共有2k+1组，其中有2k+2个奇数,因此必有两个奇数在一组。,有k+1个偶数时情况相同。,3.49,A是1,2,.,2n中任意n+1个数，试证至少存在一对a,bA 使下面结果成立： ab,书中例题,3.50,A是1,2,.,2n中任意n+1个数，试证至少存在一对a,bA 使得a与b互素。,从A中任意取n+1个数，必有两个数相邻，相邻数互素,3.51,A是由13个互不相等的实数组成的集合，则至少存在一对 x,y属于A，使,
