5.1抽屉原理

抽屉原理问题知识点总结

抽屉原理的基本形式是：如果n个物品被放置到m个抽屉中，并且n > m，那么至少有一个抽屉中有超过一个物品。

抽屉原理的应用非常广泛，它不仅出现在数学领域，还涉及到计算机科学、逻辑学、统计学、概率论等方面。总结抽屉原理的知识点，可以从以下几个方面来展开。

一、基本概念

1. 抽屉原理的概念

抽屉原理是由德国数学家穆勒（Dirichlet）在1834年提出的。它的基本概念是指如果有n个物品要放到m个抽屉里，且n > m，那么至少有一个抽屉里面有至少两个物品。

2. 抽屉原理的表述

抽屉原理还可以用集合的交并运算来表述，即如果n个单个的数的和大于(n-1)倍的抽屉数，则必定存在多个数分配到同一个抽屉里。

3. 抽屉原理的思维方法

抽屉原理是一种常见的数学论证方法，它的核心思想是通过将物品放入抽屉的过程，然后证明必然会有至少一个抽屉中包含多个物品。这种思维方法在解决相关问题时非常重要。

二、抽屉原理的应用

1. 计算机科学

在计算机科学中，抽屉原理经常用来解决散列冲突问题。当散列表的大小是有限的时候，存储的数据项的数量可能会比散列表的大小大，这时就可能会出现散列冲突。抽屉原理可以帮助我们理解为什么散列冲突总是不可避免的。

2. 统计学

在统计学中，抽屉原理可以用来解释生日悖论。生日悖论是指在一个小的群体中，其中两人有相同生日的概率实际上要比我们直觉上想象的要高得多。这一现象可以通过抽屉原理来很好地解释。

3. 概率论

在概率论中，抽屉原理可以用来解决一些排列组合的问题。例如，如果有n+1个物品要放到n个抽屉中，那么必然有一个抽屉中至少有两个物品。这对于解决某些赌博游戏中的概率问题很有帮助。

4. 逻辑学 在逻辑学中，抽屉原理可以用来解释一些谬误和伪命题。例如，当有大于两个的命题时，就一定会出现至少两个命题具有相同的逻辑值。

三、抽屉原理的证明

1. 直接证明法

抽屉原理最简单的证明方法是使用直接证明法。假设放置的物品数大于抽屉的数量，通过逻辑推理可以得出至少有一个抽屉至少有两个物品。这是一种比较直观的证明方法，适用于绝大多数的抽屉原理问题。

抽屉原理

规律：用苹果数除以抽屉数，若除数不为零，则“答案”为商加1；

若除数为零，则“答案”为商

抽屉原则一：把n个以上的苹果放到n个抽屉中，无论怎么放，一定能找到一个抽屉，它里面至少有两个苹果。

抽屉原则二：把多于m x n 个苹果放到n个抽屉中，无论怎么放，一定能找到一个抽屉，它里面至少有（m+1）个苹果。

例1 五年级有47名学生参加一次数学竞赛，成绩都是整数，满分是100分。已知3名学生的成绩在60分以下，其余学生的成绩均在75～95分之间。问：至少有几名学生的成绩相同？

例2 夏令营组织2000名营员活动，其中有爬山、参观博物馆和到海滩游玩三个项目。规定每人必须参加一项或两项活动。那么至少有几名营员参加的活动项目完全相同？

例3把125本书分给五（2）班学生，如果其中至少有1人分到至少4本书，那么，这个班最多有多少人？

例4五（1）班张老师在一次数学课上出了两道题，规定每道题做对得2分，没做得1分，做错得0分。张老师说：可以肯定全班同学中至少有6名学生各题的得分都相同。那么，这个班最少有多少人？

例5任意将若干个小朋友分为五组。证明：一定有这样的两组，两组中的男孩总数与女孩总数都是偶数。

练习

1.某单位购进92箱桔子，每箱至少110个，至多138个，现将桔子数相同的作为一组，箱子数最多的一组至少有几箱？

2.幼儿园小朋友分200块饼干，无论怎样分都有人至少分到8块饼干，这群小朋友至多有多少名？

3.有若干堆分币，每堆分币中没有币值相同的分币。任意挑选多少堆分币，才能保证一定有两堆分币的组成是相同的？

