第二章(Chapter 2)鸽巢原理.ppt

第二章(Chapter 2) 鸽巢原理 (The Pigeonhole Principle) 2.1 问题的引入 鸽巢原理又称抽屉原理(the Dirichlet drawer principle)或鞋盒原理(shoebox principle) 原理阐释：有许多鸽子飞进不足够多的鸽子巢内，那么至少要有一个鸽巢被两个或多个鸽子占据。 2.1问题的引入 实例： ⒈ 366个人中必然有至少两人生日相同。 ⒉ 抽屉里散放着10双手套，从中任意抽取11只，其中至少有两只使成双的。 ⒊ 某次会议有n位代表参加，每位代表认识其他代表中某些人，则至少有两个人认识的人数是一样的。 ⒋ 任给5个不同的整数，其中至少有3个数的和被3整除。 这些例子中都包含着鸽巢原理的一般意义! 2.2 鸽巢原理的简单形式： 定理2.1 如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多个物体。 证明：如果这n个盒子中的每一个都至多含有一个物体，那么物体的总数最多是n。既然我们有n+1个物体，于是某个盒子就必然包含至少两个物体。 [注]： ①鸽巢原理仅能被用于证明一个排列或某种现象的存在性，不能对任何构造排列或寻找现象的例证给出任何指示。 ②一些与鸽巢原理相关的其他原理： 如果n个物体放入n个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体； 如果n个物体放入n个盒子并且没有盒子被放入多于一个物体，那么每个盒子中恰好有一个物体； ③上述三个原理的抽象表述形式： 令X和Y是两个有限集，并令f ：X→Y是一个从X到Y的函数， 如果X的元素多于Y的元素，那么f 就不是一一对应的。 如果X和Y含有相同个数的元素，并且f 是映上(onto)的,那么f 就是一一对应的。 如果X和Y含有相同个数的元素，并且f 是一对一的，那么f 就是映上的。 ④若把将物体放入盒子改为用n中颜色中的一种颜色对每一个物体涂色，则鸽巢原理可断言：如果n+1个物体用n中颜色涂色，那么必然有两个物体被涂成相同颜色。 下面介绍鸽巢原理简单形式的应用： 例题2.2.1：从1到2n的正整数中任取n+1个，则这n+1个数中至少有一对数，其中一个数是另一个数的倍数。解 证明：设所取n+1个数分别为： 对序列中的每一个数去掉一切2的因子，直至剩下一个奇数为止。例如，68=2×34=22×17，去掉2的因子22，留下奇数17，结果得到由奇数组成的序列： …… (R) 1到2n中只有n个奇数，故序列(R)中至少有两个是相同的。设为： ，对应地有： ， ，若 ＞ ，则 是 的倍数。 例题2.2.2：设 是正整数序列，则至少存在整数 和 ， ＜ ，使得和： 是 的倍数.（即，在序列 中存在连续个 ，这些 之和能被 整除）。解 例题2.2.3：设 是3个任意整数, 是 的任一排列，则 至少有一个是偶数。 解： 例题2.2.4（中国余氏定理）令 和 为二互素的正整数，并令 和 为两整数，且 0≤ ≤ 以及0≤ ≤ 。于是，存在一个整数 ，使得 除以 的余数为 ，并且 除以 的余数为 ；即 可以写成 的同时又可以写成 的形式，这里 和 是两个整数。 解： 2.3鸽巢原理的推广形式（也称加强形式） 定理2.2 令 为正整数。如果将 个物体放入盒子内，那么，或者第一个盒子至少含有 个物体，或者第二个盒子至少含有 个物体，……, 或者第 个盒子至少含有 个物体 。 证明： [注]： ⑴鸽巢原理的简单形式是由其加强形式通过令 而得到的。 ⑵鸽巢