数学竞赛之组合数学选讲.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．平面上任给2019个点，其中任两点距离均大于 ，求证：必有223个点彼此之间距离都不小于2。 解答:将平面按图分成九个抽屉,i号小方格全体为第i个抽屉.2019个点分放在九个抽屉中,至少有一个抽屉含有223个点,由于2019个点中任两点距离均大于 ,所以此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 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的同侧，且ABAC,则d(B,PC)= d(P,m),矛盾. 13 例6． 一组砝码具有如下性质：（1）其中有5个砝码的质量各不相同；（2）对于任何2个砝码，都可以找到另外2个砝码，它们质量之和相等。问这组砝码至少有多少个？ 解答:设A是其中最重的砝码,B是次重的砝码,则质量组{A,B}的质量之和只能与质量分别与它们相等的两个砝码的质量之和相等.因此至少有两组这样的砝码.又砝码{A,A}的质量之和又只能与质量分别与它们相等的两个砝码的质量之和相等,因此最重的砝码至少有4个,次重的砝码至少有2个. 同理最轻的砝码至少有4个, 次轻的砝码至少有2个.因为有5个质量各不相同的砝码,