《组合数学课件.》由会员分享，可在线阅读，更多相关《组合数学课件.（58页珍藏版）》请在金锄头文库上搜索。
1、组合数学 西北工业大学附属中学 焦和平 1 一概论 pp组合数学是一个古老而又年轻的数学分支。组合数学是一个古老而又年轻的数学分支。 组合数学中的著名问题组合数学中的著名问题 地图着色问题地图着色问题 中国邮差问题中国邮差问题 船夫过河问题船夫过河问题 任务分配问题任务分配问题 2 组合数学主要研究一组离散对象满足一组合数学主要研究一组离散对象满足一 定条件的安排，讨论的内容大致有四方面：定条件的安排，讨论的内容大致有四方面： pp1 1存在性存在性：有没有满足条件的安排？：有没有满足条件的安排？ pp2 2计数计数：满足条件的安排有多少种？：满足条件的安排有多少种？ pp3 3构造构造：给出
2、满足条件的安排的具体构造。：给出满足条件的安排的具体构造。 pp4 4优化优化：在众多满足要求的安排中，按一定的标：在众多满足要求的安排中，按一定的标 准挑出最优的安排。准挑出最优的安排。 3 二、数学竞赛中的主要问题 p1组合数学中的存在性问题 p11抽屉原理 抽屉原理是一件简单明了的事实：n+1个物品 放入n个抽屉中，则至少有一个抽屉，其中有两个 或更多的物品。 一般地：m个物品放入n个抽屉中，则至少有 一个抽屉不少于a个，其中 4 抽屉原理 p一般地：m个物品放入n个抽屉中，则至少有一个 抽屉不少于a个，其中 5 抽屉原理的变式抽屉原理的变式 6 例例1 1单位圆内任意投放六点，求证至少
3、有两点距离单位圆内任意投放六点，求证至少有两点距离 不大于不大于1 1。 pp解答：取六点中一点解答：取六点中一点A A， 若若A A为单位圆的圆心，为单位圆的圆心， 结论显然成立。结论显然成立。 若若A A不是圆心不是圆心OO，则如图将，则如图将 单位圆划分为六个中心角为单位圆划分为六个中心角为6060度的扇形度的扇形, ,若阴影部若阴影部 分内尚有六点中另一点分内尚有六点中另一点, ,则结论成立则结论成立. . 若阴影部分若阴影部分 内没有六点中除内没有六点中除A A点外的点点外的点, ,则另五点则另五点( (物品物品) )在其余在其余 四个扇形四个扇形( (抽屉抽屉) )中中, ,由抽屉
4、原理由抽屉原理, ,必有某个扇形必有某个扇形( (抽屉抽屉 ) )含有至少两个含有至少两个( (物品物品), ),故结论成立故结论成立. . 7 例例2 2平面上任给平面上任给20052005个点，其中任两点距离均大于个点，其中任两点距离均大于 ，求证：必有，求证：必有223223个点彼此之间距离都不小于个点彼此之间距离都不小于2 2。 pp解答解答: :将平面按图分成九个将平面按图分成九个 抽屉抽屉,i,i号小方格全体为第号小方格全体为第i i 个抽屉个抽屉.2005.2005个点分放在九个点分放在九 个抽屉中个抽屉中, ,至少有一个抽屉至少有一个抽屉 含有含有223223个点个点, ,由于
5、由于20052005个个 点中任两点距离均大于点中任两点距离均大于 , ,所以此所以此223223个点距离均大个点距离均大 于于, ,它们中没有两点属于同它们中没有两点属于同 一小方格一小方格, ,而同号方格又不而同号方格又不 在同一方格中的任两点距在同一方格中的任两点距 离都不小于离都不小于2.2. 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 4 4 5 5 6 6 4 4 5 5 6 6 4 4 5 5 6 6 7 7 8 8 9 9 7 7 8 8 9 9 7 7 8 8 9 9 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 4 4
6、5 5 6 6 4 4 5 5 6 6 4 4 5 5 6 6 7 7 8 8 9 9 7 7 8 8 9 9 7 7 8 8 9 9 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 4 4 5 5 6 6 4 4 5 5 6 6 4 4 5 5 6 6 7 7 8 8 9 9 7 7 8 8 9 9 7 7 8 8 9 9 8 pp本题牵扯到本题牵扯到A A的子集以及子集中各数之和两个讨论的子集以及子集中各数之和两个讨论 对象，分别讨论它们有多少种。对象，分别讨论它们有多少种。1515元子集元子集A A的子集的子集 共个共个 ，不空真子集共，不空真子集共 个，真子个，
7、真子 集中各数之和集中各数之和S S满足满足 =27979=27979， pp子集中各数和的种数不超过子集中各数和的种数不超过2797927979，将，将3276632766个子个子 集放入集放入2797927979类和（抽屉）中，至少有一类和中含类和（抽屉）中，至少有一类和中含 有两个子集，即有有两个子集，即有 B B与与C C中各数和相中各数和相 等。若等。若 ，则结论成立；若，则结论成立；若 ，则以，则以 pp 代替代替B B，C C，结论亦成立。，结论亦成立。 9 10 1 12 2 极端原理极端原理 利用讨论“极端”对象来实现问题解决的解题方法 称为用极端原理解题，常用的极端原理基于
8、下述简单 的事实： 1）由实数组成的有限集合，必有一个最大数，也 有一个最小数。 2）由自然数组成的任何非空集合中，必有一个最 小的自然数。 为了肯定或否定组合数学问题的存在性，极端原 理有着重大的作用。考察极端情况，讨论极端对象， 无形中给问题的讨论增加了一个条件，所以更有利于 问题的解决；用反证法时，讨论极端情况，使矛盾更 容易暴露。11 例例5 5 对平面上不全共线的对平面上不全共线的n n个点，求证：必存在一个点，求证：必存在一 条恰好通过两点的直线。条恰好通过两点的直线。 解答：对解答：对n n个点中的任两点作连线个点中的任两点作连线mm， 并取连线外的点并取连线外的点P P（必存在
9、），（必存在）， 考察考察P P到到mm的距离的距离d d（P P，mm），）， 由于点为有限个，连线由于点为有限个，连线mm为有限条，为有限条， 组合（组合（P P，mm）也只能有有限个，用极端原理设）也只能有有限个，用极端原理设d d（ P P，mm）为最小。）为最小。 下面证明，下面证明，mm恰通过恰通过n n点中点中2 2点：点： 过点过点P P作作mm的垂线，设垂足为的垂线，设垂足为A.A.若若mm上至少有上至少有n n 点中的点中的3 3点，则至少有点，则至少有2 2点在点在A A的同侧，设的同侧，设B B，C C在在A A 的同侧，且的同侧，且AB3）名乒乓球选手单打比赛若干场后
10、）名乒乓球选手单打比赛若干场后, ,任意两任意两 名选手已赛过的对手恰好都不完全相同名选手已赛过的对手恰好都不完全相同, , 求证求证: :总可以从中去掉一名选手总可以从中去掉一名选手, ,使得余下的选手中使得余下的选手中, ,任意任意 两个选手已赛过的对手仍然都不完全相同两个选手已赛过的对手仍然都不完全相同. . pp证明证明: :若不存在可去选手若不存在可去选手, ,则则A A不是可去选手不是可去选手, , 去掉去掉A A后后. .至至 少存在选手少存在选手B B和和C,C,他们赛过的对手完全相同他们赛过的对手完全相同, ,故故B B和和C C一定一定 没有赛过没有赛过; B; B和和C
11、C中恰有一人中恰有一人( (不妨设为不妨设为B)B)与与A A赛过赛过( (否则否则B B 和和C C在未去掉在未去掉A A时赛过的对手完全相同时赛过的对手完全相同), ),如图如图: : 同时同时C C也不是可去选手也不是可去选手, C, C代替代替A,A, 如上述讨论可知如上述讨论可知, ,有有D D和和E,E,其中其中D D和和C C赛过赛过, , E E和和C C未赛过未赛过, , 去掉去掉C C后后, D, D和和E E赛过的对手赛过的对手 相同相同.D D不会是不会是A,B(A,B(因因A,BA,B与与C C未赛过未赛过),D),D与与B B 赛过赛过( (因因D D和和C C赛过
12、赛过, , 去掉去掉A A后后,B,C,B,C对手相同对手相同). ). 去掉去掉C C后后, D, D和和E E赛过的对手相同赛过的对手相同. .所以所以E E与与B B也赛过也赛过. . 14 1.3 构造法和不变性原理 pp通过直接构作出解答来实现问题的解决称为用构通过直接构作出解答来实现问题的解决称为用构 造法解题造法解题; ;对讨论问题分析其变化对讨论问题分析其变化, ,找出其中不变找出其中不变 的量、不变的关系或不变的性质，抓住变中的的量、不变的关系或不变的性质，抓住变中的“ “不不 变变” ”以促使问题的解决称为用不变性原理解题。以促使问题的解决称为用不变性原理解题。 pp对于组
13、合数学的存在性问题，常用构造法给出肯对于组合数学的存在性问题，常用构造法给出肯 定的答案，而不变性原理常可给出否定的结论。定的答案，而不变性原理常可给出否定的结论。 不变性原理中最简单、最实用的是奇偶性分析。不变性原理中最简单、最实用的是奇偶性分析。 15 例例8 8 有一个凸有一个凸n n边形（边形（n4n4）所有顶点用红绿蓝三色）所有顶点用红绿蓝三色 染色，三种颜色都出现，且任意两相邻顶点不同色，染色，三种颜色都出现，且任意两相邻顶点不同色， 求证：可用在求证：可用在n n边形内不交的对角线将多边形分成边形内不交的对角线将多边形分成n-2n-2 个三角形，使每个三角形的三顶点都不同色。个三
14、角形，使每个三角形的三顶点都不同色。 pp解答解答: :若某种颜色的点只有一个若某种颜色的点只有一个, ,则易知结论成立则易知结论成立. .若若 每种颜色的顶点至少有二个每种颜色的顶点至少有二个, ,且相邻顶点颜色不同且相邻顶点颜色不同, ,则则 必有连续三个顶点必有连续三个顶点k,k+1,k+2k,k+1,k+2恰为三色恰为三色, ,将此三角形从将此三角形从 凸凸n n边形中割下边形中割下, , 那么余下的是规模更小的凸多边形那么余下的是规模更小的凸多边形, , 若仍然每种颜色的顶点至少有二个若仍然每种颜色的顶点至少有二个, , 可继续割去一个三色三角形可继续割去一个三色三角形, 最后可得某
15、种颜色只有一个最后可得某种颜色只有一个, , 可以如图给出分划可以如图给出分划. . 16 例例9 9 能否把能否把1 1，1 1，2 2，2 2，3 3，3 3，20052005，20052005这这 40104010个数排成一列，使得两个个数排成一列，使得两个1 1之间有一个数，两个之间有一个数，两个2 2 之间有二个数，之间有二个数，两个，两个20052005之间有之间有20052005个数个数 . . 17 p证明：充分性：可用构造法作出，如图，正方形可剖 分成6个钝角三角形，又任一钝角三角形总可分成两个 钝角三角形。 必要性：先找出任意钝角三角形剖分中不变的关系。 对剖分法的剖分点进行分类：在正方形边界上的剖分 点或在某一剖分三角形边上但不是该 三角形顶点的内剖分点称为第一类 剖分点；不在三角形边上的内剖分点 称为第二类剖分点。如图中F，G，H 为第一类剖分点，E为第二类剖分点。 18 19 （2）任意凸四边形（各种情形）可剖分成钝角三角形（ 锐角三角形）的充要条件又各是什么？ 20 2组合数学中的计数问题 p21 加法原理和乘法原理 p加法原理：设事件A有m种选取方式，事件B有n种选取 方式，事件A和事件B没有共同选取方式，则选A或选B 有m+n种方
