学号：20115034032学年论文（本科）学院数学与信息科学学院专业信息与计算科学年级2011级姓名陈婷婷论文题目鸽巢原理及其应用指导教师沈明辉职称教授成绩2014年3月16日学年论文成绩评定表目录摘要 (1)关键字 (1)Abstract (1)Key words (1)前言 (2)1.鸽巢原理 (2)1.1 鸽巢原理的简单形式 (2)1.2 鸽巢原理的一般形式 (3)1.3 鸽巢原理的加强形式 (3)2. 鸽巢原理的相关推论 (4)3.鸽巢原理的应用 (6)3.1 鸽巢原理应用于数的整除关系 (6)3.2 鸽巢原理应用于实际生活 (7)参考文献 (9)鸽巢原理及其应用姓名：陈婷婷学号：20115034032数学与信息科学学院信息与计算科学专业指导老师：沈明辉职称：教授摘要：鸽巢原理是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重要类型之一，在数论和组合论中有着广泛的应用. 本文简单介绍了鸽巢原理的几种形式，便于了解鸽巢原理到底是什么东西.本文主要研究鸽巢原理和其原理的应用.应用主要从数学领域的应用和现实生活中的应用两大方面进行研究，数学领域方面主要应用于整除关系的证明等几方面的解题.关键字：鸽巢原理; 组合数学; 鸽巢原理的应用Pigeonhole principle and the application of the pigeonhole Abstract:Pigeonhole principle is a mathematical combination of problem of the existence of one of the basic principles of nonconventional problem solving method , is also one of the important types in number theory and combination has a wide range of applications. This paper briefly introduces the principle of Pigeonhole in several forms, easy to understand what the Pigeonhole principle is. This paper mainly studies the principle of Pigeonhole principle and the application of the principle. Application mainly from the mathematical field of application and the reality of life 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:Pigeonhole principle；Mathematical combination ；The application of the principle前言：在组合数学中，证明某种排列或模式存在的一个应用最广泛的工具是鸽巢原理.这一原理也称狄利克雷抽屉原理或鞋盒原理.它和容斥原理一样，是组合分析中的一个重要的原则.它可以用来解决组合分析中许多“存在性”问题，并且常常得到一些令人惊异的结果.下面我们主要研究鸽巢原理的基本形式及其扩展形式和应用.1.鸽巢原理1.1 鸽巢原理的简单形式定理一 如果把n+1个物体放入n 个盒子中去，则至少有一个盒子放有两 个或更多的物体.证明（反证法） 假设n 个盒子中的每个盒子里至多放入了一个物体，则 放入n 个盒子中的物体总数至多为n 个，这与题设“共有n+1个物体”相矛盾，所以知道假设是错误的，从而证明了至少有一个盒子中放有两个或更多的物体.定理一仅能被用于证明一个排列或某种现象的存在性，不能对任何构造排列或寻找现象的例证给出任何指示.例一 在一次舞会上，来了来了来了n 位舞伴，彼此认识的握手问候，证明：在无论什么情况下，这n 位舞伴中至少有两个人握手的次数一样多.证 有已知条件可知，这n 位舞伴中，每个人握手的次数最少有0次，最多有n-1次，比如，如果有一位舞伴握手的次数是0次，那么其他舞伴握手的次数最多不能多于n-2次，即握手次数为0,1,2，...,n-2;如果有一位舞伴握手的次数是n-1次，那么其他舞伴握手次数最少不能少于1次，即握手次数为1,2，...,n-1.总之，这n 位舞伴按照其握手次数归入相应的“抽屉”，则根据抽屉原理可知，至少有两个人属于同一抽屉，即可得这两个人握手次数一样多.例2 设1234,,,a a a a 为任意四个整数，1234,,,b b b b 为1224,,,a a a a 的任一排列，则11223344,,,b a b a b a b a 中必有两个数之差是3的倍数.证明 既然1234,,,b b b b 4是1234,,,a a a a 的一个排列，显然11223344,,,b a b a b a b a 为四个整数，这四个整数被3整除的余数只能是0,1,2中的一个，于是按余数的情形构造3个抽屉，把这4个数11223344,,,b a b a b a b a 视为四个物体，放入这3个抽屉中去，根据抽屉原理，至少有一个抽屉里面放了两个或两个以上的物体，不妨设这两个数为i i b a 与j j b a ,显然有mod3i ij j b a b a 根据同余与整除的关系，有3i i j j b a b a从而11223344,,,b a b a b a b a 中必有两个数之差是3的倍数.1.2 鸽巢原理的一般形式定理1就可以叙述为：如果把n+1=2+2+....+2-n+1个物体放入n 个盒子中 去，则至少存在一个i(i=1,2,...,n),使得第i 个盒子中至少放有两个物体， 设想，如果将2+2+....+2-n+1中的第i 个2改为正整数i q (i=1,2,...,n),就得到鸽巢原理的一般形式.定理2 设qi 是正整数（i=1,2,...n),12...1n q q q q n ,如果将q 个物体放入n 个盒子中去，则必存在一个i ，使得第i 个盒子中至少有i q 个物体. 证明（反证法） 假设结论不成立，即对每个i,第i 个盒子中至多放有1i q 个物体，从而这n 个盒子放入的物体的总数最多为1i q 的和=i q -n<q ，这与“把q 个物体放入n 个盒子中”矛盾，所以假设是错的，即：必存在一个i,使得第i 个盒子中至少有i q 个物体.1.3 鸽巢原理的加强形式定理 3 设A 是有限集，12,,...,n q q q 都是正整数，如果|A|>=12...1n q q q n ,iA A (i=1,2,,..n),且1ni i A A ，则必有正正是k(1k n ),使得k k A q .证明（反证法） 假设有正整数k(1k n )使得1k i A q (i=1,2,,...,n),此时 1211111...n n n n i i i n i i i i AA A q q q q n , 这与12...1n Aq q q n 矛盾，所以假设不成立，因此，必有正整数k(1k n ),使得k k A q .例5 随意的给正方形的8个顶点编上号码1,2，...,8,求证：必有一个顶点，该顶点及与之相邻的两个顶点的号码之和不小于14.证明 以128,,...,A A A 表示的8个顶点，以i q (i=1,2,,...,8)表示顶点i A 及与i A 相邻的两个顶点的号码之和，则128...12...8310814181q q q有定理3，必有正正是k （18k ）,使得14kq ,这表示必有一个顶点，该顶点及与之相邻的两个顶点的号码之和不小于14.2. 鸽巢原理的相关推论在上一节中我们介绍了鸽巢原理的基本形式及其简单证明，但是对于一些更为复杂的，有关存在性的组合问题，鸽巢原理的基本形式显得无能为力，为此，本节将对鸽巢原理进行更为一步的深入研究，以得到某些推论.在定理2中，若12...n q q q r ,则可以得到下面的结论.推论1 如果把n(r-1)+1个物体放入n 个盒子中，则至少存在一个盒子放有不少于r 个物体.例1 分别将两个大小不一的圆盘分成100个相等的扇形，在大圆盘上任意选取50个扇形染成红色，将其余50个大扇形染成蓝色，并将小圆盘上的100小扇形上的每一个任意的染成红色或蓝色，然后将小圆盘放在大圆盘上面，使得两个圆盘的中心重合，这样，转动小圆盘能使其每一个扇形都能叠放于大圆盘上的某一扇形内，证明：当适当转动小圆盘时，可使叠放的扇形对中，同色者至少有50对.证明 小圆盘的每个扇形都叠放于大圆盘的一个扇形中，有100中可能的位置，所以将这100种可能位置看做100个不同的盒子，在这100种可能位置中，将同色的扇形对看做放入盒子中的物体，小圆盘的每一扇形都有50次配成同色的扇形对，因此这样的扇形对一共有10050个，而100501005011,有推论知，至少有一种小圆盘与大圆盘的叠放方式，可使叠放的扇形中至少有50个同色的扇形对.例2 在某中学A 班有50名学生，其中年龄最小的是15岁，最大的是16岁，证明这个班至少有三个学生是同年同月生的.证明 50>49=2(25-1)+1,由于年龄最小的是15岁，最大的 是16岁，故将15岁，16岁看最2个“盒子”，将50名学生放入这2个“盒子”中。

