抽屉原理论文

1、摘 要 抽屉原理是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重 要类型之一，在数论和组合论中有着广泛的应用。 本文简单介绍了抽屉原理的几种形式，便于了解抽屉原理到底是什么东西。本文 主要研究抽屉原理的抽屉构造和原理的应用。构造主要研究抽屉原理经常使用的几种 构造方式：分割图形构造法，整数性质构造法（同余类构造法、划分数组构造法） ，间 接转换构造法（染色体构造法） 。应用主要从数学领域的应用和现实生活中的应用两大 方面进行研究，数学领域方面主要应用于数论，代数，几何等几方面的解题，现实生 活中大多数用于电脑算命，预测某些存在性的结果等等。 关键词：抽屉原理；“抽屉”的构造；抽

2、屉原理的应用 Abstract Drawer principle is a mathematical combination of problem of the existence of one of the basic principles of non conventional problem solving method, is also one of the important types in number theory and combinatorics, has a wide range of applications. This paper briefly introduces

3、 the principle of drawer in several forms, easy to understand the drawer principle is what. This paper mainly studies the principle of drawer drawer structure and the application of the principle. Tectonic research drawer principle often use several construction methods: segmentation graph construct

4、ion method, construction method of integer properties ( congruence class construction method, construction method of dividing the array ), indirect conversion method of construction ( chromosome construction method). Application mainly from the mathematical field of application and the reality of li

5、fe in the application of the two major aspects of research, mathematical fields mainly used in number theory, algebra, geometry and so on several aspects of the problem solving, in real life, most used computer fortune-telling, predict some existence results etc. Key words： Drawer Principle； drawer

6、tectonic drawer；principle application 目 录 1 1 引引 言言 .1 2 2 抽屉原理抽屉原理 .1 2.1 抽屉原理概述 .1 2.1.1 抽屉原理的几种常见形式 .1 2.1.2 抽屉原理的其他特殊形式.3 2.2 抽屉原理的构造及其常用的几种构造方式 .3 2.2.1 利用分割图形的方法构造抽屉.4 2.2.2 利用整数性质来构造抽屉 .5 2.2.3 利用间接转换的方法来构造抽屉 .6 2.2.4 利用对称性构造抽屉 .7 3 3 抽屉原理的应用抽屉原理的应用 .8 3.1 抽屉原理在数学领域的应用 .8 3.1.1 应用于数论问题.9 3.1.

7、2 应用于几何问题.10 3.1.3 应用于代数问题.10 3.1.4 应用于组合问题.11 3.1.5 应用于数学奥赛.11 3.2 抽屉原理在生活中的应用 .13 4 4 总总 结结 .13 谢谢 辞辞 .14 参参 考考 文文 献献 .15 抽屉原理及其应用 1 引 言 抽屉原理是离散数学中的一个重要原理，在数论和组合论中有着广泛的应用，是 处理存在性问题的一个重要方法。抽屉原理又叫个鸽笼原理，它由德国数学家狄利克 雷（Dirichlet，1805-1859）首先发现，因此又叫作狄利克雷原理。抽屉原理是组合 数学中一个最基本的原理，在组合数学的发展中起到了至关重要的作用。狄利克雷在 研究

8、数论的问题时最早很巧妙的运用抽屉原理去解决问题。后来德国数学家闵可夫斯 基（Minkowski，1864-1909）也运用这一原理得到一些结果。到了 20 世纪初期杜尔 （A Thue，1863-1922）在不知道狄利克雷和闵夫斯基的工作情况下，很机巧的利用鸽 笼原理来解决不定方程的有理数解的问题，有 12 篇论文用到这个原理。后来西根 （C.L.Siegel，1896-？）利用杜尔的结果发现了现在称为西根引理的东西，这个引理 是研究超越数时最基本的必要工具。在数学的学习研究中，我们可以把抽屉原理看作 是一种重要的非常规的解题方法，应用它能解决许多涉及存在性的数学问题。 2 抽屉原理 2.1

9、抽屉原理概述 抽屉原理有时也被称为“鸽巢原理” ， “邮箱原理” ， “重叠原则” ， “狄利克雷原理” 等等，它是组合数学中一个重要的原理。 2.1.1 抽屉原理的几种常见形式 (1)把 5 个苹果放到 4 个抽屉中，必然有一个抽屉中至少有 2 个苹果，这是抽屉原 理的通俗解释。 若有 10 个苹果，而只有 9 个抽屉，则必然有一个抽屉中至少有 2 个苹果，依次类 推，我们可得到抽屉原理的另一种较规范的形式，即： 若把个苹果放到个抽屉中，必然有一个抽屉中至少有 2 个苹果。1n+n 我们用简单的数学语言可以把上述原理描述为：将个物品放入个盒子中，1n+n 则至少有一个盒子中装的物品数不少于

