第二章（Chapter 2）鸽巢原理（The Pigeonhole Principle）.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.3：设 是3个任意整数； 是 的任一排列，则 至少有一个是偶数。 解： 例题2.2.4（中国余氏定理）令 和 为二互素的正整数，并令 和 为两整数，且0≤ ≤ 以及0≤ ≤ 。于是，存在一个整数 ，使得 除以 的余数为 ，并且 除以 的余数为 ；即 可以写成 的同时又可以写成 的形式，这里 和 是两个整数。 解： 2.3鸽巢原理的推广形式（也称加强形式） 定理2.2 令 为正整数。如果将 个物体放入 盒子内，那么，或者第一个盒子至少含有 个物体，或者第二个盒子至少含有 个物体，……, 或者第 个盒子至少含有 个物体 。 证明： [注]： ⑴鸽巢原理的简单形式是由其加强形式通过令 而得到的。 ⑵鸽巢原理的加强形式可用着色的术语表述为：如果 个物体中的每一个物体被指定用 种颜色中的一种着色，那么存在一个这样的 ，使得第 种颜色的物体至少有 个。 ⑶鸽巢原理加强形式的直接表述： 只鸽子， 个鸽巢，则至少有一个鸽巢里有不少于 只鸽子。（其中， 表示的 取整，即不超过 的最大整数） ⑷在初等数学中，鸽巢原理加强形式常用于 都等于同一个整数的特殊情况。此时，该原理可叙述为： 1）如果 个物体放入 个盒子中，那么至少有一个盒子含有 个或更多个物体。 2）如果 个非负整数 的平均数大于 ，即： ＞ ，那么至少有 一个整数大于或等于 。 3）如果 个非负整数 的平均数小于 ，即： ＜ ，那么其中 至少有一个整数小于 。 4）如果 个非负整数 的平均数至少等于 ，那么这 个整数中至少有一个满足 ≥ 。 下面介绍鸽巢原理加强形式的应用： 例题2.3.1：一篮子水