抽屉原理及应用

论文总字数：9408字

摘 要

关键词：抽屉原理，数论，应用

Abstract：Drawer principle is one of the two basic principles in combinatorics, and it is a mathematical principle which is very elementary but involving wider application. In this paper,we introduced the principle of drawers in simple way, and highlighted its application in algebra, geometry, and other aspects.

Keywords：drawer principle, number theory, application

目 录

1 引言 4

2抽屉原理概述 4

3 抽屉原理的应用 5

3.1 抽屉原理在数论中的应用 5

3.2 抽屉原理在群论中的应用 9

3.3 抽屉原理在图论中的应用 9

3.4抽屉原理在几何学中的应用 11

3.5利用抽屉原理简证不等式 12

结论 14

参考文献 15

致谢 16

1 引言

抽屉原理是由Dirichlet（狄利克雷）归纳出的一个重要而基本的组合学中的原理，常称为鸽巢原理或Dirichlet原理，它的直观意义是，当鸽子比笼子多时，鸽子归笼时则有的笼子会多于1只鸽子.

这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的问题，得到一些很重要的结论，它是非常规数学解题方法的重要类型，因此数学竞赛中经常选用这方面的题目.

本文全面而系统的归纳总结了抽屉原理在不同方面的简单应用，通过巧妙应用抽屉原理解决数学上以及日常生活中的一些问题.

2 抽屉原理概述

抽屉原理有多种表述形式，但是概括起来主要有以下两种

原理1 设个元素按任一确定的方式分成个集合，如果,那么必有一个集合至少含有两个元素.

原理2 把个物体放入个抽屉中，其中必有一个抽屉中至多有个物体.

原理 3 若将个物品放入个盒子中，则至少有一个盒子中有不少于个物品.其中是不小于的最小整数.

例1 某次演出有个演员参加演出，每个演员除自己以外至少认识其余个中的一个，则在这个演员中，至少有2个演员认识的人数相等.

证明 个演员按认识的人数分类.他们认识的人数分别是1，2，.将个演员视为个元素，将按认识的人数的多少分成类，视为个盒子，则至少2个演员认识的人数在同一类中，即他们认识的人数相等.

事实上，用集合语言叙述更明白，个演员为集合，按他们认识的人数相同时分在同一个子集，从而将划分成个不交子集的并，则必有其子集的“元素”多于2个，即至少有2个认识的人数相等.

例2 一篮子水果中装有苹果、梨子和桃子，为了保证篮子内或者至少装有8个苹果，或者至少装有6个梨子，或者至少装有9个桃子，则放入篮中的水果最少个数是多少？

解 由抽屉原理1可知，无论怎样装入，8 6 9-3 1=21个水果将保证篮子内的水果满足所要求的性质，但7个苹果，5个梨子和8个桃子，即总数为20的水果不能满足所要求的性质.

评注 抽屉原理只是断言存在一个盒子，该盒中有两个或两个以上的物品，但它并没有指出是哪个盒子，要想知道是哪个盒子，则只能逐个检查这些盒子.

3 抽屉原理的应用

3.1 抽屉原理在数论中的应用

在初等数论中，很多问题都可以看作存在性问题，所以可以考虑利用抽屉原理进行解决，利用抽屉原理解决数论问题时常常是利用整数的性质来制造抽屉的.

例3（中国余式定理）设为两个互素的正整数，是满足的整数.证明：存在正整数，使得除以的余数为，除以的余数为，即可以写成的同时又可以写成的形式，这里和是整数.

证明 考虑以下个整数这个整数除以的余数是都是.若这个数中存在两个数除以的余数相同，设为.设这两个数为和，其中，则存在整数，使得

(1)

和

(2)

同时成立.将式（1）减去式（2），就可以得到

. (3)

从式（3）可以看出，是的一个因子，而由题设条件可知，互素，它们的最大公因子为1，因此，是的因子.由前面的推导过程有，从而,也就是说不可能是的因子，矛盾.所以

这个数除以的余数互不相等，而所有的整数除以的余数只有这个数.依据抽屉原理1，除的余数取遍这个数.特别地，数也是如此，对于，令为整数，满足，使得除以的余数为，即存在整数，有.

综上所述，，满足例题中要证明的结论.

例4 从1，2，，2160这2160个数中最多能选出多少个数，使得选出来的数中，没有一个是另一个的20倍.

解 根据题意，若和不能同时出现在1，2，，2160中，由2160=20108，且108=520 8，则选择1，2，3，4，5，108，109，，2159，这2057个数满足要求. 这里没有选择的数是6，7，，107，2160，共103个数.

由于2160=2057 103，因此，若选出2058个数，则在下面的103个数组(6，620)，（7，720），，（108，10820）中，必有同一数组的两个数被同时选中.从而，必有一个数是另一个数的20倍.

所以，从1，2，，2160这2160个数中最多能选出2057个数.

例5 设是集合1，2，，16的子集.若中的任意两个元素、，其乘积不是完全平方数，求中元素的最大值，并求出满足要求的子集的个数.

解 将集合1，2，，16分成若干个子集，使得同一子集的任意两个元素的乘积是完全平方数，不在同一子集的任意两个元素的乘积不是完全平方数.

为使中元素最多，令

剩余内容已隐藏，请支付后下载全文，论文总字数：9408字