离散第4讲 鸽笼原理2.2

计算机专业基础课程授课人：张桂芸dyxy1999@126.comPowerPointTemplate_Sub1归纳原理2鸽笼原理2第3讲归纳原理鸽笼原理Textbook

Page25to28《离散数学》第4讲内容提要鸽笼原理的基本形式基本形式一基本形式二巧妙应用鸽笼原理鸽笼原理的加强形式*加强形式一加强形式二加强形式三4第3讲归纳原理鸽笼原理的直观解释5第3讲归纳原理鸽笼原理的直观解释十只鸽子飞进9只笼子6第3讲归纳原理鸽笼原理的直观解释十只鸽子飞进9只笼子7第3讲归纳原理小档案——狄里克雷鸽笼原理也叫做抽屉原理，狄里克雷原理,以19世纪德国数学家狄里克雷的名字命名狄里克雷在数论中有许多重要发现，并对于n=5的情况证明了费马的最后的定理，即x5+y5=z5不存在非平凡的整数解狄里克雷经常在工作中使用鸽笼原理十分基本、非常重要、应用极其广泛的数学原理。是解决存在性问题的基本工具。8第3讲归纳原理鸽笼原理的基本形式基本形式一：如果把n+1个（n为正整数）对象放入n个盒子里，那么至少有一个盒子中放有两个或两个以上的对象证明：反设每个盒子都少于两个物体，则n个盒子里最多放置了n个物体，与前提矛盾。

9第3讲归纳原理应用举例例1：在一组367个人中至少有多少人生日相同？至少有两个人有相同的生日，因为最多只有366种可能的出生日期。例2：在27个英文单词中至少有多少个单词以同一字母打头？一定至少有两个单词以同一字母打头。10第3讲归纳原理巧妙使用鸽笼原理在边长为2的正方形中任取5个点，证明存在两个点，它们之间的距离不超过。证明如图将正方形等分为4份。根据鸽笼原理，至少有一份中含有这5个点中的2个。由于这2个点在一个边长为1的正方形中，它们之间的距离显然不超过。

11第3讲归纳原理例2.9：三维空间中有9个格点（各坐标均为整数的点），证明所有格点连线的中点中至少有一个也是格点。证：我们知道，格点的三个坐标的奇(用1表示)偶(用0表示)状况只有8个：(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)。因此，根据鸽笼原理基本形式一，9个格点中至少有两个格点的坐标的奇、偶状况相同。设这两个格点的坐标是(a,b,c)和(a’,b’,c’)，于是，它们之间连线的中点的坐标是((a+a’)/2,(b+b’)/2,(c+c’)/2),由于(a,b,c)和(a’,b’,c’)的奇、偶状况相同，((a+a’)/2,(b+b’)/2,(c+c’)/2)中各坐标均为整数，故该点是一个格点。12第3讲归纳原理鸽笼原理的基本形式基本形式二：如果把m个对象放入n个盒子里（m、n均为正整数），那么有一个盒子中至少放入了(=r)个对象证明：如果每个盒子包含的物体都不多于，那么物体总数最多为，从而不多于m-1，与前提矛盾。在基本形式二中，令m=n+1，则得到基本形式一13第3讲归纳原理应用举例例3：100个人中至少有多少个人同一个月出生？至少有9个人同一个月出生.例4：如果有5种可能的成绩A、B、C、D、E，那么一个班里至少有多少个学生才能保证至少有6个学生得到相同的分数？至少有26个学生在鸽笼原理的许多有趣应用中，必须以某种巧妙的方式找到或设计问题中的盒子（n）、放入盒子里的物体(m)及盒子中物体的个数r。14第3讲归纳原理应用举例例5：为保证一个省的2500万个电话有不同的10位号码，所需的区号至少是多少？假定电话号码是Nxx-Nxxxxxx形式，前3位是区号，N表示2到9的十进制数字，x表示任意十进制数字。

所需的区号至少是4个(201,202,203,204):15第3讲归纳原理例2.11：从集合{1，2，…，200}中任选101个数。证明：无论怎样选取，在选取的这些数中，必定存在两个数，使得其中之一可以被另一个整除。证：我们知道，任何正整数都可以写成2k·a的形式，其中k是自然数，a是奇数。对于集合{1，2，…，200}中的数，a只能是1，3，5，…，199这100个数中的一个。于是，根据鸽笼原理基本形式一，在选取的101个数中，有两个数的上述表示形式中的a是相同的。即分别是2k·a，2j·a，它们之中自然有一个可以被另一个整除。16第3讲归纳原理例2.13取黑白围棋子21枚，黑白数目不限，排列成3行7列的长方形。求证：无论怎样排放，都可以从中找到一个长方形，使该长方形的四个角的棋子同色。证.设21枚棋子排成的长方形如下：

由鸽笼原理基本形式二，中至少有枚棋子同色，不妨设它们是（黑子）。考虑，如果其中有两枚黑子，那么命题已成立；若不然，中至少有三枚白子，不妨设它们是。再考虑，这3枚棋子中必有枚棋子同色，如果其中有两枚白子，那么与中白子组成长方形白色的四角，满足命题要求；如果其中有