有鸽巢原理推论1知：至少有一个“盒子”中放有25名学生，即至少有25名学生同岁，也就是说这25名学生同年生，再将十二个月份分为12个“盒子”，将这25名同年生的学生放入这12个“盒子”中，因为2512311,故有推论1知，至少有一个“盒子”中放有3名学生，即在此25个同年生的学生中至少有3个人是同月生的，故这个班中至少有3个人是同年同月生的.推论 2 对于任意n 个正整数12,,...,n m m m ,如果这n 个整数满足不等式121...1n m m m r n ,则12,,...,n m m m 中至少有一个不小于r.证明(反证法) 假设对所有的12,,...,n m m m ,都有12,,...,n m m m 小于r,即11,2,...,i m r i n ,于是12...1nm m m nr n n r所以 121...1n m m m r n这与121...1n m m m r n 矛盾，因此，假设不成立，原命题成立，所以12,,...,n m m m 中至少有一个不小于r 的结论成立.推论3 m 只鸽子，n 个鸽巢，则至少有一个鸽巢里有不少于1m n只鸽子.注：这里的符号“[]”为取整符号，即[x]表示不超过x 的最大整数.至此，本章总结了鸽巢原理的表现形式及其推论，虽然原理的表述比较简单，但是应用原理证明问题的时候，构造鸽巢的方法是比较不容易得到的.3.鸽巢原理的应用运用鸽巢原理的关键是“制造抽屉”及“元素”。