组合数学课件第三章习题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个点试证其中至少有两点 期间距离小于 解 第三章习题解答 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 n个球放到m个盒子中去 试证其中必有两个盒子有相同的球数 解 第三章习题解答 12 n各单位各派两名代表去出席一会议 位代表围一圆桌坐下 试问 1 各单位代表并排坐着的方案是多少 2 各单位的两人互不相邻的方案数又是多少 解 第三章习题解答 13 一书架有m层 分别放置m类不同种类的书 每层n册 先将书架上的图书全部取出清理 清理过程要求不打乱所有的类别 试问 1 m类书全不在各自原来层次上的方案数有多少 2 每层的n本书都不在原来位置上的方案数等于多少 3 m层书都不在原来层次 每层n本书也不在原来位置上的方案数又有多少 解 第三章习题解答 14 行列的格子同种颜色着色 每格赵一种颜色 其中必有一个4角同色的矩形 解 第三章习题解答 15 两名教师分别对6名学生同时进行两门课程的面试 每名教师各管一门课程 每名学生每门面试的时间都是半个小时 共有多少不同的面试顺序 解 第三章习题解答 16 在平面直角坐标系中至少任取多少个整点 两个坐标系都是整数 才能保证其中存在3个构成三角形 包含3点在一条直线上 的面积是整数 可以为0 解 第三章习题解答 17 在平面直角坐标系中至少任取去多少个整点才能保证存在3个点构成的三角形的重心是整点 解 第三章习题解答 在平面直角坐标系中任取4N 3个整点 保证存在N个点的重心是整点 N 2a3b 第三章习题解答 1 解设Ai为甲与第i个朋友相遇的会议集 i 1 6 则 Ai 12 6 4 3 2 28故甲参加会议数为28 5 33 题目 61 62 63 64 65 66 第三章习题解答 解设A3 被3整除的数的集合A5 被5整除的数的集合A7 被7整除的数的集合所以 A7 A5 A3 A3 A5 A7 A5 A3 33 4 29 题目 5003 5 5003 5 7 第三章习题解答 3解每个人的朋友数只能取0 1 n 1 但若有人的朋友数为0 即此人和其他人都不认识 则其他人的最大取数不超过n 2 故这n个人的朋友数的实际取数只有n 1种可能 所以至少有 人的朋友数相等 题目 nn 1 第三章习题解答 4解 a 从n个元素中取k个元的组合 总含指定的m个元的组合数为 设这m个元为a1 a2 am Ai为不含ai的组合 子集 i 1 m Ai Ai1 Ai2 Ail Ai 1 Aij 1 n 1k n lk n mn k nk m i 1 m l 1 l l j 1 i1 il m l l mk n lk m l 0 n mk m n mn k 第三章习题解答 b 令k n m l个相同的球放入k个不同的盒子里 每盒不空的方案数为 设Ai为第i个盒子为空的方案集 i 1 2 k Ai Ais Ai 1 Ais 1 l 1k 1 k 1 l 1l l 1k 1 k j l 1l k l 1l i1 ij k j j s 1 j s 1 k i 1 k j 1 j k j 0 j kj k j l 1l 第三章习题解答 l个相同的球放入n个不同的盒子里 指定的m个盒子为空 其他盒子不空的方案数为 l 1n m 1 第三章习题解答 c 设Ai为m l个元中取m i个 含特定元素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 N0 N1 N2 1 Nl 题目 m lm i m l 1m i 1 m l 1m i m l 1m i l 第三章习题解答 5证显然 每列中必有两数字相同 共有 种模式 有 或 两种选择 故共有 2种选择 2 6 现有7列 2 即必有 列在相同的两行选择相同的数字 即有一矩形 四角的数字相等 题目 32 32 32 76 第三章习题解答 6证把 正方形分成四个 的正方形 如下图 12 12 则这 点中必有两点落在同一个小正方形内 而小正方形内的任两点的距离都小于 2 12 题目 第三章习题解答 7证把边长为 的三角形分成四个边长为 的三角形 如下图 12 则这 点中必有两点落在同一个小三角形中 题目 第三章习题解答 8证整数的个位数的可能取值为 共 种可能 11个整数中必有 个数的个位数相同 即这两个数之差能被 整除 题目 第三章习题解答 证用反证法 设存在划分P1 P2 P3 P4 P5 1 326 Pi中无数是两数只差 66 则有一Pi中至少有66个数 A a1 a66 a1 a2 a66 以下按书上174页的例题证明可得 题目 3265 第三章习题解答 10解按题意可得如下的带禁区的棋盘其中有阴影的表示禁区 ABC 禁区的棋子多项式为 R R R 1 x 1 3x x 1 4x 4x x 故方案数 3 4 2 4 1 1 0 1 2 2 3 题目 第三章习题解答 11证设m个盒子的球的个数是a1 am 各不相等 且有0 a1 a2 am 则有a2 1 am m 1 故 ai 1 2 m 1 m m 1 与n m m 1 相矛盾 所以必有两个盒子的球数相等 12 12 i 1 m 题目 第三章习题解答 12解 1 方案数 n 1 2 n 2 设第i个单位的代表相邻的方案集为Ai i 1 2 n Ai 1 Ai 1 2n k 1 2 n n n i 1 k 0 k 0 I n k i I nk k k k 题目 第三章习题解答 13解令Dn n 1 1 方案数 Dm n 11 12 1n m 2 Dk n Dn mk k m k k 0 m 3 DmDn m 题目 第三章习题解答 14证每列有 m 1 行 只有m种颜色 故一列中必有两格同色 同色的 个格子的行号有 种取法 有m种色 故有m 种同色模式 现有m 1列 必有两列的同色模式相同 即由这两列的对应行上有 个格子同色 正好是一个矩形的 个角上的格子 得证 题目 m 12 m 12 m 12 第三章习题解答 15解第一门课的顺序有6 种第二门课的顺序有 D6 6 265古总顺序有6 265种 题目 12 13 14 15 16 第三章习题解答 16解任一点的坐标 a b 只有如下 种可能 奇数 偶数 奇数 奇数 偶数 奇数 偶数 偶数 因而5个点中必有两个点模2的格式一样 设2 x1 x2 2 y1 y2 即x1 x2 2ky1 y2 l 则三角形面积S 111x1x2x3y1y2y3 011x1 x2x2x3y1 y2y2y3 12 12 011kx2x3ly2y3 是整数 题目 第三章习题解答 17解设 x y 是整点 每个分量模3后有如下表的结果 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2 若有 个点模 后的结果落在上表中的同一格中 则这 个点的重心是整点 第三章习题解答 若有 点占满一行 则 点重心是整点 有 点占满一列 则 点重心是整点 若存在一组均匀分布 则有3点重心是整点 由上表可知 若只有8个点 也不能保证有 点的重心是整点 因为若每个格子都有 点 则只占有 个格子 无法保证上面的要求 下面假设存在 个点 其中任 点的重心都不是整点 第三章习题解答 则这9个点 至