离散第4讲 鸽笼原理2.2.ppt

第3讲 归纳原理 鸽笼原理 Textbook Page 25 to 28 内容提要 鸽笼原理的基本形式 基本形式一 基本形式二 巧妙应用鸽笼原理 鸽笼原理的加强形式* 加强形式一 加强形式二 加强形式三 鸽笼原理的直观解释 鸽笼原理的直观解释 鸽笼原理的直观解释 小档案——狄里克雷 鸽笼原理也叫做抽屉原理，狄里克雷原理, 以19世纪德国数学家狄里克雷的名字命名 狄里克雷在数论中有许多重要发现，并对于n = 5的情况证明了费马的最后的定理，即x5 + y5 = z5不存在非平凡的整数解 狄里克雷经常在工作中使用鸽笼原理 十分基本、非常重要、应用极其广泛的数学原理。是解决存在性问题的基本工具。 鸽笼原理的基本形式 基本形式一：如果把n + 1个（n为正整数）对象放入n个盒子里，那么至少有一个盒子中放有两个或两个以上的对象 证明：反设每个盒子都少于两个物体，则n个盒子里最多放置了n个物体，与前提矛盾。 应用举例 例1：在一组367个人中至少有多少人生日相同？ 至少有两个人有相同的生日，因为最多只有366种可能的出生日期。 例2：在27个英文单词中至少有多少个单词以同一字母打头？ 一定至少有两个单词以同一字母打头。 巧妙使用鸽笼原理 在边长为2的正方形中任取5个点，证明存在两个点，它们之间的距离不超过 。 证明　如图将正方形等分为4份。根据鸽笼原理，至少有一份中含有这5个点中的2个。由于这2个点在一个边长为1的正方形中，它们之间的距离显然不超过 。 　　　　　 例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)中各坐标均为整数，故该点是一个格点。 鸽笼原理的基本形式 基本形式二：如果把m个对象放入n个盒子里（m、n均为正整数），那么有一个盒子中至少放入了 (=r )个对象 证明：如果每个盒子包含的物体都不多于 ，那么物体总数最多为 ，从而不多于m-1，与前提矛盾。 在基本形式二中，令m=n+1，则得到基本形式一 应用举例 例3：100个人中至少有多少个人同一个月出生？ 至少有9个人同一个月出生. 例4：如果有5种可能的成绩A、B、C、D、E，那么一个班里至少有多少个学生才能保证至少有6个学生得到相同的分数？ 至少有26个学生 在鸽笼原理的许多有趣应用中，必须以某种巧妙的方式找到或设计问题中的盒子（n）、放入盒子里的物体(m)及盒子中物体的个数r。 应用举例 例5：为保证一个省的2500万个电话有不同的10位号码，所需的区号至少是多少？假定电话号码是Nxx-Nxxxxxx形式，前3位是区号，N表示2到9的十进制数字，x表示任意十进制数字。 所需的区号至少是4个(201,202,203,204): 例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 ，它们之中自然有一个可以被另一个整除。 例2.13 取黑白围棋子21枚，黑白数目不限，排列成3行7列的长方形。求证：无论怎样排放，都可以从中找到一个长方形，使该长方形的四个角的棋子同色。 证.设21枚棋子排成的长方形如下： 由鸽笼原理基本形式二， 中至少有 枚棋子同