10、2 个，即必存在一个盒子中装有至少两个或更 多的物品。 （2）若将个盒子看作是有限集合的个子集，看作是集合的元素个数，nAn1n+A 则我们可以把上述原理描述为以下形式： 设是有限集，且=，则必有正整数AniAAnA i ,.,2 , 1, 1 1 n i i A = A ，使得。 nkk12 k A （3）由以上的原理我们又可以把抽屉原理描述为下面这个形式：若把个苹1kn+ 果放入个盒子里，则必有一个盒子中至少有个苹果。n1k + 即：若将个物品放入个盒子中，则至少有一个盒子中至少有 个物 1 11 rnnr 品。 设是个整数，而且，则 2 n mmm,., 21 n1 . 21 r n m

11、mm n 中至少有一个数不小于 。 n mmm,., 21 r 即：设是有限集，且=，则必有正整AniAArnA i ,.,2 , 1, 11 1 n i i A = A 数，使得。nkk1rAk （4）假如，有个苹果，把它们放入个抽屉里面，则必有一个抽屉里至少有mn 个苹果。1 1 n m 证明：反证法，如果一个抽屉里面至多放个苹果，则个抽屉里面的苹果 n m1 n 数不超过1 1 m n m n 与已知的个苹果矛盾。即必有一个抽屉里面至少有个苹果。m1 1 n m 若把看作是有限集合的元素个数，看作是集合的个子集，则我们又可以mAnAn 把上述原理表示为：设是元集，且，则必有正整A2mmn

12、iAAi,.,2 , 1 =1 = n i i A A 数，使得nkk11 1 n m Ak （5）假设有个苹果，有标号为的抽屉，则存在至少1. 21 nqqq n n,.,3 , 2 , 1 一个标号为的抽屉里面至少有个苹果，j j pnj,.,3 , 2 , 1 证明：反证法，假如第一个抽屉里面最多只有个苹果，第二个抽屉里面最多1 1 p 只有个苹果，第个抽屉最多只有个苹果，则个抽屉里面的苹果总1 2 pn1 n pn 数不超过 nqqqqqq nn .1.11 2121 与原假设个苹果矛盾。即上述原理成立。即：设是有限1. 21 nqqq n A 集都是正整数。如果且= n qqq,.,

13、 21 niAAnqqqA in ,.,2 , 1, 1. 21 1 n i i A = ，则必有正整数，使得.Ankk1 kk qA 2.1.2 抽屉原理的其他特殊形式 1、抽屉原理还有一种特殊的表现形式，那就是逆向抽屉原理： 把个苹果任意放入个抽屉里面，则至少有个抽屉里面的苹果数 1 2 1 nn kkn1k 一样多。 即：把个元素任意分成类，则至少有类元素的个数一样多。 1 2 1 nn kkn1k 证明：反证法，假设如果至多有类的元素一样多，那么元素个数最少的放法是k 类放 0 个元素，类放 1 个元素，类放 2 个元素，类放个元素，这样最kkkk1n- 少需要 与已知出现矛盾。 1

14、2 1 2 1 1.210 nknnkn nk 抽屉原理的形式比较多变，在具体的应用中也会有不同的变化，但本质上都是一 样的。 上述抽屉原理的证明均采用反证法，这种证明方法对于证明元素个数多于抽屉个数 的问题时具有普遍意义。 2.2 “抽屉”的构造 通过了解抽屉原理的形式，我们可以利用它的特殊形式来解决不同的问题。首先， 必须明确题目中应该以什么为抽屉，什么为物品；其次，构造合适的抽屉，需要注意 的是抽屉的数量一定要少于物品的数量。最后，运用抽屉原理解决问题。其中，最重 要最有难度的就是如何构造抽屉，构造抽屉是运用抽屉原理解题的关键，下面介绍几 种常用的构造抽屉的方法。 2.2.1 利用映射的

