在映射角度下理解鸽笼原理及其具体应用

1、在映射角度下理解鸽笼原理及其具体应用摘 要： 鸽笼原理是数学中的重要原理, 在解决数学问题时有非常重要的作用。本文将从映射角度理解鸽笼原理，并介绍其在生活中的具体应用。关键词 ： 鸽笼原理；映射；具体应用鸽笼原理，又称抽屉原则或重叠原则，如果能灵活运用这一原则，可以很顺利地解决一些看上去相当复杂甚至觉得简直无从下手的数学问题。因此，常被一些国内外数学竞赛作为命题的内容之一，不失为中学生开展课外活动的好材料。一、鸽笼原理的简单形式鸽笼原理： （抽屉原则或重叠原则）将N+1 只或 N+1 只以上的鸽子放入N个鸽笼内，则至少有一个鸽笼内有两支或两支以上的鸽子。二、从映射角度理解鸽笼原理映射为鸽笼原理

2、提供了理想的数学语言，反之， 鸽笼原理为映射提供了实际背景，为映射建立了一个直观而形象的数学模型，两者相辅相成，相得益彰。设鸽子的集合为A a1,a2 an ，笼子的集合为B b1,b2 bn ，n m , 集合 A 中每一鸽子都要以某一方式进入集合B 中的某一笼内，不存在某一鸽子可以同时既在甲笼又在乙笼，当然， A中可以有 两只或两只以上的鸽子，对应B中的一只笼子，或B中的笼子可以未 被A中的鸽子所对应。从映射角度理解鸽笼原理，鸽笼原理是一种特 殊的对应单一对应。这样，在此单一对应下，从集合 A中任意挑出两只不同的笼，能否总能找到两只不同的笼，使得鸽与笼配对呢？显然，此事办不到，这是因为鸽多

3、笼少，而不是鸽少笼多或鸽笼相当，因此，由于所选相异两鸽的任意性，当分别对应进入相异两笼时，必有某些余鸽无笼可归，所以在意对应下，由于鸽多笼少，至少要有双鸽同笼现象发生将 是不可避免的。其实，上述现象，映射为原理定义了精确的数学语言：(1)单射：设f是从集合A到集合B的一个映射，若任给xi , X2 A,只要Xi X2,就有f ( % ) f ( X2),那么就称f是从集合A到 集合B的一个单射。(如图1)(2)满射：设f是从集合A到集合B的一个映射，如果f (A) =B,那么称f是从A到B上的一个满射。(如图2)图1图2（3）双射：若f既是单射又是满射，则称f是从A到B的一个双射。（如图3）又

4、如，（图4）所示为既非单射又非满射。图33 4这样，鸽笼原理实际上是排除了单射的可能,当然随之也排除了双射的可能，因此，它可能是满射，或者也可能是既非单射又非满射, 两者必居其一。三、同笼最小重复鸽数P的确定当鸽多笼少，必出现多对一，那么 N只鸽进入M只笼（N>M）寸, 至少有多少只鸽（设为P）同笼？由于需要计算的是同笼重鸽数的最低数，因此只需考虑满射，在即非单射又非满射情况下同笼的重鸽数必然超过 P.表示不小于凡的最小整数，能够证明P= -N ,就是所需要确定的同笼的最低重复数。用映射思想表述就是设 F是从A到B的任意一个映射，A二A,A2, ' , B= B,B2, Bm,若

5、 N>M设 P= N/M,则必 至少存在 A,A2, ApSA,使得 F(Ai)=F(A2)=F(Ap).四、鸽笼的构造应用鸽笼原理的基本思想是根据不同问题自身特点，洞察问题本质，先弄清对哪些元素进行分类，再找出分类的规律，即所谓的构造 鸽笼，构造抽屉是应用抽屉原理的关键.在介绍抽屉原理的应用之前， 本文先用几个具体的例子来介绍几种常用的构造抽屉的方法.1.等分区间制造鸽笼当问题的结论与区间有关时，可等分某个区间，设计出若干个鸽 笼。例1求证：对于任给的正无理数 及任意大的自然数n,存在一 1mn,1证明：把区间(0, 1)进行n等分，得n个小区间0,- n由鸽笼原理知，这些区间内的n

