组合数学第三章习题解答.ppt

第三章习题 3 1某甲参加一种会议 会上有6位朋友 某甲和其中每人在会上各相遇12次 每二人各相遇6次 每三人各相遇4次 每四人各相遇3次 每五人各相遇2次 每六人各相遇一次 1人也没有遇见的有5次 问某甲共参加了几次会议 1 解设Ai为甲与第i个朋友相遇的会议集 i 1 6 则 共33次会议 2 求从1到500的整数中被3和5整除但不被7整除的数的个数 解设A3 被3整除的数的集合A5 被5整除的数的集合A7 被7整除的数的集合 3 n代表参加会议 试证其中至少有2人各自的朋友数相等 解 每个人的朋友数只能取0 1 n 1 以下分两种情况讨论 若有人的朋友数为0 即此人和其他人都不认识 则其他n 1个人的最大取数不超过n 2 必有两人认识人数相等 若没有人的朋友数为0 则这n个人的朋友数的实际取数只有n 1种可能 所以至少有 人的朋友数相等 3 4试给下列等式以组合意义 a 从n个元素中取k个元素的组合 总含m个指定的元素的组合数为C n m k m 设这m个元素为a1 a2 am Ai为不含ai的组合 i 1 2 m b 令k n m l个相同的球放入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个盒子为空 其他盒子不空的方案数为C l 1 n m 1 c 设Ai为m l个元素中取m i个 含特定元素a的方案集 Ni为m l个元素中取m i个的方案数 则 3 5设有3个7位的二进制数a1a2a3a4a5a6a7 b1b2b3b4b5b6b7 c1c2c3c4c5c6c7 试证存在整数i和j 1 i j 7 使得下列之一必然成立 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列 即必有 列在相同的两行选择相同的数字 即有一矩形 四角的数字相等 3 6在边长为1的正方形内任取5点 试证其中至少有两点 其间距离小于 证把 正方形分成四个相等的小正方形 如下图 则这 点中必有两点落在同一个小正方形内 而小正方形内的任两点的距离都小于 证把边长为 的三角形分成四个边长为 的三角形 如下图 则这 点中必有两点落在同一个小三角形中 3 7在边长为1的等边三角形内任取5点 试证至少有两点距离小于1 2 3 8任取11个数 求证其中至少有两个数它们的差是10的倍数 证明 一个数是不是10的倍数取决于这个数的个位数是不是0 是0就是10的倍数 一个数的个位数只可能是0 1 9十个数 任取11个数 其中必有两个个位数相同 那么这两个数的差的个位数必然是0 3 9把从1到326的326个整数任意分为5个部分 试证其中有一部分至少有一个数是某两个数之和 或是另一个数的两倍 证明 用反证法 设存在划分 设这66个元素为a1 a2 a3 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个元素 设这个集合为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部分 其中必有一部分其中有一个数是另两个数之差 设ai aj ah 那么反过来 aj ai ah 构造 3 10A B C三种材料用作产品I II III的原料 但要求I禁止用B和C作原料 II不能用B作原料 III不允许用A作原料 问有多少种安排方案 解按题意可得如下的带禁区的棋盘其中有阴影的表示禁区 ABC 禁区的棋子多项式为 R R R 1 x 1 3x x2 1 4x 4x2 x3 故方案数 3 4 2 4 1 1 0 1 3 11 n个球放到m个盒子中去 n m m 1 2 试证其中必有两个盒子有相同的球数 证明 用反证法 假如没有两个盒子的球数相同 那么m个盒子中最少需要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 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为至少存在三元素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 3 x1 9 0 x2 8 7 x3 17 的整数解数目 解 设A1是满足x1 3的解 A2是满足x1 10的解 A3是满足x2 9的解 A4是满足x3 7的解 A5是满足x3 18的解 A1的解等价于 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 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 其解的数目为0 3 25 试证满足下列条件x1 xn r 0 xi k的整数解数目为 设Ai是满足xi k 1的整数解集合 3 26 试证满足下列条件x1 xn r 1 xi k的整数解数目为 设Ai是满足xi k 1的整数解集合 3 27 求n对夫妻排成一行 夫妻不相邻的排列数 设Ai是第i对夫妻排在一起的排列集 3 28 p q N p是奇数 现有pq个珠子 着q种颜色 每种颜色有p个珠子 假定相同颜色的珠子无区别 试分别求满足以下条件的珠子的排列数 a 同颜色的珠子在一起 b 同颜色的珠子处于不同的块 c 同颜色的珠子最多在两个块 解a 解b 3 29 将r个相同的球放进n个有标志的盒子 无一空盒 求方案数 解 两种算法 1 解2 设Ai为第i盒为空 其它盒任意的方案数 3 30 由28题 两种算法应相等 3 31 设B是A的子集 求A的子集包含B的子集的数目 设子集的元素数目为r m r n 解 设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个不相同的点至少存在两点 其间距离不超过 把圆周分成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 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 b A使下面结果成立 a b 书中例题 3 50 A是 1 2 2n 中任意n 1个数 试证至少存在一对a b A使得a与b互素 从A中任意取n 1个数 必有两个数相邻 相邻数互素 3 51 A是由13个互不相等的实数组成的集合 则至少存在一对x y属于A 使 3 55 令A为从等差数列1 4 7 10 100中任选20个不同的数 试证其中至少存在两个数 它们的和为104 项数是1 100 1 3 34 去掉1和52 共32个项 任取20个不同的数 至少有18个是32项中的数 4 100 7 97 因此至少有两个数落在同一组中 也就是存在两个数它们的和为104 3 56 平面上6个点 不存在3点共一条直线 其中必存在3点构成一个三角形 有一内角小于等于30度 平面上6个点构成一个6边形 其内角和为720度 必有一角不大于120度 从这个角出发到各顶点的连线构成4个角 这4个角度数之和是120度 因此至少有一个角的度数不大于30度 3 57 n是大于等于3的整数 则下列数的集合 2 1 22 1 23 1 2n 1 1 中存在一数被n除尽 首先这是n 1个奇数 假如n是偶数时 不可能 当n 4时 数列为 1 3 7 不可能被n除尽 题 3 61 n个单位各派两名代表出席一个会议 2n位代表围一圆桌坐下问 a 各单位代表并排坐着的方案有多少 b 各单位的两人互不相邻的方案数又等于多少 b 各单位的两人互不相邻的方案数又等于多少 设第i个单位相邻的方案数为Ai 3 62 一书架有m层 分别放置m类不同种类的书 每层n册 现将书架上的图书全部取出清理 清理过程要求不打乱所在的类别 试问 a m类书全不在各自原来层次上的方案数有多少 b 每层的n本书都不在原来位置上的方案数等于多少 c m层书都不在原来层次 每层n本书也不在原来位置上的方案数又是多少 3 64两名教师分别对6名学生进行面试 每位教师各负责一门课 每名学生面试时间固定 试问共有多少种面试的顺序 解第一门课的顺序有6 种第二门课的顺序有 共有6 265 3 65X 0 1 2 9 10 从X中任取7个元素 则其中必有两个元素之和等于10 分成6组 0 10 1 9 4 6 5 从中任取7个数 除去5 还剩6个数 按鸽巢原理 必有两个数落在一组中 而每组两个数之和都是10 3 66每边长为3的等边三角形内取10个点 试证至少有一对点距离小于1 如果把三角形分成9个边长为1的等边三角形 10个点必有至少两个点落在1个小三角形上 其距离必小于1 3 67任取7个不同的正整数 其中至少存在两个整数a和b使得a