15、概念构造抽屉 2.2.2 利用奇偶分类构造抽屉 2.2.3 利用分割概念构造抽屉 1 1、利用剖分图形来构造抽屉、利用剖分图形来构造抽屉 本方法主要用于解决点在几何图形中的位置分布和性质问题,通常我们把一个几何 图形分割成几部分,然后把每一部分当作一个“抽屉”,每个抽屉里放入相应的元素。 通常情况下,我们分割图形构造抽屉的最好方法是等分这个几何图形,例如等分圆,正方 形等。 例： 上述例子是通过分割图形构造抽屉，在一个几何图形内有若干已知点，我们可以 根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点 进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决。 2 2、

16、利用划分数组来构造抽屉、利用划分数组来构造抽屉 利用此方法解题的关键是要明确分组的“对象”,然后将这些对象分成适当的数组,再 应用抽屉原理,问题便得以解决。 例 5：任意给定 7 个不同的整数,求证:其中必有两数之和或差是 10 的倍数。 证明：设这 7 个不同的整数分别为,它们分别除以 10 后,得到的余数是从 721 ,.,ttt 0 到 9 中的一个数。 (1)若这 7 个余数中有两个数相同:设,则为整数、qpkqtkpt ji 10,10 即存在两数之差是的倍数。的倍数，是即10,10 jiji ttqptt10 (2)若这 7 个余数中任何两个都不同,由抽屉原理知,至少有一数被 10

17、 除余数为 6、7、8、9 四个数中的一个。 将余数为 6 的数与余数为 4 的数划为一组,余数为 7 的数与余数为 3 的数划为一组,余 数为 8 的数与余数为 2 的数划为一组,余数为 9 的数与余数为 1 的数划为一组。于是便 有,这 7 个不同的余数,除 0,5 外,其余的必有一组数它们做和是 10 的倍数。 3 3、利用划分集合来构造抽屉、利用划分集合来构造抽屉 例 6： 2 2在 1,4,7,10,13，100 中任选出 20 个数，其中至少有不同两组数， 其和都等于 104，试证明之。 证：给定的数共有 34 个，其相邻两数的差均为 3，我们把这些数分成如下 18 个不 相交的集

18、合且把它们看作是个抽屉，从已知的 1524,1007,9749,55，18 34 个数中任选个数，即使把前两个抽屉中的数 1 和 52 都取出，则剩下的个数在2018 后面的个抽屉中至少有不同的两个抽屉中的数全部被取出，这两个抽屉中的数互不16 相同，每个抽屉中的两个数的和都是 104。 4 4、利用等分区间来构造抽屉、利用等分区间来构造抽屉 2.2.4 利用余数概念构造抽屉 把所有的整数按照除以某个自然数 m 的余数分为 m 类，叫做 m 的剩余类或同余类， 在抽屉原理利用整除关系解决问题时，常常用剩余类作为抽屉，根据抽屉原理，可以 证明任意个整数中，必有两个自然数之差是的倍数。n1n 例

19、3：证明任取 8 个自然数，必有两个数的差是 7 的倍数。 证明：任一个整数被 7 除后的余数只有可能是 0 到 6 这 7 个自然数中一个。把这 7 个自然数看成是 7 个抽屉，则 8 个整数中必有两个整数被 7 除后的余数落在同一个抽 屉里面，即必有至少两个整数除以 7 的余数相等。则这两个数的差必然是 7 的倍数。 例 4： 1 1 证明任意五个整数中,必有三个整数的和是 3 的倍数。 证明：任一整数被 3 除余数只可能是 0,1,2。若给定的五个整数被 3 除所得的余数 中 0,1,2 都出现,那么余数分别为 0,1,2 的三个数的和一定能被 3 整除；如果余数中至 多只出现 0,1,

20、2 中的两个,那么由抽屉原理,其中必有一个余数至少出现三次。而这余 数相同的三个数的和一定能被 3 整除。 注:对于如何解决有关整除的存在性问题,通常情况下,我们对模 n 进行同余分 类,继而造 n 个抽屉。即以 n 为模,可将整数集分为“余 0 类” 、 “余 1 类”,“余 n-1 类”共 n 只抽屉。然后应用抽屉原理,原问题便得以解决。 A6 A5 A4 A3 A2 A1 A6 A5 A4 A3 A2 A1 2.2.4 利用不大于 n 的正整数构造抽屉 2.2.4 利用间接转换关系构造抽屉 即通过间接转换的方式,把原问题转换为一类容易解决的新问题,继而通过对新问 题的求解,间接的来解决原

