02.用数学归纳法解组合问题.pdf

6 中 等 数 学 用数 学归纳法解组合 问题 张 雪 天津 师范大学数学科学学院 l O级研 究生 3 0 0 3 8 7 中圈分类号 0 1 5 7 文献标识码 A 文章编号 1 0 0 5 6 4 1 6 2 0 1 2 0 2一 O 0 O 6 0 5 本讲适合 高中 数学归纳法 是数学解 题 的一种重要 方 法 在数学竞赛的各分支中有着广泛的应用 这种方法也经常用来解竞赛中的组合问题 实质就是将一个无法穷尽验证的命题转化为 普通命题进行证明 从而达到证明的目的 数 学归纳法有以下几种形式 第一数学归纳法 跳跃数学归纳法 第二数学归纳法 本文通过 具体实例例述数学归纳法在解组合问题中的 几种应用 1 组合恒等式 例 1 证 明 对一切正整数 t 和一切 实 数 有 E 1 C k x 一 1 一 1 2 证明当 ir t 1时 左边 1 一 1 右边 假设 7 m时 对一切实数有 1 c 0 1 则当 m 4 1时 对一切实数 有 1 c t 1 1 c c 1 收稿 日期 2 0 1 1 1 I一1 0 1 c m t 1 c r a c 一 薹 1 Ct x l J1 x m 一 1 2 m m 2 3 m十1 一 一 戈 1 2 m 1 m 1 一 1 z 2 x m 1 因此 当 n m 1时 题设等式成立 综上 命题成立 2 组合计数 例 2 设集合 S 1 2 n 为 S 的子集 把 中的所有数 的和称为 的 容 量 规定空集 的容量 为 0 若 的容量为 奇 偶 数 则称 为 S 的 奇 偶 子集 证 明 1 s 的奇子集与偶子集个数相等 2 当 n 3时 Is 的所有奇子集的容量 之和与所有偶子集的容量之和相等 1 9 9 2 全国高中数学联赛 证明设 s 的奇子集个数为t 容量之 和为 偶子集个数为 b 容量之和为 1 用数学归纳法证明 b 当 1 时 S 有一个奇子集t 1 有一个 偶子集 故 a b 1 假设 r k时 结论成立 接下来证明 口 b 万方数据 2 0 1 2年第 2 期 7 当 k为奇数时 k 1为偶数 I s 的所有 奇子集由两部分组成 不含 k 1的奇子集 含 k l 的奇子集 前者的个数是 a 后者可 由s 的奇子集与集合 j 1 的并产生 故个 数也为 a 于是 a 2 a 同理 b 川 2 b 于是 由假设知 a b 当 k为偶数时 k 1 为奇数 S 的所有 奇子集由两部分组成 不含 k 1的奇子集 含 k 1的奇子集 前者 的个数是 a 后者可 由S 的奇子集与集合 l 的并产生 故个 数为 b 于是 a a b 同理 b b a 因为 a b 所 以 结 论对 k l也 成立 综上 口 b 2 用数学归纳法证明 A B 当 n 3时 s 有 4个奇子集 1 3 2 1 2 3 有 4个偶子集 2 j 2 l 3 1 2 3 直接计算得 A B 3 1 2 假设 n Ij 3 时 A B 当 n k 1时 若 k l是奇数 则 s 的所有奇子集 由以下两类子集组成 i S 的奇子集 i i S 的每一个偶子集与集 的并 于是 A l A B k 1 b 同理 B l B A k 1 a 已证 a b 故 A 川 B 若 k 1 是偶数 有 A l 2 A k 1 a B l 2 B k 1 b 由归纳假设及 a b 得 A B 川 所以 对于任意 自然数 n n 3 都有 A B 注 本题中的两问均用到了第一数学 归纳法 先假设当 n k时结论成立 再分别 讨论当n k 1 时 k 为奇数与偶数的两种情 形 找到 Js 川 与 s 的关系后进行证明 可见 第一数学归纳法是最常运用到的方法 例 3 黑板上有一个凸 2 0 1 1边形 别佳 逐条依次画上它 的对角线 已知所 画的每条 对角线与前面已画上的对角线中的至多一条 交于内点 问 别佳至多可画上多少条对角 线 2 0 1 1 俄罗斯数学奥林 匹克 解用归纳法证明 对于凸 边形 至多 可画 2 n一 6条对角线 设A A A 是一个凸多边形 可依次画 出如下 2 n一 6 条对角线 A2 A4 A3 A5 9 6 1 A 一2A Al A3 A1 A 4 Al A 一1 当 n 3时 结论显然成立 假设小于 n时 命题都成立 对凸 n边形 设 画上 的最后一条对角线 为A A 它与前面已画的对角线中的至多一 条 若存在 设为 Z 交于内点 所有已画出的 对角线 除了A A 和 z 外 全部位于 k 边形 A l A 2 或 n 2一k 边形 A A 1 A A l 内 由归纳假设至多有 2 一 6 2 2 一 一 6 2 n 一 8 条对角线 其加上 A A 和 Z 后至多2 一 6 条 故对于凸 n边形 至多可画上 2 n一6条 对角线 所以 别佳至多可画上 4 0 1 6条对角线 注 本题首先要发现对于凸 n 边形而 言 至多有 2 n 一 6 条对角线 然后运用第二数 学归纳法证 明当边数小于 厅时成立 进而证 明凸 n边形满足上述条件 3 染色问题 例 4 一个有限图的顶点可染成黑 色或 白色 一开始所有的顶点都是黑色 每次操作 选择一个顶点 P 并将 P及其相邻的点进行 变色 问 能否经过一系列操作将所有顶点从 万方数据 8 中 等 数 学 黑色变为白色 L 4 2 0 1 0 加拿大数学奥林匹克 解可 以 对 n个顶点的图用归纳法进行证明 当 n 1时 显然成立 当图有 l n 2 个顶点时 此操作可 实现 设 为一个有 n个顶 点的图 顶点分别 为 P l P 2 P 设 P 为基点 进行操作变色 将其相邻 点设为 从图 jf 的边上移 出 得到一个 较小 的图 由归纳假设知 在 图 中存 在一个可操 作的序列g i 毋相邻的点为 F J 使得 这些点都可以变色 若按序列 g 操作改变了 P 的颜色 则视 为成功 假设按序列g 操作不能改变点 P i 1 2 n 的颜色 分两种情形讨论 1 n为偶数 按构造的序列 g g g 就能把每个 顶点的颜色从黑变 白 2 为奇数 图 中存在一顶点有偶数个邻点 事实上 设 P 的邻点个数为 k 等 价于 的边数 则 P 尸 2 2 e e 是图 的边数 所以 存在偶数 k 重新对顶点编号 假设 P i 有 2 j 个邻 点 分别为 P P P 构 造 的 序列 为 g g g 则按要求可 以使每个点 的颜 色都改变 注 在运用第一数学归纳法的时候 有 时假设 n成立 寻证 n l 成立有 困难 此时 不妨将 n退到 n一1 寻证 n成立 本题 就是 运用了这种方法 假设有限图有 n个顶点 设 有 n一1 个顶点图成立 进而结合图论的知识 讨论 n在偶 数和奇数 的情 形下顶 点染 色的 情形 例 5 为平面上有限多个整点所成的 集合 证 明 可将 中的点染成红色或蓝色 使得每一条与坐标轴平行 的直线上 两种颜 色点的个数相等或相差 1 5 证明对集合 中的点数 n 进行归纳 当 n 1 时 结论显然 假设在点数小于 时 命题成立 考虑 n个点 若在某一条平行于坐标轴的直线上只有 一 个点属于集合 则其余的 n一1 个点可以 用两种颜色染色 满足要求 在过此点与另一 条坐标轴平行 的直线 f 上 如果红点多 少 于蓝点 就将 这点染 成蓝 红 色 如果 红点 数等于蓝点数 就将这点随意染色 这样的染 色满足要求 设在每一条平行于坐标的直线上 若有 属于集合 的点 则至少有两个 此时 对集 合 中任一点 c 存在集合 M 中的点 D F 使得 C D C F分别与 轴 Y轴平行 设 为 矩形 C D E F的第四个顶点 如果点 E在集合 中 将 C D E F以 外的点染好 颜色满 足要求 然后 将点 C 染成红色 D F染成蓝色 如果点 E不在集合 中 将点 C D F 去掉 将点 E补充进来 由归纳假设 可将这 些点染上颜色满足要求 再将点 F D染上与 点 E相同的颜色 点 C染上与点 E不 同的颜 色 此时 集合 M中的点都染了颜色并且满 足要求 注 本题运用第二数学归纳法 先假设 点数小于 n时 命题成立 然后 在此基础上 分别讨论当集合 中有 n个点的两种不同 情形 在某一条平行于坐标轴的直线 上只有 一 个点属于集合 和在一条平行 于坐标轴 的直线上至少有两个点属于集合 万方数据 2 0 1 2年第2期 9 4覆盖 问题 例 6 如图 1 一个单位 L形 由三个单 位方 格组 成 证明 对于任意的正整数 k 一 个相似 的 i 倍 大的 L形可 以分 割 成 若 干 个 单 位 L 形 图 1 2 0 1 0 爱沙尼亚数学奥林匹克 证明如 图 2 放置大 L形 让其 较 长 的 两 边 交 于 左上 角 从左 上角 开始 用 k个 与大 L形方 向相同的单 位 L形 沿 对 角 线 方向覆盖大 L形 余下 的部 分 由两 图2 个相同的 楼梯形 组成 只需证明 其 中一 个 不妨设 为位置较 低的一个 可以被单位 L形不重叠地覆盖 这个楼梯形有 i 阶 最低一 阶的高度为 k一1 而最高一阶的高度为2 k一 2 当 k 1时 楼梯形不存在 当 k 2时 楼梯形可以被一个单位 L形 覆盖 假设结论对 k阶 的楼梯形 成立 下面考 虑 k 2阶的楼梯形 将左侧和底部宽为 2的条带分离出来 由归纳假设 余下 的部分可以被单位 L形覆 盖 条带的顶端可以被一个单位 L形覆盖 最后 尝试覆盖余下的条带 其底边长为 k 2 左侧边长为 2 Ij2 1 k能被 3整除 将该图分成 2 X 2 k和 k 2的两条 分别 用由两个单位 L形组成的 2 3的矩形覆盖 即可 如图 3 L 厂 厂 L 广 网 3 图 4 2 k 1 m o d 3 将该图分成 2 X 2 k一2 和 k 2 X 2 两部分 分别用 2 3的矩形覆盖 如图 4 3 k 2 m o d 3 将该图形分成 2 X 2 后 一 4 和 k一 2 2两部分 和左下角的一部分 这是一 个 k 2的 L形 两个条 带 都可 以用 2 X 3的矩 形 覆 盖 而根据 归纳 左下角 的 部分也可 以被单位 L形覆 盖 如图 5 L I 丰 三 图 5 注 本题因特殊条件需运用到跳跃数 学归纳法 即在假设结论对 k阶成立后 讨论 k 2阶楼梯形的情形 由于两个 L形重叠后 成为一个矩形 且长为 3个单位 于是 在此 就需要 针 对 k与 3的三 种关 系分 别 进行 讨论 例 7 在 n n的棋盘 中 任 k行和任 z 列的公共部分成为其 子片 并称 k 1为 其半周长 假如若干个半周长不小于 n的子 片共 同覆盖了棋盘的整条主对角线 证明 这 些子片所覆盖的方格数不少于棋盘总方格数 的一 半 第 2 5届全苏数学奥林 匹克 证明对 n用数学归纳法证明 当 n 1 2时 结论显然成立 当 n 2时 假设对所有 m X m m n 的棋盘结论成立 下面只需证对 n X n棋盘结论也成立 万方数据 1 0 中 等 数 学 事实上 对任一组满足要求 的子片 考虑 关于主对角线组成 的一对方格 i J 和 i i 若每对方格 中至少有一个被覆盖 则 结论成立 若某一对方格 i 与 J i i 都不 被覆盖 删去第 i J行及第 i J列 此 时 每 个子片至多被删去两行或两列或一行一列 否则 该子片盖住方 格 i 或 i 因此 在剩下棋盘 中 每个子片的半周长都不小于 n一2 根据归纳假设 剩下 it 一2 X it 一 2 的棋盘中至少有一半的方格被子片盖住 由上知共删去方格 4 n一4个 因为盖住 方格 i i 的子片半周长不小于 所以 其在 第 i 行和第 i 列至少覆盖了 1 1 一1个方格 同理 盖住 的子片至少盖住 了第 行和第 列的 n一1 个方格 因为子片不盖住 i 与 i 所以 删 去的两行 和两列中被子片覆盖的方格至少有 2 n一1 个 即不少于被删去方格的一半 于是 命题得证 练 习 题 1 设 k是 正 整 数 证 明 可 以将 集 合 O 1 2 3 2 一1 分成两个没有公共元 素 的子 集 X 2 和 y Y 2 使得 2 k 2 k Y i i l I l 对任何 m 1 2 j 都成立 2 0 0 5 中国国家集训队测试 提 示 对 k 用第二数学归纳法进行证明 当 k 1 时成立 假设命题在小于或等于 k时成立 讨论 k 1时的情形 由假设知 1 X 2 孙 y 1 2 I Y 2 Y 2 U y l y 2 2 k I 2 2 2 0 1 2 2 一1 并且这两个子集没有公共元素 再证明两个 子集的元素和相等即可 2 对 2 0 0 7 2 0 0 7方格表中的一些单位 正方形进行染色 用 i J 表示第 i 行 第 列 的单位正方形 s 表示所有 已经染过色且满 足 i 及 Y 的单位 正方形 Y 组成 的 集合 首先 在每一个 已染过色 的单位正方形 i J 中写下其所对应 的 S 所 含的有 色单 位正方形的个数 接下来每一次操作是指分 别在每一个已染过色的单位正方形 i 中 写下其所对应的 Is 在上一次操作以后所包 含的所有有色单位正方形 中所填数字之和 证明 经过有限次这样的操作 所有有色单位 正方形 中的数字都是奇数 第 1 5届土耳其数学奥林匹克 提示 参见 中等数学 2 0 0 9年增刊第 6 9页 3 试证 在 2 2 个单位小方格组成 的 正方形棋盘上