1、 6 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 把 10 个苹果放进 9 个抽屉中，无论怎么放，一定能找到一个抽屉，里面至少有 2 个 第第十三十三讲讲 简单抽屉原理简单抽屉原理 7 苹果这个看上去很显然的现象，在数学中我们把它称作抽屉原理 一般地，我们有如下结论： 抽屉原理 I 把一些苹果随意放入若干个抽屉，如果苹果个数多于抽屉个数，
2、那么一定能找到一个 抽屉，里面至少有 2 个苹果 以 9 个抽屉为例：把 9 个苹果放进 9 个抽屉，这时苹果个数不多于抽屉个数，如果苹 果平均放进抽屉中，则每个抽屉都只放了 1 个苹果但如果把 10 个苹果放进 9 个抽屉， 这时苹果个数多于抽屉个数，一定能找到一个抽屉，里面至少有 2 个苹果因为即使每个 抽屉都放 1 个苹果时，也只能放进1 99个苹果，剩下的 1 个苹果再放进任何一个抽屉， 都会使该抽屉中有 2 个苹果 类似的，把 99 个苹果放进 9 个抽屉，苹果个数多于抽屉个数，一定能找到一个抽屉， 里面至少有 2 个苹果事实上，我们还可以发现：如果这 99 个苹果平均放进 9 个抽
3、屉中， 每个抽屉里放99911个苹果， 如果放得不平均， 则肯定有某个抽屉里的苹果多于 11 个 但 如果把 100 个苹果放进 9 个抽屉，即使每个抽屉都放 11 个苹果，只能放 99 个苹果，剩下 1 个苹果再放进抽屉中，一定会使得某个抽屉至少有 12 个苹果 我们把“抽屉原理 I”加以推广，就可以得到一个更全面的抽屉原理 抽屉原理 II 把 m 个苹果放入 n 个抽屉（m 大于 n） ，结果有两种可能： （1）如果mn没有余数，那么就一定有抽屉至少放了“mn”个苹果； （2）如果mn有余数，那么就一定有抽屉至少放了“mn的商再加 1”个苹果 抽屉原理也称“鸽巢原理”或“狄利克莱原理” ，
4、是 19 世纪德国数学家狄利克莱最早 提出的，在组合数学中有着非常重要的地位 回想刚才得出抽屉原理的过程，在计算时我们都使用了平均分配的思想为什么要平 如果把 96 个苹果放入 8 个抽屉，那么一定有抽屉至少放了_个苹果 如果把 97 片培根放在 8 个盘子，那么一定有盘子至少放了_片培根 如果把 98 只羊放在 8 个笼子里，那么一定有笼子至少放了_只羊 练练 一一 练练 8 均分呢？因为只有这样做才能使得放入同一个抽屉的苹果尽量少，求出的结果才是至少 几 个虽然我们算的是分到同一个抽屉的苹果，但考虑的时候却是让同一抽屉中的苹果尽量 少这种从反面考虑的分析方法又叫做“最不利原则” ，即考虑最
5、坏的情形这一原则 不仅体现在抽屉原理中，它还在解决很多与“至多” 、 “至少”相关的问题时非常有用 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 分析：如果没有满足“有 5 条相同品种的鱼”的要求，最“倒霉”的情况是什么？换句话说，当结论不 成立时，最多可能有多少条鱼？只要比这个“最多的”还要多，结论就肯定成立了 分析：仍旧考虑问题的反
6、面，当本题中的结论不成立时，最多能取出多少个球？ 练习 2 爷爷给小明买了一盒糖， 这些糖分为苹果味、 桔子味和菠萝味三种口味， 每种口味各 30 颗 小 明特别喜欢吃苹果味的，他闭着眼睛，至少需要摸出多少颗糖，才能保证一定能拿到 1 颗苹果味 的？至少需要摸出多少颗糖，才能保证能拿到两种口味的糖？ 一个布袋里有大小相同颜色不同的一些木球，其中红色的有 10 个，黄色的有 8 个，蓝色的有 3 个，绿色的有 1 个现在闭着眼睛从中摸球，请问： （1）至少要取出多少个球，才能保证取出的球至少有三种颜色？ （2）至少要取出多少个球，才能保证其中必有红球和黄球？ 例题 2 练习 1 一个布袋里有 7
7、 种不同颜色的彩球，每种颜色的彩球都有很多，那么至少要拿出多少个彩球， 才能保证其中有 6 个相同颜色的彩球？ 一个鱼缸里有 4 个品种的鱼，每种鱼都有很多条至少要捞出多少条鱼，才能保证其中有 5 条相同品种的鱼？ 例题 1 9 分析：结论的反面是什么？在不满足结论的情况下，最多能摸出多少只袜子？ 分析：本题中我们要保证“至少包含三种花色”和“这三种花色的牌至少都有 3 张”这两 个条件，如果不能同时保证这两个条件，那么最多可能取出多少张牌？ 分析：摸出的 4 枚棋子的颜色情况都有哪几种？如果结论不成立，最多可能摸了几次？ 大头把一副围棋子混装在一个盒子中（围棋子有黑、白两种颜色） ，然后每次
8、从盒子中摸出 4 枚棋子，那么他至少要闭着眼睛摸几次，才能保证其中有三次摸出棋子的颜色情况是相同的？（不 必考虑每次摸出的 4 枚棋子的顺序） 例题 5 练习 4 口袋中装有 4 种不同颜色的珠子，每种都是 100 个要想保证从袋中摸出 3 种不同颜色的珠 子，并且每种至少 10 个，那么至少要摸出多少个珠子？ 一副扑克牌共 54 张，其中有 2 张王牌，还有黑桃、红心、草花和方块 4 种花色的牌各 13 张现 在要从中随意取出一些牌，如果要保证在取出来的牌中至少包含三种花色，并且这三种花色的牌至 少都有 3 张，那么最少要取出多少张牌？ 例题 4 练习 3 袋子里白袜子、黑袜子、红袜子各 1
9、0 只现在闭着眼睛从袋子中摸袜子，请问： （1）至少要摸出多少只袜子才能保证一定有颜色相同的两双袜子？ （2）至少要摸出多少只袜子才能保证一定有颜色不同的两双袜子？ 将 1 只白袜子、2 只黑袜子、3 只红袜子、8 只黄袜子和 9 只绿袜子放入一个布袋里请问： （1）一次至少要摸出多少只袜子才能保证一定有颜色相同的两双袜子？ （2）一次至少要摸出多少只袜子才能保证一定有颜色不同的两双袜子？（两只袜子颜色相同即为 一双） 例题 3 10 分析：至少有 3 个格子里的米粒一样多的反面是最多只有 2 个格子的米粒数一样多，想想 这时格子里至少有多少个米粒？ 国王让阿凡提在8 8的国际象棋棋盘的每个格
10、子里放米粒结果每个格子里至少放一粒米， 无论怎么放都至少有 3 个格子里的米粒一样多，那么至多有多少个米粒？ 例题 6 鸽巢原理 鸽巢原理鸽巢原理又名抽屉原理抽屉原理或狄利克雷原理狄利克雷原理，它由德国数学家狄利克雷(Divichlet，18051855) 首先发现鸽巢原理在组合学中占据着非常重要的地位，它常被用来证明一些关于存在性的数学 问题，并且在数论和密码学中也有着广泛的应用使用鸽巢原理解题的关键是巧妙构造鸽巢或抽 屉，即如何找出合乎问题条件的分类原则鸽巢原理的应用在几何图形中： 例：例：在边长为在边长为 2 的等边三角形内任意选择的等边三角形内任意选择 5 个点，存在个点，存在 2 个
11、点，其间距离至多为个点，其间距离至多为 1 分析：由题意，可以构造出 4 个抽屉，每个抽屉满足在其中的距离至多为 1根据抽屉原理，在 4 个抽屉里分别放置 4 个点，不论第 5 个点如何放置，都满足两点之间的距离最多为 1 小小 故故 事事 11 作业作业 1. 口袋里装有红、黄、蓝、绿 4 种颜色的球各 5 个小华闭着眼睛从口袋里往外摸球，每次摸出 1 个球他至少要摸出多少个球，才能保证摸出的球中每种颜色的球都有？ 2. 小钱的存钱罐中有 4 种硬币：1 分、2 分、5 分、1 角，这四种硬币分别有 5 个、10 个、15 个、 20 个小钱闭着眼睛向外摸硬币，他至少摸出多少个硬币，才能保证
12、摸出的硬币中至少有两种不同的 面值？至少摸出多少个硬币，才能保证摸出的硬币中既有 5 分硬币也有 1 角硬币？ 3. 如果筷子颜色有黑色、白色、黄色、红色、蓝色五种，每种各有 10 根在黑暗中取出一些筷 子， 为了搭配出两双颜色相同的筷子， 最少要取多少根才能保证达到要求？为了搭配出两双颜色不同的 课课 堂堂 内内 外外 晏子春秋里有一个“二桃杀三士”的故事齐景公养着三名勇士，他们名叫田开疆、 公孙接和古冶子这三名勇士都力大无比，武功超群，为齐景公立下过不少功劳但他们也刚 愎自用，目中无人，得罪了齐国的宰相晏婴晏子便劝齐景公杀掉他们，并献上一计：以齐景 公的名义赏赐三名勇士两个桃子，让他们自己
13、评功，按功劳的大小吃桃 三名勇士都认为自己的功劳很大，应该单独吃一个桃子于是公孙接讲了自己的打虎功， 拿了一只桃；田开疆讲了自己的杀敌功，拿起了另一桃两人正准备要吃桃子，古冶子说出了 自己更大的功劳公孙接、田开疆都觉得自己的功劳确实不如古冶子大，感到羞愧难当，赶忙 让出桃子并且觉得自己功劳不如人家，却抢着要吃桃子，实在丢人，是好汉就没有脸再活下 去，于是都拔剑自刎了古冶子见了，后悔不迭仰天长叹道： “如果放弃桃子而隐瞒功劳， 则有失勇士尊严；为了维护自己而羞辱同伴，又有损哥们义气如今两个伙伴都为此而死了， 我独自活着，算什么勇士！ ”说罢，也拔剑自杀了 晏子采用借“桃”杀人的办法，不费吹灰之力
14、，便达到了他预定的目的，可说是善于运用 权谋汉朝的一位无名氏在一首诗中曾不无讽刺的写道： “一朝被谗言，二桃杀三士谁 能为此谋，相国务晏子！ ” 值得指出的是，在晏子的权谋之中，包含了一个重要的数学原理抽屉原理 在“二桃杀三士”的故事中，把两个桃子看作两个抽屉，把三名勇士放进去，至少有两名 勇士在同一个抽屉里，即有两人必须合吃一个桃子如果勇士们宁死也不肯忍受同吃一个桃子 的羞耻，那么悲剧的结局就无法避免 二桃杀三士二桃杀三士 12 筷子，最少要取多少根才能保证达到要求？（两根颜色相同的筷子搭配成一双筷子） 4. 盒子里一共有 4 种不同形状的零件， 分别有 9、 10、 11 和 12 个，
15、至少要从中摸出多少个零件， 才能保证有 3 种不同形状的零件，并且这三种零件中每种至少有 3 个？ 5. 中午放学，食堂里有五种菜供学生们选择，每人只能选两种不同的菜至少有多少名学生，才 能保证其中至少有 5 名学生选择的菜完全相同？ 13 第十三讲 简单抽屉原理 1. 例题 1 答案：17 解答：17最不利情况是没有 5 条相同品种的鱼，这时最多每个品种都有 4 条鱼，一共44 16 条只要比 16 条多，就能保证有 5 条相同品种的鱼了因此至少捞出 17 条鱼 2. 例题 2 答案： （1）19； （2）15 解答： （1）如果取出的球没有三种颜色，最不利的情况是尽量多地取出其中的某两种，
16、红球和黄球最多，全 都取出共有10818个球只要多于 18 个，就能保证有三种颜色的球了，因此至少取出 19 个 （2）如果取出的球中红球和黄球不同时出现，最不利的情况是首先蓝球和绿球都取出，并且红球和黄球中的 一种也都取出，红球比黄球多，应将红球全部取出，此时共取出3 1 1014 个球，因此至少取出 15 个球， 才能保证红球黄球同时出现 3. 例题 3 答案： （1）13； （2）14 解答： （1） 如果没有颜色相同的两双袜子，这时每种颜色的袜子至多 3 只，一共至多1233312 只因 此至少摸出 13 只才能保证有两双颜色相同的袜子 （2）如果没有颜色不同的两双袜子，那么最不利情况
17、是成双成对的袜子都是同一种颜色的，这时最多有 91 1 1 113 只袜子因此至少摸出 14 只才能保证有两双颜色不同的袜子 4. 例题 4 答案：33 解答：反过来考虑，就是“最多只有 2 种花色的牌不少于 3 张，其余花色都不到 3 张 ”最不利的情况就要使 取的牌尽量多，我们应该将其中两种花色尽量多取、剩下两种花色都取 2 张，包括 2 张大小王牌，最多能取 13 22 2232 张牌因此至少取出 33 张才能保证满足要求 5. 例题 5 答案：11 解答：摸出的棋子的颜色情况有五种：4 白、3 白 1 黑、2 白 2 黑、1 白 3 黑、4 黑根据最不利原则，如果没 有三次摸出棋子颜色
18、情况相同，最多是每种情况各摸出 2 次，一共2 510 次只要摸的次数比 10 次多，就 能保证至少有三次摸出棋子颜色情况相同因此至少摸 11 次 6. 例题 6 答案：1055 简 答 ： 如 果 不 满 足 条 件 ， 最 多 只 有 两 个 格 子 中 的 米 粒 数 一 样 多 ， 则 64 个 格 子 里 至 少 有 1 1223332321056 个米粒如果少于 1056 个米粒，就必然有三个格子里的米粒数一样多， 因此至多有 1055 个米粒 7. 练习 1 答案：36 简答：如果不满足条件，最多可以取出7 535个彩球，因此取出 36 个彩球就能保证有 6 个颜色相同的 8.
19、练习 2 答案：61；31 简答： 第一个问题， 如果不满足条件， 拿的都不是苹果味的， 最多拿光了桔子味的和菠萝味的， 一共303060 颗因此至少拿 61 颗，才能保证拿到苹果味的第二个问题，如果拿的不到两种口味，最多一种口味，最多 可以拿 30 颗，因此至少拿 31 颗才能保证拿到两种口味 9. 练习 3 答案： （1）10； （2）13 简答： （1）至少摸出333 1 10 只袜子 （2）至少摸出10 1 2 1 13 只袜子 10. 练习 4 14 答案：219 简答：如果不满足条件，其中两种颜色的珠子尽量多，另外八种颜色的珠子都不到 10 个，这时最多可以有 100 1002 9
20、218 个珠子因此至少拿 219 个珠子，才能保证有三种颜色的珠子都至少 10 个 11. 作业 1 答案：16 简答：如果不满足要求，最多摸出三种颜色的球，最多有5 315 个因此至少摸出 16 个球就能满足要求 12. 作业 2 答案：21；36 简答：第一个问题，如果不满足要求，就只摸出一种面值的，最多 20 个，因此至少摸出 21 才能满足要求第 二个问题，如果不满足要求，5 分硬币和 1 角硬币缺一种，最多有5 102035个硬币，因此至少摸出 36 个硬币才能满足要求 13. 作业 3 答案：16；15 简答：与例题 5 方法相同第一个问题，至少取出3 5 1 16 根才能满足要求第二个问题，至少取出 10 1 4 1 15 根才能满足要求 14. 作业 4 答案：28 简答：与例题 4 方法相同，至少摸出11 1222 128 个零件才能满足要求 15. 作业 5 答案：41简答：从 5 种菜中选择 2 种不同的菜，有 10 种方式如果不满足要求，最多选出4 1040名学 生，因此选出 41 名学生即可满足要求