21、问题。 例 8：17 个科学家中每个人与其余 16 个人通信，他们通信所讨论的仅有三个问题， 而任两个科学家之间通信讨论的是同一个问题。证明：至少有三个科学家通信时讨论 的是同一个问题。 解：不妨设 A 是其中一位科学家，他与其余 16 位讨论的问题只有三个，把三个问 题看作三个抽屉，16 位科学家看作 16 个苹果，则由抽屉原理知，16 位科学家中至少 有 6 位科学家与科学家 A 讨论同一问题。 设这 6 位科学家为，讨论的是甲问题。 123456 ,A A A A A A 若这 6 位中有两位之间也讨论甲问题，则结论成立。 否则他们 6 位只讨论乙、丙两问题。这个问题就是相当于“六人集会

22、问题” 。从而 我们可以设为 6 个点，两者只讨论乙问题，他们之间用红色线段表 123456 ,A A A A A A 示，两两讨论丙问题，他们之间用蓝色线段表示，那么把从出发的 5 条线段， 1 A 12 A A ，放入红，蓝两个抽屉中，根据抽屉原理知，一定至少有 3 条 13 A A 14 A A 15 A A 16 A A 线段同色不妨设线段，都为红色考虑线段， 12 A A 13 A A 14 A A 23 A A 24 A A 34 A A 分以下两种情况： （1）若，都是蓝色，则三角形的三边同为蓝色，如图 23 A A 24 A A 34 A A 234 A A A （3） ，这就

23、是说三者互不认识 234 ,A A A （2）若，中至少有一条为红色，不妨设为，如图（4） ，则 23 A A 24 A A 34 A A 23 A A 三角形的三边同为红色，即三者互相不认识 123 A A A 123 ,A A A （3） 实线表示红色，虚线表示蓝色 （4） 我们可以得到证明的结果，即至少有三个科学家通信时讨论的是同一个问题。 上述例子也属于利用染色制造抽屉，染色问题的实质是分类，只不过题目以涂色 形式出现，显得直观而已 抽屉原理的应用非常广泛,本文只介绍了抽屉原理几种常见的构造方法,其实还有 一些其他的构造方法，例如奇偶性构造法、等分区间构造法等等。在解决同一道抽屉 原理

24、的题时,并不是只有一种构造抽屉原理的方法,只有接触更多的不同形式的问题并 加以解决才能学好抽屉原理。 总而言之，应用抽屉原理解题需要很强的灵活性，不过也有其解题的步骤，步骤 如下：第一步：分析题意。分清什么是“东西”，什么是“抽屉”，也就是什么作 “东西”，什么可作“抽屉”。第二步：构造抽屉。这个是关键的一步，这一步就是 如何设计抽屉。根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系， 设计和确定解决问题所需的抽屉及其个数，为使用抽屉原理铺平道路。第三步：运用 抽屉原理。观察题设条件，结合第二步，恰当应用各个原则或综合运用几个原则，达 到问题的解决。 3 抽屉原理的应用 抽屉原理在

25、各个领域都有一定的应用，这里简单介绍一下在数学领域及在生活中 的应用。 3.1 抽屉原理在数学领域的应用 一般地说，用抽屉原理来解决的数学问题有如下特征：新给的元素具有任意性， 如八个苹果放入七个抽屉，可以随意的一个抽屉放几个，也可以让抽屉空着，问题的 结论是存在性命题，题中常含有“至少有”，“一定有”，“不少于”， “存在”，“必然有”等词语，其结论只要存在，不必确定前面的内容已 经介绍了一些常用的构造抽屉的方法，这对我们的解题有很大的帮助。下面介绍几种 应用抽屉原理的情况。 3.1.1 利用抽屉原理证明不等式 1、证明代数不等式 2、证明三角不等式 3.1.2 利用抽屉原理解决逻辑问题利用

26、抽屉原理解决逻辑问题 例 12：在对角线为 50 米的长方形草坪上，有 10 个同学在踢足球，无论他们怎么 跑动，求至少会有两个同学之间的距离不会超过多少米？ 解：我们把大的长方形按长和宽同时等 分的方式分割成 9 个小长方形，如图所示由 抽屉原理可知，把这 9 个小长方形看作是 9 个抽屉，则至少有两个同学在一个小长方 形里面。即他们之间最大的距离不超过小长方形的对角线长度米，即无论这十个同 50 3 学怎么跑，其中至少有两个同学的距离不会超过米。 50 3 3.1.3 利用抽屉原理解答数学奥赛题 1 1、连续多次运用抽屉原理、连续多次运用抽屉原理 例 16：2一个国际社团的成员来自六个国家

