《组合数学课件第三章习题1.ppt》由会员分享，可在线阅读，更多相关《组合数学课件第三章习题1.ppt（42页珍藏版）》请在三一文库上搜索。
1、1.某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议,解：.,第三章习题解答,2.求从1到500的整数中被3和5整除但不被7整除的数的个数.,解：.,第三章习题解答,3. n代表参加会议，试证其中至少有2人各自的朋友数相等。,解：.,第三章习题解答,4. 试给出下列等式的组合意义,第三章习题解答,解：.,第三章习题解答,5.设有3个7位的2进制数,解：.,试证存在整数i和j， 使得下列之一必然成立。,第三章习题解答,6. 在边长为1的正方形内任取5个点试证
2、其中至少有两点，期间距离小于,解：.,第三章习题解答,7.在边长为1的等边三角形内任取5个 点试证其中至少有两点，期间距离小于,解：.,第三章习题解答,8. 任取11个整数，求证其中至少有两个数它们的差是10的倍数。,解：.,第三章习题解答,9. 把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍。,解：.,第三章习题解答,10. A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）,解：.,第三章习题解答,11.
3、 n个球放到m个盒子中去， 试证其中必有两个盒子有相同的球数。,解：.,第三章习题解答,12. n各单位各派两名代表去出席一会议。 位代表围一圆桌坐下。试问： （1）各单位代表并排坐着的方案是多少？ （2）各单位的两人互不相邻的方案数又是多少？,解：.,第三章习题解答,13. 一书架有m层，分别放置m类不同种类的书，每层n册。先将书架上的图书全部取出清理。清理过程要求不打乱所有的类别。试问 （1）m类书全不在各自原来层次上的方案数有多少？ （2）每层的n本书都不在原来位置上的方案数等于多少？ （3）m层书都不在原来层次，每层n本书也不在原来位置上的方案数又有多少？,解：.,第三章习题解答,14
4、. 行 列 的格子同 种颜色着色，每格赵一种颜色，其中必有一个4角同色的矩形。,解：.,第三章习题解答,15. 两名教师分别对6名学生同时进行两门课程的面试（每名教师各管一门课程）每名学生每门面试的时间都是半个小时，共有多少不同的面试顺序？,解：.,第三章习题解答,16. 在平面直角坐标系中至少任取多少个整点（两个坐标系都是整数）才能保证其中存在3个构成三角形（包含3点在一条直线上）的面积是整数（可以为0）,解：.,第三章习题解答,17. 在平面直角坐标系中至少任取去多少个整点才能保证存在3个点构成的三角形的重心是整点？,解：.,第三章习题解答,在平面直角坐标系中任取4N-3个整点， 保证存在
5、N个点的重心是整点。 N=2a3b,第三章习题解答,1解 设Ai为甲与第i个朋友相遇的会议 集，i1，6则 Ai12 ( ) 6 ( )4 ( ) 3 ( )2 ( )( ) 28 故甲参加会议数为 28533 （题目）,6 1,6 2,6 3,6 4,6 5,6 6,第三章习题解答, 解 设A3：被3整除的数的集合 A5：被5整除的数的集合 A7：被7整除的数的集合 所以 A7A5A3 A3A5 A7A5A3 33429 （题目）,500 35,500 357,第三章习题解答,3 解 每个人的朋友数只能取0，1， n1但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超 过
6、n2故这n个人的朋友数的实际取数只 有n1种可能 ，所以至少有人 的朋友数相等 （题目）,n n1,第三章习题解答,4 解 ( a ) 从n个元素中取k个元的组合， 总含指定的m个元的组合数为( )=( ) 设这m个元为a1，a2，am，Ai为不含ai的 组合(子集)，i=1，m Ai= ( ) Ai1 Ai2 Ail( ) ( ) Ai ( ) + (1) Aij (1) ( ) ( ),n1 k,n l k,nm nk,n k,m,i=1,m,l=1,l,l,j=1,i1,il(m , l),l,m k,n l k,m,l=0,nm km,nm nk,第三章习题解答,( b )令knml个
7、相同的球放入k个不同 的盒子里每盒不空的方案数为( ) 设Ai为第i个盒子为空的方案集，i=1,2,k. | Ai |= ( ), | Ais | = ( ) ( )= | Ai |= ( ) + (1) Ais (1) ( ) ( ),l1 k1,k1+l1 l,l1 k1,kj+l1 l,k+l1 l,i1,ij(k , j),j,s=1,j,s=1,k,i=1,k,j=1,j,k,j=0,j,k j,kj+l1 l,第三章习题解答,l个相同的球放入n个不同的盒子里，指定 的m个盒子为空，其他盒子不空的方案数 为( ),l1 nm1,第三章习题解答,( c ) 设Ai为m+l个元中取m+i
8、个，含特定元素 a的方案集；Ni为m+l个元中取m+i个的方案 数则： Ni( ) | Ai |=( )， | Ai |=( ) | Ai+1 |= | Ai |=( ) | Ai |= Ni| Ai | i=0,1, ,l | A0 |=N0 | A0 | =N0| A1 |=N0(N1|A1| =N0N1+N2+(1) Nl (题目）,m+l m+ i,m+l1 m+ i1,m+l1 m+ i,m+l1 m+ i,l,第三章习题解答,5 证 显然，每列中必有两数字相同，共 有( )种模式，有或两种选择故共 有( )2种选择 ( )2=6现有7列， = 2即必有列在相同的两行选择相 同的数字
9、，即有一矩形，四角的数字相等 （题目）,3 2,3 2,3 2,7 6,第三章习题解答,6 证 把正方形分成四个的 正方形如下图：,1 2,1 2,则这点中必有两点落在同 一个小正方形内而小正方 形内的任两点的距离都小于 2,1 2,（题目）,第三章习题解答,7 证 把边长为的三角形分成四个边长 为的三角形，如下图：,1 2,则这点中必有两点落在 同一个小三角形中,（题目）,第三章习题解答,8 证 整数的个位数的可能取值为， ，共种可能11个整数中必有 个数的个位数相同，即这两个数之差能 被整除,（题目）,第三章习题解答, 证 用反证法。设存在划分 P1P2P3P4P51，326，Pi中无数
10、是两数只差 66，则有一Pi中至少有66个数， A a1 ,a66 ，a1a2a66 ， 以下按书上174页的例题证明可得(题目),326 5,第三章习题解答,10 解 按题意可得如下的带禁区的棋盘 其中有阴影的表示禁区,A B C,禁区的棋子多项式为：,R( ) =R( ) R( ) =(1+x)(1+3x+x ) =1+4x+4x + x,故方案数3!42!+4 1!1 0!1,2,2,3,（题目）,第三章习题解答,11 证 设m个盒子的球的个数是a1,am， 各不相等，且有0a1a2am则有 a21、amm1，故 ai1+2+m1m(m1) 与nm(m1)相矛盾！ 所以必有两个盒子的球数
11、相等,1 2,1 2,i=1,m,（题目）,第三章习题解答,12 解 ( 1 ) 方案数(n1)！2,n,( 2 ) 设第i个单位的代表相邻的方案集为 Ai，i1,2 , ,n | Ai | (1 ) | Ai | (1) ( ) (2nk1)! 2,n,n,n,i=1,k=0,k=0,I( n ,k),iI,n k,k,k,k,（题目）,第三章习题解答,13 解 令Dnn!(1 + ) ( 1 )方案数Dm( n! ),1 1!,1 2!,1 n!,m,( 2 ) ( ) Dk (n!) Dn,m k,k,mk,k=0,m,( 3 ) Dm Dn,m,（题目）,第三章习题解答,14 证 每列
12、有(m+1)行，只有m种颜色，故 一列中必有两格同色同色的个格子的行 号有( )种取法有m种色，故有m( ) 种同色模式，现有m( ) +1列，必有两列 的同色模式相同即由这两列的对应行上有 个格子同色，正好是一个矩形的个角上 的格子得证 (题目),m+1 2,m+1 2,m+1 2,第三章习题解答,15 解 第一门课的顺序有6!种 第二门课的顺序有： D66! ( )265 古总顺序有6!265种 （题目）,1 2!,1 3!,1 4!,1 5!,1 6!,第三章习题解答,16 解 任一点的坐标（a , b）只有如下 种可能：(奇数，偶数)、(奇数，奇数)、 (偶数，奇数)、(偶数，偶数)。
13、因而5个点 中必有两个点模2的格式一样设 2(x1x2)，2(y1y2)即x1x22k y1y2l，则三角形面积 S,1 1 1 x1 x2 x3 y1 y2 y3,0 1 1 x1 x2 x2 x3 y1 y2 y2 y3,1 2,1 2,0 1 1 k x2 x3 l y2 y3,是整数,（题目）,第三章习题解答,17 解 设(x，y)是整点，每个分量模3后有 如下表的结果：,(0，0) (0，1) (0，2),(1，0) (1，1) (1，2),(2，0) (2，1) (2，2),若有个点模后的结果落在上表中的同 一格中，则这个点的重心是整点,第三章习题解答,若有点占满一行，则点重心是整
14、点； 有点占满一列，则点重心是整点； 若存在一组均匀分布，则有3点重心是整点 由上表可知，若只有8个点，也不能保证有 点的重心是整点（因为若每个格子都有 点，则只占有个格子，无法保证上面的 要求）,下面假设存在个点，其中任点的 重心都不是整点,第三章习题解答,则这9个点，至少占有 5个格子（因 为每格中最多有2个点，否则有3个点的重 心为整点），每行最多有格，又=3 所以每行都有点 同理，每列都有点,9 2,5 2,不妨设第一行2点，第二行2点，第三行1点 前2 行有两种模式：,或,这样第三行的点无论在哪一列都构成占满,第三章习题解答,一列或构成一组均匀分布满足前面说的 三点重心是整点的情况,故 9个点能保证其中存在个点的重心是 整点 （题目）,第三章习题解答,