6、1个数中，必有两个数落在某一个区间，从而这两个数的差的绝对值小于 1.n设PiN(i 1,2,.,n 1),则由 是正无理数得0 Pi P 1所以这n1个数PiPi(i 1,2,., n 1)中，必有2个数，不妨设为和P2P2,它们的差的绝对值小于-,即(PlP2)( P1P2设 P1P2m, PiP2k,则1mn上述例子涉及区间问题，把区间(0,1)进行n等分，得n个小区间，自然就得到了 n个鸽笼，而n1个数可以作为n 1个物体，此处可以利用鸽笼原理解决问题.2 .分割图形构造抽屉在一个几何图形内有若干已知点,我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为鸽笼，再对已知点

7、进行 分类，集中对某一个或几个鸽笼进行讨论，使问题得到解决.例2在边长为2米的正方形内，任意放入13个点.求证：必有1平方米.证明：把边长为2米的正方形分割成面积为1平方米的4个小正方形，如图1.由鸽笼原理知，至少有4个点落在同一个面积为1平 方米的小正方形内（或边上），以这4个点为顶点的四边形的面积总 小于或等于小正方形的面积，即以这4个点为顶点的四边形的面积不 超过1平方米.注：此例是通过分割图形构造鸽笼.将正方形等分成4个矩形来制造鸽笼也可以解决本题，如图 2.3 .利用“对称性”构造鸽笼“对称性”是数学中常用的处理问题的一种方法.同样，在构造 鸽笼的过程中也可以利用“对称性”来解决问题

8、，这种方法不易观察， 需要不断的训练.例3九条直线中的每一条直线都把正方形分成面积比为 2: 3的 两个四边形.证明：这九条直线中至少有 三条经过同一点. 证明：如图，设 CD是一条这样的直 线.我们再画出这两个梯形的中位线 AB, 因这两个梯形有相等的高，所以他们的面积 比应等于对应的中位线长的比，即等于 AP：PB （或者BP：PA）因为点p有确定的位 置，它在正方形一对对边中点的连线上， 并 且AP:PB 2:3,由几何上的对称性，这种点共有P,Q,R,S .已知的九条适合条件的分割直线中的每一条必须过P,Q,R,S这4点中的一点.把P,Q,R,S当成4个鸽笼，9条直线当成9个物体， 即

9、可看出必有3条分割直线经过同一个点.正方形是个比较规则的图形，在正方形中有很多对称关系，对解题减小了一点难度。4 . 用整数性质制造鸽笼当问题与整数性质有关时，我们可以用整数的性质，把题目中的数设计成一些鸽笼，然后用鸽笼原理去解仔细观察题目中的数，如果题中数据具有一定的规律，可以划分数组构造鸽笼例4从1,2,3,98中任取50个不同的数，试证：其中必与两个数，它们之差等于7证明 : 先把所给的98 个数设计成49 个鸽笼：（ 1 ， 8）， （ 2， 9）（3, 10） , （4, 11）,，（21, 28）,，（91, 98）,可以发现每个抽屉里的两个数之差为7从1, 2, 3,，98中任取

10、50个，就是从这49个鸽笼中任取50 个数，由鸽笼原理知，必有一个鸽笼中要取出两个数，即这50 个数中必有两个数，它们之差为7本题的关键就是对这98 个数进行合理分类，构造鸽笼分类的原则是每个鸽笼中的两个数只差是7，且鸽笼的个数少于任取的数的个数五 . 抽屉原理在生活中的应用1. 月黑穿袜子有一个晚上你的房间的点灯忽然坏了，伸手不见五指，而你又要 出去，于是你就摸底下的袜子.你有三双分别为红、白、蓝颜色的袜子，可是你平时做事随便，一脱袜子就乱丢，在黑暗中不知道哪一双是颜色相同的你想拿最少数目的袜子出去，在外面借街灯配成颜色相同的一双这最少数目应该是多少？运用鸽笼原理，你就会知道只拿出去四只袜子

11、就行了因为我们有三双红、白、蓝的袜子，相当于3 个鸽笼，我们拿出去的4 只袜子就是 4个物体， 4个物体肯定有2个是同一个颜色的。2. 手指纹和头发据说世界上没有两个人的手指纹是一样的，因此警方在处理犯罪问题时很重视手指纹，希望通过手指纹来破案或检定犯人可是在13亿中国人当中，最少有两个人头发是一样多的这是因为，人的头发数目是不会超过13 亿这么大的数目，假定人最多有N根头发.现在我们编上号码Al, A2, A3, A4,., An .其中A表不由 i 根头发的那些人现在假定每个Ai 都有一个人，那么还剩下“13亿减N'个人，这数目不会等于零，我们现在随便挑一个放进和他头发相同的小组就行，他就会在里面遇到和他有相同头发数目的人了3. 电脑算命“电脑算命”看起来挺玄乎，只要你报出自己出生的年、月、日和性别一按按键，屏幕上就会出现所谓性格、命运的句子，据说这就是你的“命”这是科学的吗？如果以 70 年算，按出生的年、月、日、性别的不同组合数应为70 365 2 51100，我们把它作为鸽笼数我国现有人口13 亿，我们把它