27、共 1978 人，用 1，2，,，1977,1978 来编号，试证明：该社团至少有一个成员的编号或者与他的两 个同胞的编号之和相等，或者是其中一个同胞的编号的两倍。（第 20 届 IMO） 证：可以用反证法来证明与本题完全相当的下列问题：把数列 1，2，,，1977,1978 按任一方式分成六组，则至少有一组具有这样的性质：其中有 一个数或等于同组中其他两数之和，或等于其中某一个数的两倍。 假设这六组中的每一组数都不具备上述性质，也就是说每一组数都具备下列性质， 记作性质： P 同组中任何两个数的差必不在此组中。 因为如果连同都在同一组中，那么由可知，这组已具备题, a bba baba 目所

28、要求的性质。 因，所以由抽屉原理可以肯定有一个组 A，其中至少有 330 个正整32961978 数，现在从 A 中任意取出 330 个数来，记其中最大的那个数为,把分别减去其余 1 a 1 a 329 个数而得到 329 个差，它们互不相等且均小于 1978，由性质（P），它们不会再在 组 A 中，即应属于其余五个数组，又因，再由抽屉原理可以肯定有一组655329 B，其中至少含有上述 329 个数中的 66 个数，从 B 中任取 66 个数且记其中的最大的那 个数为，再把减去其余的 65 个数，得出的差显然不再属于 B，当然也不会属于 1 b 1 b A。 假如其中的某一个数属于 A，由于

29、与分别可以写成 bb 11 bb, 111 aabaab 其中与都属于 A，于是a a aaaaaabb 111 这就同 A 具备的性质（P）的假设相违背，这就是说上述 65 个数必属于其余四个 数组。 由于，所以至少有一组，称为 C，至少会有上述 65 个整数中的 17 个，16465 反复进行上述推理，最后可得一数组 F，其中至少会有两个数，大数与小数之差是一个 小于 1978 的自然数，可是它不在 A,B,C,D,E,F 的任何一组中，这显然是一个矛盾。这 矛盾说明至少有一组数不具备性质，即题目的结论是正确的。 P 我们容易发现，如果把题目中的 1978 改成任何一个不小于 1957 的

30、正整数后其结 论仍是成立的。此例的解答过程说明了对有的数学问题需要我们连续运用抽屉原理， 而且每构造一次抽屉都把范围缩小一些。 2 2、逆向运用抽屉原理、逆向运用抽屉原理 例 17：从 1、2、3、4、12 这 12 个自然数中，至少任选几个，就可以保证其 中一定包括两个数，他们的差是 7? 解：在这 12 个自然数中，差是 7 的自然数有以下 5 对:12，5,11，4, 10，3,9，2,8，1 。另外，还有 2 个不能配对的数是6,7 。只要有两个数 是取自同一个集合，那么它们的差就等于 7。 把这 7 个集合看成 7 个抽屉，则由抽屉原理知，任取 8 个数，就可以保证其中有 两个数的差

31、是 7； 即使把 6 跟 7 全部选出，由抽屉原理可知，从其余的 5 个抽屉中取 6 个元素，则 一定可以使有两个元素来源于同一个抽屉，即至少任取 8 个数，可以保证其中一定有 两个数的差为 7。 综上所述，从这 12 个自然数中，至少任选 8 个数，就可以保证其中一定包括两 个数，他们的差是 7. 3.2 抽屉原理在生活中的应用-招生录取问题 其实，抽屉原理不仅在数学中有用，在现实生活中也到处在起作用，如招生录取、 就业安排、资源分配、职称评定等等，都不难看到抽屉原理的作用。下面简单的举几 个例子：370 个同学中必有至少 2 个人的生日是同一天；4 双不同颜色的筷子中必须取 出 5 枝筷子

32、才能保证其中至少有一双筷子是同颜色的；13 个人中必有两个人的生肖是 一样的等等。 4 总 结 抽屉原理叙述起来比较简单，因此本文将重点放在了抽屉原理的应用，尤其是构 造抽屉的几种方法，这是灵活应用抽屉原理的关键 总而言之，应用抽屉原理也有其解题的步骤，步骤如下： 第一步：分析题意。分清什么是“东西”，什么是“抽屉”，也就是什么作“东西”， 什么可作“抽屉”。 第二步：制造抽屉。这个是关键的一步，这一步就是如何设计抽屉。根据题目条件和 结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需的抽 屉及其个数，为使用抽屉铺平道路。 第三步：运用抽屉原理。观察题设条件，结合第二步，恰当应用各个原则或综合运用 几个原则，以求问题之解决。