4.图书馆有甲、乙、丙、丁四类图书，规定每个同学最多可以借两本不同类的图书，至少有多少个同学借书，才能保证有两个人所借的图书类别相同？

5.我国人口已超过12亿，如果人均寿命不超过75岁，那么我国至少有两个人出生的时间相差不会超过2秒钟。这个结论是否正确？

山东省济宁一中奥林匹克数学竞赛辅导讲义 贾广素 编写

第二章 几个重要的原理

2.1 抽屉原理

将10个苹果放在9个抽屉中，无论怎么放，一定会有一个抽屉里放了2个或更多的苹果，这个简单的事实就是抽屉原理. 它是由德国数学家狄利克雷(Dirichlet)提出来的,因此也称为狄利克雷原理.如果将苹果换成信，鸽子或鞋，而把抽屉换成信筒，鸽笼或鞋盒，那么这个原理应然适用. 它是许多存在性问题得以证明的理论依据,也是离散数学中的一个重要原理，把它推广到一般情形，就可以得到：

抽屉原理

如果将m个物品放入n个抽屉内，那么至少有一个抽屉的物品不少于l个，其中[]1mnlmn （这里[]x表示不超过x的最大整数）

【证明】当|nm时，若结论不真，则每个抽屉中至多有1mn个物品，那么n个抽屉中物品的总数(1)mnmnmn个，矛盾！

时，若结论不真，则n个抽屉中物品总数[]mmnnmnn个，也矛盾！ 当有的参考书上给出了此定理的另外一种写法：如果将m个物品放入n个抽屉内，那么必有一个抽屉内至少有1[]1mn个物品。这是抽屉原理的不同的两种表现形式，其本质是一样的。另外，抽屉原理还有其它的几种形式的推广：

推广1：如果将m个物体放入n个抽屉内，那么必有一个抽屉内的物品至多有[]mn个。

这是推广也叫做第二抽屉原理，证明如下：

【证明】用反证法，如果每个抽屉内至少有[]mn＋1个物品，那么n个抽屉内的物品的总数至少为([]1)mmnnmnn，这与n个抽屉内共有m个物品矛盾！

推广2：无穷多个物品放入有限个抽屉中，则至少有一个抽屉中有无穷多个物品。

推广3：把121nmmmn个元素分成n类，则存在一个k，使得第k类至少有||nmnm|nm山东省济宁一中奥林匹克数学竞赛辅导讲义 贾广素 编写

1 / 6

第24讲 抽屉原理二

内容概述

抽屉原理在教字、表格、图形等具体问题中有较复杂的应用．能够根据已知条件合理地选取和设计“抽屉”与“苹果”，有时还应构造出达到最佳状态的例子．

典型问题

兴趣篇

1．将60个红球、8个白球排成一条直线，至少会有多少个红球连在一起？

答案：7

详解：60÷（8＋1）=6„„6,6＋1=7个。

2．17名同学参加一次考试，考试题是3道判断题（答案只有对或错），每名同学都在答题纸上依次写上了3道题目的答案．请问：至少有几名同学的答案是一样的？

答案：3

详解：答案的结果有23=8种情况，即8个抽屉。17÷8=2„„1，2＋1=3名。

3．任意写一个由数字1、2组成的六位数，从这个六位数中任意截取相邻两位，可得一个两位数，请证明：在从各个不同位置上截得的所有两位数中，一定有两个相等．

详解：两位数的情况共4种：12,21,11,22。六位数可以截取出5个两位数，所以必有重复。

4．将1至6这6个自然数随意填在图2，4-1的六个圆圈中，试说明：图中至少有一行的数字之和不小于8。

详解：1＋2＋3＋4＋5＋6＋7=21,21÷3=7，图形总共有3行，第一行只有一个数，最大填6，那么后两行至少有一行是大于7的整数，即不小于8。

5．从l，2，3，„，99，100这100个数中任意选出51个数，请说明：

(1)在这51个数中，一定有两个数的差等于50；

详解：构造差为50的抽屉：（1,51）、（2,52）、„„、（50,100），共50个抽屉。选出51个数，必有两数来自一组，即差为50.

(2)在这51个数中，一定有两个数差1．

详解：构造差为 1的抽屉：（1,2）、（3,4）、„„、（99,100），共50个抽屉。必有两数来自一组，即差为1.

2 / 6

6．从1，2，3，„，21这些自然数中，最多可以取出多少个数，使得其中每两个数的差都不等于4？