下载文档原格式
第二讲组合数学之染色与覆盖例1．有一次车展共36个展室，以下列图，每个展室与相邻的展室都有门相通，进口和出口以下图。
观光者（填“能”或“不可以”）从人口进去，不重复地观光完每个展室再从出口出来。
解：答：不可以；如图将展室黑白相间染色，进口为白色，出口也是白色，而走遍36个展室，从白到黑，再从黑到白，共走了35步，最后应当走到黑格，而出口仍旧是白格，矛盾，所以没法达成。
例2．棋盘由下列图所示的9个小圆圈摆列而成，用1~9编号，在3号和9号的小圆圈中各方一枚棋子，分别代表警察和小偷。
若两个小圆圈之间有线相连，则棋子能够从此中一格走入另一格，此刻由警察先走，两人轮番，每人每次走一步，每步能够从一格走到有线相连的临格之中。
假如在6步以内警察走入小偷所在的格子中，就算警察抓住了小偷而立功获胜；假如警察走了6步还没有抓住小偷，就算他渎职而失败。
问警察应怎样取胜。
147369258解：警察先从3走到1，则小偷从9走到7（或8）；第2步，警察走到2，小偷走到6（或9）；第3步，警察走到3，小偷走到7或8；第4步，警察走到4，小偷走到9；第5步，警察6，小偷不论是走到7（或8），警察在第6步必定能够获胜。
例3．空间六点任三点不共线，任四点不共面，成对地连结它们获得十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色），求证：不论这么染，总存在一个同色的三角形。
解：设六点为A、B、C、D、E、F，从A点出发的五条线段AB、AC、AD、AE、AF中起码有3条是同色的，不如设AB、AC、AD为红色，我们再看△BCD的三边，假如都是蓝色，那么存在同为蓝色的△BCD，若△BCD中有一条边不是蓝色，而是红色，不如设BC是红色，则AB、AC、BC都是红色，这是一个红色三角形。
所以总存在一个同色的三角形。
例4．下列图是由14个大小同样的方格构成的图形，试问方格构成的长方形。
（“能”或“不可以”）剪裁成7个由相邻两个解：答：不可以；如图，将图形黑白相间染色，则出现8个黑格，6个白格，而相邻的两个方格构成的长方形必定是一黑一白，矛盾，所以没法裁成7个小长方形。
组合数学第二讲抽屉原理的其他应用形式一、单色三角形问题前面数例我们看到，抽屉原理应用的关键在于恰当地制造抽屉，分割图形，利用自然数分类的不同方法如按剩余类制造抽屉或按奇数乘以2的方幂制造抽屉，利用奇偶性等等，都是制造“抽屉”的方法。
大家看到，抽屉原理的道理极其简单，但恰当地精心地应用它，不仅可以解决国内数学竞赛中的问题，而且可以解决国际中学生数学竞赛，例如IM0中的难题。
例1．（第6届国际中学生数学奥林匹克试题）17名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而且任意两名科学家通信时只讨论一个题目，证明：其中至少有三名科学家，他们相互通信时讨论的是同一个题目。
证明：视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个问题则在相应两点连条蓝线。
三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。
考虑科学家A，他要与另外的16位科学家每人通信讨论一个问题，相应于从A出发引出16条线段，将它们染成3种颜色，而16=3×5+1，因而必有6=5+1条同色，不妨记为AB1，AB2，AB3，AB4，AB5，AB6同红色，若B i（i=1，2，…，6）之间有红线，则出现红色三角线，命题已成立；否则B1，B2，B3，B4，B5，B6之间的连线只染有黄蓝两色。
考虑从B1引出的5条线，B1B2，B1B3，B1B4，B1B5，B1B6，用两种颜色染色，因为5=2×2+1，故必有3=2+1条线段同色，假设为黄色，并记它们为B1B2，B1B3，B1B4。
这时若B2，B3，B4之间有黄线，则有黄色三角形，命题也成立，若B2，B3，B4，之间无黄线，则△B2，B3，B4，必为蓝色三角形，命题仍然成立。
说明：（1）本题源于一个古典问题--世界上任意6个人中必有3人互相认识，或互相不认识。
教学目标抽屉原理是一种特殊的思维方法，不但可以根据它来做出许多有趣的推理和判断，同时能够帮助同学证明很多看似复杂的问题。
本讲的主要教学目标是：1．理解抽屉原理的基本概念、基本用法；2．掌握用抽屉原理解题的基本过程；3. 能够构造抽屉进行解题；4. 利用最不利原则进行解题；5.利用抽屉原理与最不利原则解释并证明一些结论及生活中的一些问题。
知识点拨一、知识点介绍抽屉原理有时也被称为鸽笼原理，它由德国数学家狄利克雷首先明确提出来并用来证明一些数论中的问题，因此，也被称为狄利克雷原则．抽屉原理是组合数学中一个重要而又基本的数学原理，利用它可以解决很多有趣的问题，并且常常能够起到令人惊奇的作用．许多看起来相当复杂，甚至无从下手的问题，在利用抽屉原则后，能很快使问题得到解决．二、抽屉原理的定义（1）举例桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。
（2）定义一般情况下，把n＋1或多于n＋1个苹果放到n个抽屉里，其中必定至少有一个抽屉里至少有两个苹果。
我们称这种现象为抽屉原理。
三、抽屉原理的解题方案（一）、利用公式进行解题苹果÷抽屉＝商……余数余数：（1）余数＝1， 结论：至少有（商＋1）个苹果在同一个抽屉里 （2）余数＝x ()()11xn -， 结论：至少有（商＋1）个苹果在同一个抽屉里（3）余数＝0， 结论：至少有“商”个苹果在同一个抽屉里 （二）、利用最值原理解题将题目中没有阐明的量进行极限讨论，将复杂的题目变得非常简单，也就是常说的极限思想“任我意”方法、特殊值方法．模块一、利用抽屉原理公式解题 （一）、直接利用公式进行解题 （1）求结论【例 1】 6只鸽子要飞进5个笼子，每个笼子里都必须有1只，一定有一个笼子里有2只鸽子．对吗？【例 2】 向阳小学有730个学生，问：至少有几个学生的生日是同一天？【例 3】 三个小朋友在一起玩，其中必有两个小朋友都是男孩或者都是女孩．【例 4】 “六一”儿童节，很多小朋友到公园游玩，在公园里他们各自遇到了许多熟人．试说明：在游园的小朋友中，至少有两个小朋友遇到的熟人数目相等．【例 5】 在任意的四个自然数中，是否其中必有两个数，它们的差能被3整除？【例 6】 证明：任取8个自然数，必有两个数的差是7的倍数．【例 7】 任给11个数，其中必有6个数，它们的和是6的倍数．【例 8】 任意给定2008个自然数，证明：其中必有若干个自然数，和是2008的倍数(单独一个数也当做和)． 【例 9】 求证：可以找到一个各位数字都是4的自然数，它是1996的倍数．【例 10】 求证：对于任意的8个自然数，一定能从中找到6个数a ，b ，c ，d ，e ，f ，使得()()()a b c d e f ---是105的倍数． 【例 11】 把1、2、3、…、10这十个数按任意顺序排成一圈，求证在这一圈数中一定有相邻的三个数之和不小于17． 【例 12】 证明：在任意的6个人中必有3个人，他们或者相互认识，或者相互不认识．【例 13】 上体育课时，21名男、女学生排成3行7列的队形做操．老师是否总能从队形中划出一个长方形，使得站在这个长方形4个角上的学生或者都是男生，或者都是女生?如果能，请说明理由；如果不能，请举出实例．知识精讲【例 14】 8个学生解8道题目．(1)若每道题至少被5人解出，请说明可以找到两个学生，每道题至少被过两个学生中的一个解出．(2)如果每道题只有4个学生解出，那么(1)的结论一般不成立．试构造一个例子说明这点.（2）求抽屉【例 15】 把十只小兔放进至多几个笼子里，才能保证至少有一个笼里有两只或两只以上的小兔？【例 16】 把125本书分给五⑵班的学生，如果其中至少有一个人分到至少4本书，那么，这个班最多有多少人？ 【例 17】 某班有16名学生，每个月教师把学生分成两个小组．问最少要经过几个月，才能使该班的任意两个学生总有某个月份是分在不同的小组里?（3）求苹果【例 18】 班上有50名小朋友，老师至少拿几本书，随意分给小朋友，才能保证至少有一个小朋友能得到不少于两本书？【例 19】 海天小学五年级学生身高的厘米数都是整数，并且在140厘米到150厘米之间（包括140厘米到150厘米），那么，至少从多少个学生中保证能找到4个人的身高相同？【例 20】 一次数学竞赛出了10道选择题，评分标准为：基础分10分，每道题答对得3分，答错扣 1分，不答不得分。
