组合数学课件..ppt

1 组合数学 西北工业大学附属中学焦和平 2 一 概论 组合数学是一个古老而又年轻的数学分支 组合数学中的著名问题 地图着色问题 中国邮差问题 船夫过河问题 任务分配问题 3 组合数学主要研究一组离散对象满足一定条件的安排 讨论的内容大致有四方面 1 存在性 有没有满足条件的安排 2 计数 满足条件的安排有多少种 3 构造 给出满足条件的安排的具体构造 4 优化 在众多满足要求的安排中 按一定的标准挑出最优的安排 4 二 数学竞赛中的主要问题 1 组合数学中的存在性问题1 1抽屉原理抽屉原理是一件简单明了的事实 n 1个物品放入n个抽屉中 则至少有一个抽屉 其中有两个或更多的物品 一般地 m个物品放入n个抽屉中 则至少有一个抽屉不少于a个 其中 5 抽屉原理 一般地 m个物品放入n个抽屉中 则至少有一个抽屉不少于a个 其中 6 抽屉原理的变式 7 例1 单位圆内任意投放六点 求证至少有两点距离不大于1 解答 取六点中一点A 若A为单位圆的圆心 结论显然成立 若A不是圆心O 则如图将单位圆划分为六个中心角为60度的扇形 若阴影部分内尚有六点中另一点 则结论成立 若阴影部分内没有六点中除A点外的点 则另五点 物品 在其余四个扇形 抽屉 中 由抽屉原理 必有某个扇形 抽屉 含有至少两个 物品 故结论成立 8 例2 平面上任给2005个点 其中任两点距离均大于 求证 必有223个点彼此之间距离都不小于2 解答 将平面按图分成九个抽屉 i号小方格全体为第i个抽屉 2005个点分放在九个抽屉中 至少有一个抽屉含有223个点 由于2005个点中任两点距离均大于 所以此223个点距离均大于 它们中没有两点属于同一小方格 而同号方格又不在同一方格中的任两点距离都不小于2 9 本题牵扯到A的子集以及子集中各数之和两个讨论对象 分别讨论它们有多少种 15元子集A的子集共个 不空真子集共个 真子集中各数之和S满足 27979 子集中各数和的种数不超过27979 将32766个子集放入27979类和 抽屉 中 至少有一类和中含有两个子集 即有B与C中各数和相等 若 则结论成立 若 则以代替B C 结论亦成立 10 11 1 2极端原理 利用讨论 极端 对象来实现问题解决的解题方法称为用极端原理解题 常用的极端原理基于下述简单的事实 1 由实数组成的有限集合 必有一个最大数 也有一个最小数 2 由自然数组成的任何非空集合中 必有一个最小的自然数 为了肯定或否定组合数学问题的存在性 极端原理有着重大的作用 考察极端情况 讨论极端对象 无形中给问题的讨论增加了一个条件 所以更有利于问题的解决 用反证法时 讨论极端情况 使矛盾更容易暴露 12 例5 对平面上不全共线的n个点 求证 必存在一条恰好通过两点的直线 解答 对n个点中的任两点作连线m 并取连线外的点P 必存在 考察P到m的距离d P m 由于点为有限个 连线m为有限条 组合 P m 也只能有有限个 用极端原理设d P m 为最小 下面证明 m恰通过n点中2点 过点P作m的垂线 设垂足为A 若m上至少有n点中的3点 则至少有2点在A的同侧 设B C在A的同侧 且AB AC 则d B PC d P m 矛盾 13 例6 一组砝码具有如下性质 1 其中有5个砝码的质量各不相同 2 对于任何2个砝码 都可以找到另外2个砝码 它们质量之和相等 问这组砝码至少有多少个 解答 设A是其中最重的砝码 B是次重的砝码 则质量组 A B 的质量之和只能与质量分别与它们相等的两个砝码的质量之和相等 因此至少有两组这样的砝码 又砝码 A A 的质量之和又只能与质量分别与它们相等的两个砝码的质量之和相等 因此最重的砝码至少有4个 次重的砝码至少有2个 同理最轻的砝码至少有4个 次轻的砝码至少有2个 因为有5个质量各不相同的砝码 至少还有另一种质量的砝码 所以砝码个数至少有4 4 2 2 1 13个 另一方面 质量分别为 1 1 1 1 2 2 3 4 4 5 5 5 5 的13个砝码满足题给条件 14 例7 n n 3 名乒乓球选手单打比赛若干场后 任意两名选手已赛过的对手恰好都不完全相同 求证 总可以从中去掉一名选手 使得余下的选手中 任意两个选手已赛过的对手仍然都不完全相同 证明 若不存在可去选手 则A不是可去选手 去掉A后 至少存在选手B和C 他们赛过的对手完全相同 故B和C一定没有赛过 B和C中恰有一人 不妨设为B 与A赛过 否则B和C在未去掉A时赛过的对手完全相同 如图 同时C也不是可去选手 C代替A 如上述讨论可知 有D和E 其中D和C赛过 E和C未赛过 去掉C后 D和E赛过的对手相同 D不会是A B 因A B与C未赛过 D与B赛过 因D和C赛过 去掉A后 B C对手相同 去掉C后 D和E赛过的对手相同 所以E与B也赛过 15 1 3构造法和不变性原理 通过直接构作出解答来实现问题的解决称为用构造法解题 对讨论问题分析其变化 找出其中不变的量 不变的关系或不变的性质 抓住变中的 不变 以促使问题的解决称为用不变性原理解题 对于组合数学的存在性问题 常用构造法给出肯定的答案 而不变性原理常可给出否定的结论 不变性原理中最简单 最实用的是奇偶性分析 16 例8 有一个凸n边形 n4 所有顶点用红绿蓝三色染色 三种颜色都出现 且任意两相邻顶点不同色 求证 可用在n边形内不交的对角线将多边形分成n 2个三角形 使每个三角形的三顶点都不同色 解答 若某种颜色的点只有一个 则易知结论成立 若每种颜色的顶点至少有二个 且相邻顶点颜色不同 则必有连续三个顶点k k 1 k 2恰为三色 将此三角形从凸n边形中割下 那么余下的是规模更小的凸多边形 若仍然每种颜色的顶点至少有二个 可继续割去一个三色三角形 最后可得某种颜色只有一个 可以如图给出分划 17 例9 能否把1 1 2 2 3 3 2005 2005这4010个数排成一列 使得两个1之间有一个数 两个2之间有二个数 两个2005之间有2005个数 18 证明 充分性 可用构造法作出 如图 正方形可剖分成6个钝角三角形 又任一钝角三角形总可分成两个钝角三角形 必要性 先找出任意钝角三角形剖分中不变的关系 对剖分法的剖分点进行分类 在正方形边界上的剖分点或在某一剖分三角形边上但不是该三角形顶点的内剖分点称为第一类剖分点 不在三角形边上的内剖分点称为第二类剖分点 如图中F G H为第一类剖分点 E为第二类剖分点 19 20 2 任意凸四边形 各种情形 可剖分成钝角三角形 锐角三角形 的充要条件又各是什么 21 2 组合数学中的计数问题 2 1加法原理和乘法原理加法原理 设事件A有m种选取方式 事件B有n种选取方式 事件A和事件B没有共同选取方式 则选A或选B有m n种方式 乘法原理 设事件A有m种选取方式 事件B有n种选取方式 则选取A以后再选B共有mn种方式 22 23 例12 三个数1447 1005 1231有许多相同之处 它们都有四位数 最高位都是1 都恰有两个相同的数字 一共有多少个这样的数 24 2 2映射与计数 25 例13 在数列1 9 81 92005中删去最高位是9的项 问余下的数列有多少项 26 例14 圆周上有n个点每两个点连一线段 假设任三条线段在圆内不共点 于是三条两两相交的线段构成一个三角形 试求这些三角形的个数 27 例15 设凸n边形的任意3条对角线不相交于行内一点 求它的对角线在行内的交点总数 28 例16 今有编号为1 2 10的钥匙与编号为1 2 10的箱子 每把钥匙只能打开与之号数相同的箱子 现将所有钥匙都放进这些箱子中 每只箱子放一把 然后锁上 那么至少有多少种不同的放法 使得至少要撬开两只箱子才能将箱子全部打开 若恰撬开两只箱子才能将箱子全部打开 又有多少放法 29 证明 我们将不定方程的任意一组非负整数解对应于一个由n个圆圈 k 1个竖线 组成的如下排列 其中第一根竖线 的左侧恰有x1个圆圈 第i 1根竖线 与第i根竖线 之间恰有xi个圆圈 第i 1根竖线 的右侧恰有xk个圆圈 显然 不定方程的不同的解对应于不同的排列 且每一个这样的对应于不定方程的一组非负整数解 因此 我们建立的对应是一个双射 又因为由n个圆圈 及k 1根竖线 组成的n k 1个元素的全排列数为 所以 不定方程的一组非负整数解组的组数为 30 2 3容斥原理 31 例18 一个学校只有3门课程 数学 物理 化学 已知修这3门课程的学生分别有170 130 120人 同时修数学 物理两门课的学生有45人 同时修数学 化学两门课的学生有20人 同时修物理 化学两门课的学生有22人 同时修三门课的学生有3人 问这个学校共有多少学生 32 例19 求a b c d e f这六个字母的全排列中不允许出现ace和df图像的排列数 33 34 例21 求由a b c d这4个字符构成的n位数字串中 a b c至少出现一次的符号串的数目 35 36 同理 37 38 练习题 1 给定2003个集合 每个集合都恰含有44个元素 并且每两个集合都恰有一个公共元素 试求这2003个集合的并集中有多少个元素 2 平面内给定200个不同的点 证明 其中距离为单位长的点对数小于2050 3 以正n边形的顶点为顶点的梯形共有多少个 39 杂题 40 例1运动会开了n天 n 1 共发出m个奖牌 第一天发出1个加余下奖牌的 第二天发出2个加余下奖牌的 如此继续下去 最后 第n天发出n个奖牌恰无剩余 问运动会共开了几天 共发出多少个奖牌 41 42 43 例2 几个人在一起 使得其中存在有相同生日的概率至少为二分之一 即23人中 至少有一对生日相同的概率超过二分之一 44 例3 甲乙二人玩 在黑板上写数的游戏 规则是二人轮流在黑板上写一个不超过p的自然数 但禁止再写出黑板上已有的因数 甲先开始写 轮到谁写而无法写出时就告负 1 当p 10时 游戏者中谁有获胜策略 2 当p 1000时 游戏者中谁有获胜策略 解答 1 甲有获胜策略 他可以先写6 于是按规则不能再写1 2 3 其余6个数分成3组 4 5 7 9 8 10 无论乙写哪一个 甲就写同组的另一个 2 考察写数原则相同但取数范围不是由1到1000而是由2到1000的这个游戏 如果这个游戏先写者有必胜策略 那么甲对原来的游戏只要照搬就行了 因为甲写下一个自然数后 乙是不能写1的 如果新游戏先写数的人没有获胜策略 即他只能告负 那么甲在原游戏中可以先写1 从而将失败留给了乙 可见 甲总有获胜策略 45 例4 甲乙两人在画有个方格的正方形场地上做游戏 甲先在场地中央画一个星号 乙则在放有星号的格子周围的8个格子中任选1个方格画一个圆圈 然后甲再在某个与已画有标记的格子挨着的空格中画一个星号 并一直继续下去 如果甲成功地将星号画入场地四角的任何一个角上的方格中 就算他获胜 求证 不论乙怎么做 甲总可以获胜 46 例5 在3 3的正方形表格中填上如图所示的9个数字 将该表进行如下操作 每次操作是对表中相邻两数同时加上一个数 相邻是指有公共边的两小格 问能否经过若干次操作使得 1 表格中各数均为0 2 表格中四个角的数为1 其余均为0 47 解答 1 能够得到 事实上经过5次操作即可 48 2 考虑这种操作的一般形式 abcdefghk为此 设表格中第一行的数从左到右为a b c 第二行的数从左到右为d e f 第三行的数从左到右为g h k 按操作规则 任意相邻的数都加同一个数 因此操作的每一步均不改变S a c e g k b d h f 的值 而表格的初始状态S的值为S 0 2 7 4 5 3 6 9 0 0要达到的状态S的值为S 1 1 0 1 1 0 0 0 0 4因此不能实现满足题目要求的操作 49 例6 凸n边形的任意3条对角线不相交于形内一点 求这些对角线将凸n边形分成的区域的个数 50 51 52 53 54 例7 已知平面上有4条直线 其中任何两条都相交 任何三条都不交于一点 于是在每条直线上都交得3个交点 它们从直线上截出两条线段 共得到8条线段 问这8条线段的长度能否分别为 1 1 2 3 4 5 6 7 8 2 互不相同的自然数 55 2 8条线段的长度可以是互不相同的自然数 见图 56 例8 一袋花生共1988颗 一只猴子第一天拿走一颗花生 从第二天起 每天拿走的都是以前各天的总和 如果到某天袋里的花生少于已拿走的总数时 这一天它又从拿走一颗开始 按原定的规律进行