组合数学教学课程.pptVIP

例18.一个学校只有3门课程：数学、物理、化学，已知修这3门课程的学生分别有170、130、120人；同时修数学、物理两门课的学生有45人；同时修数学、化学两门课的学生有20人；同时修物理、化学两门课的学生有22人；同时修三门课的学生有3人。问这个学校共有多少学生？ 例19. 求a，b，c，d，e，f这六个字母的全排列中不允许出现ace和df图像的排列数。 例21. 求由a，b，c，d这4个字符构成的n位数字串中，a，b，c至少出现一次的符号串的数目。 同理 练习题 1．给定2003个集合，每个集合都恰含有44个元素，并且每两个集合都恰有一个公共元素，试求这2003个集合的并集中有多少个元素？ 2．平面内给定200个不同的点，证明：其中距离为单位长的点对数小于2050。 3．以正n边形的顶点为顶点的梯形共有多少个？ 杂 题 例1 运动会开了n天（n1）,共发出m个奖牌,第一天发出1个加余下奖牌的,第二天发出2个加余下奖牌的,如此继续下去,最后,第n天发出n个奖牌恰无剩余.问运动会共开了几天?共发出多少个奖牌? * * 组合数学 西北工业大学附属中学 焦和平 一．概论 组合数学是一个古老而又年轻的数学分支。 组合数学中的著名问题  地图着色问题 中国邮差问题 船夫过河问题 任务分配问题 组合数学主要研究一组离散对象满足一定条件的安排，讨论的内容大致有四方面： 1．存在性：有没有满足条件的安排？ 2．计数：满足条件的安排有多少种？ 3．构造：给出满足条件的安排的具体构造。 4．优化：在众多满足要求的安排中，按一定的标准挑出最优的安排。 二、数学竞赛中的主要问题 1．组合数学中的存在性问题 1．1抽屉原理 抽屉原理是一件简单明了的事实：n+1个物品放入n个抽屉中，则至少有一个抽屉，其中有两个或更多的物品。 一般地：m个物品放入n个抽屉中，则至少有一个抽屉不少于a个，其中 抽屉原理 一般地：m个物品放入n个抽屉中，则至少有一个抽屉不少于a个，其中 抽屉原理的变式 例1．单位圆内任意投放六点，求证至少有两点距离不大于1。 解答：取六点中一点A，若A为单位圆的圆心，结论显然成立。 若A不是圆心O，则如图将单位圆划分为六个中心角为60度的扇形,若阴影部分内尚有六点中另一点,则结论成立. 若阴影部分内没有六点中除A点外的点,则另五点(物品)在其余四个扇形(抽屉)中,由抽屉原理,必有某个扇形(抽屉)含有至少两个(物品),故结论成立. 例2．平面上任给2005个点，其中任两点距离均大于 ，求证：必有223个点彼此之间距离都不小于2。 解答:将平面按图分成九个抽屉,i号小方格全体为第i个抽屉.2005个点分放在九个抽屉中,至少有一个抽屉含有223个点,由于2005个点中任两点距离均大于 ,所以此223个点距离均大于,它们中没有两点属于同一小方格,而同号方格又不在同一方格中的任两点距离都不小于2. 1 2 3 1 2 3 1 2 3 4 5 6 4 5 6 4 5 6 7 8 9 7 8 9 7 8 9 1 2 3 1 2 3 1 2 3 4 5 6 4 5 6 4 5 6 7 8 9 7 8 9 7 8 9 1 2 3 1 2 3 1 2 3 4 5 6 4 5 6 4 5 6 7 8 9 7 8 9 7 8 9 1．2 极端原理 利用讨论“极端”对象来实现问题解决的解题方法称为用极端原理解题，常用的极端原理基于下述简单的事实： 1）由实数组成的有限集合，必有一个最大数，也有一个最小数。 2）由自然数组成的任何非空集合中，必有一个最小的自然数。 为了肯定或否定组合数学问题的存在性，极端原理有着重大的作用。考察极端情况，讨论极端对象，无形中给问题的讨论增加了一个条件，所以更有利于问题的解决；用反证法时，讨论极端情况，使矛盾更容易暴露。 例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的同侧，且ABAC,则d(B,PC)= d(P,m),矛盾. 例6． 一组砝码具有如下性质：（1）其中有5个砝码的质量各不相同；（2）对于任何2个砝码，都可以找到另外2个砝码，它们质量之和相等。问这组砝码至