组合数学作业1.pdf

SY0721129 刘佳 第 2 章 鸽巢原理 第 2 章 鸽巢原理 2 4 练习题 1 关于本节中的应用 4 证明对于每一个1 2 21 存在连续若干天 在此期间国际象棋大师将恰好 下完局棋 情形21 是在应用 4 中处理的情况 能否判断 存在连续若干天 在此期间国际象棋大 师将恰好下完 22 局棋 k k k 证明 证明 设表示在前 天下棋的总数 i ai 若正好有 则命题得证 若不然 如下 i ak 共有 11 周 每天至少一盘棋 每周下棋不能超过 12 盘 有 且771 i1321 7721 aaa 21 2 1 k 有kkakakak 1321 7721 观察以下 154 个整数 kakakaaaa 77217721 每一个数是 1 到之间的整数 其中k 132153132 k 由鸽巢原理 这 154 个数中至少存在两个相等的数 都不相等 7721 aaa kakaka 7721 都不相等 ji 使 i akaj 即这位国际象棋大师在第 1 j2 j 天总共下了盘棋 ik 综上所述 对于每一个1 2 21 存在连续若干天 在此期间国际象棋大师将恰 好下完局棋 k k 当 22 时 132 154 那么以下 154 个整数 kk 22 22 22 77217721 aaaaaa 在 1 到 154 之间 若这 154 个数都不相同 则它们能取到 1 到 154 的所有整数 必然有一个数是 22 2222 i a771 i 等于 22 的数必然是某个 i a771 i 则在前 天 这位国际象棋大师总共下了 22 盘棋 i 若这 154 个数中存在相同的两个数 都不相等 7721 aaa kakaka 7721 都不相等 第 1 页 w w w k h d a w c o m 课后答案网 SY0721129 刘佳 ji 使 i akaj 即这位国际象棋大师在第 1 j2 j 天总共下了盘棋 ik 综上所述 存在连续若干天 在此期间国际象棋大师将恰好下完 22 局棋 5 证明 如果从 中选择个整数 那么总存在两个整数 它们之间最多差 2 n3 2 1 1 n 证明 证明 把 按顺序三个数字分为一组 共有组 它们是 n3 2 1 n 3 2 1 6 5 4 nnn3 13 23 由鸽巢原理 从组整数中 选择n1 n个整数 至少有两个整数属于同一组 且根据以上分组方式 这两个数之间最多相差 2 即总存在两个整数 它们之间最多差 2 7 证明 对任意给定的 52 个整数 存在其中的两个整数 要么两者的和能被 100 整除 要么两者的差能被 100 整除 证明 证明 任何一个整数的后两位 都是 00 01 02 03 99 之一 现在对所有整数按照后两位数的不同分组如下 00 99 01 98 02 51 49 50 共有 51 个组 由鸽巢原理 对于任意给定的 52 个整数 至少存在两个整数属于同一组 属于同一组的两个数 要么后两位数相同 要么后两位数相加等于 100 若这两个数后两位相同 那么这两者的差能被 100 整除 若这两个数后两位相加等于 100 那么两者的和能被 100 整除 11 一个学生有 37 天用来准备考试 根据过去的经验 她知道她需要不超过 60 小时的学习时间 她还希望 每天至少学习 1 个小时 证明 无论她如何安排她的学习时间 不过 每天都是整数个小时 都存在连 续的若干天 在此期间她恰好学习了 13 个小时 证明 证明 设表示在前 天学习的小时数 i ai 有 37 天准备考试 每天至少学习 1 小时 总学习时间不超过 60 小时 有 且371 i601 3721 aaa 我们还有 7313131314 3721 aaa 观察以下 74 个整数 13 13 13 37213721 aaaaaa 第 2 页 w w w k h d a w c o m 课后答案网 SY0721129 刘佳 每一个数是 1 到 73 之间的整数 由鸽巢原理 这 74 个数中至少存在两个相等的数 都不相等 3721 aaa 13 13 13 3721 aaa 都不相等 ji 使 i a13 j a 即这个学生在第 i天恰好总共学习了 13 个小时 1 j2 j 14 一只袋子装了 100 个苹果 100 个香蕉 100 个橘子和 100 个梨 如果我每分钟从袋子里取出 1 种水果 那么需要多少时间我就能肯定至少已拿出了 1 打相同种类的水果 答 答 45 分钟 下面证明此结论 最坏的情况是 拿了若干次之后 还是不能拿到 1 打相同的水果 但是这个次数的 极限是每种水果拿了 11 个 也就是总共拿了 44 次 因为若拿到第 45 次时 必定有一种 水果拿到了 12 个 1 打 也就是说拿 45 次 肯定至少已拿出了 1 打相同种类的水果 15 证明 对任意个整数 存在两个整数和 1 n 1 a 2 a 1 n a i a j aji 使得 能够被整除 i a j an 证明 证明 任何一个整数被除的余数是以下个数之一 nn 0 1 2 1 n 由鸽巢原理 对于任意个整数 它们除以的余数至少有两个相 同 1 n 1 a 2 a 1 n an 不妨设这两个数为和 i a j aji a a能够被n整除 ij 19 证明 在边长为 1 的等边三角形内任意选择 5 个点 存在 2 个点 其间距离之多为 1 2 证明 证明 把边长为 1 的等边三角形按照右图方式分割为 4 部分 每一部分都是边长为 1 2 的等边三角形 在同一个小三角形中相距最远的 2 个点距离为 1 2 由鸽巢原理 任意选择 5 个点 至少有 2 个点属于同一个小三角形 即 在边长为 1 的等边三角形内任意选择 5 个点 存在 2 个点 其间距离之多为 1 2 证明 在边长为 1 的等边三角形内任意选择 10 个点 存在 2 个点 其间距离之多为 1 3 第 3 页 证明 证明 把边长为 1 的等边三角形按照右图方式分割为 9 部分 每一部分都是边长为 1 3 的等边三角形 在同一个小三角形中相距最远的 2 个点距离为 1 3 由鸽巢原理 任意选择 10 个点 至少有 2 个点属于同一个小三角形 即 在边长为 1 的等边三角形内任意选择 10 个点 w w w k h d a w c o m 课后答案网 SY0721129 刘佳 存在 2 个点 其间距离之多为 1 2 确定一个整数 使得如果在边长为 1 的等边三角形内任意选择个点 则存在 2 个点 其间距离之 多为 1 n m n m n 证明 证明 由等边三角形分割成小等边三角形的变化规律 1 4 9 16 25 2 n 可知 边长为 1 的等边三角形 可以分割为个边长为 1 的等边三角形 2 nn 边长为 1 的等边三