组合数学-第一节：鸽巢原理

第1章 鸽巢原理

鸽巢原理（又叫抽屉原理）指的是一件简单明了的事实：为数众多的一群鸽子飞进不多的巢穴里，则至少有一个巢穴飞进了两只或更多的鸽子。

这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的组合问题，得到一些很重要的结论，它在数学的历史上起了很重要的作用。

1.1 鸽巢原理的简单形式 鸽巢原理的简单形式可以描述为：

定理1.1.1 如果把1n +个物品放入n 个盒子中，那么至少有一个盒子中有两个或更多的物品。 证明 如果每个盒子中至多有一个物品，那么n 个盒子中至多有n 个物品，而我们共有1n +个物品，矛盾。故定理成立。

鸽巢原理只断言存在一个盒子，该盒中有两个或两个以上的物品，但它并没有指出是哪个盒子，要想知道是哪一个盒子，则只能逐个检查这些盒子。所以，这个原理只能用来证明某种安排的存在性，而对于找出这种安排却毫无帮助。

例1 共有12个属相，今有13个人，则必有两人的属相相同。

例2 在边长为1的正方形内任取5点，则其中至少有两点，它们之间的距离不超过

2

。 证明 把边长为1的正方形分成4个边长为

1

2

的小正方形，如图1.1.1所示，在大正方形内任取5点，则这5点分别落在4个小正方形中。由鸽巢原理知，至少有两点落在某一个小正方形中，从而这两点间的

距离小于或等于小正方形对角线的长度

2

。

例3 给出m 个整数12,,,m a a a ，证明：必存在整数,(0)k l k l m ≤<≤，使得

()12k k t m a a a +++++

证明 构造部分和序列

1121212,,m m s a s a a s a a a ==+=+++

则有如下两种可能：

（i ）存在整数(1)h h m ≤≤，使得h m s ，此时，取0,k l h ==即满足题意。

（ii ）对任一整数i ，均有(1)i m s i m ≤≤，令(m o d )i i r s m =，则有11(1)i r m i m ≤≤-≤≤，这样，

m 个余数均在1到m-1之间。由鸽巢原理知，存在整数(1,)k l k l m ≠≤≤，使得k l r r =。不妨设l k >，

则

12111()()()(mod )0(mod )

k k t k k t k t k t k a a a a a a a a a s s k r r m m ++++++=+++++-++=-=-=

综合（i ）和（ii ），即知题设结论成立。

例4 一个棋手有11周时间准备锦标赛，他决定每天至少下一盘棋，一周中下棋的次数不能多于12次，证明：在此期间的连续一些天中他正好下棋21次。

证明 令1277,b b b 分别为这11周期间他每天下棋的次数，并作部分和

11212771277,,a b a b b a b b b ==+=+++

根据题意，有1(177)i b i ≥≤≤ 且1612(171)i i i b b b i +++++≤≤≤

所以有1237711211132a a a a ≤<<<<≤?= （1.1.1） 考虑数列12771277,;21,21,21a a a a a a +++

它们都在1与13221153+=之间，共有154项，由鸽巢原理知，其中必有两项相等，由（1.1.1）式知1277,a a a 这77项互不相等，从而127721,21,21a a a +++ 这77项也互不相等，所以一定存在

177i j ≤≤≤，使得

21j i a a =+

因此

121121221()()j i i i j i i i j

a a

b b b b b b b b b b b +++=-=++++++-+++=+++

这说明从第1i +天到第j 天这连续j i -天中，他刚好下了21盘棋。

例5 从1到200的所有整数中任取101个，则这101个整数中至少有一对数，其中的一个一定能被另一个整除。

证明 设12101,a a a 是被选出的101个整数，对任一i a ，都可以唯一地写成如下的形式：

2(1,2,101)si i i a r i =?= ，

其中，i s 为整数，i r 为奇数。例如：

367229,6421=?=?

由于1200i a ≤≤，所以(1101)i r i ≤≤只能取1，3，5，……199这100个奇数，而12101,,r r r ，共有101项，由鸽巢原理知，存在1101i j ≤≠≤，使得

i j r r =不妨设i j s s <，则

22

2j j i

j

s

s s j j s i

i

a r a r -?=

==?整数即j a 能被i a 整除。

从上面的几个例子可以看出，尽管鸽巢原理很简单，但它却能解决一些看似很复杂的组合问题。在将其应用到具体的组合问题时，需要一定的技巧去构造具体问题中的“鸽子”与“鸽巢”。

1.2 鸽巢原理的强形式

定理1.2.1 设12,,n q q q 都是正整数，如果把

121n q q q n +++-+

个物品放入n 个盒子，那么或者第1个盒子至少包含1q 个物品，或者第2个盒子至少包含2q 个物品，……或者第n 个盒子至少包含n q 个物品。

证明 若对所有的(1)i i n ≤≤，第i 个盒子至多只有1i q -个物品，则n 个盒子中至多有

()()()()1212111n n q q q q q q n -+-++-=+++-

个物品，而我们现在有121n q q q n +++-+ 个物品，矛盾。故定理成立。

在定理 1.2.1中令122n q q q === ，则变成了鸽巢原理的简单形式。在定理 1.2.1中令

12n q q q r === ，则得到如下的推论：

推论1.2.1 若将(1)1n r -+个物品放入n 个盒子中，则至少有一个盒子中有r 个物品。 推论1.2.1也可以叙述如推论1.2.2所描述的另一种形式： 推论1.2.2 设12,,n m m m 是n 个整数，而且

121n

m m m r n

+++>-

则12,,n m m m 中至少有一个数不小于r 。

推1.2.3 若将m 个物品放入n 个盒子中，则至少有一个盒子中有不少于m n ??????个物品。其中，m n ??

????

是不小于

m

n

的最小整数。 例1 设有大小两只圆盘，每个都划分成大小相等的200个小扇形，在大盘上任选100个小扇形漆成黑色，其余的100个小扇形漆成白色，而将小盘上的200个小扇形任意漆成黑色或白色。现将大小两只圆盘的中

心重合，转动小盘使小盘上的每个小扇形含在大盘上的小扇形之内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。

证明 如图1.2.1所示，使大小两盘中心重合，固定大盘，转动小盘，则有200个不同的位置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘上的200个小扇形中有100个漆成黑色，100个漆成白色，所以小盘上的每个小扇形无论漆成黑色或白色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色，因而小盘上的200个小扇形在200个重合位置上共同色10020020000?=次，平均每个位置同色20000200100÷=次。由鸽巢原理知，存在着某个位置，使同色的小扇形数大于等于100个。

例2 任意2

1n +个实数

2123,,,1n a a a a +

（1.2.1）

组成的序列中，必有一个长为1n +的非降子序列，或必有一个长为1n +的非升子序列。 在证明本例之前先看一个具体的例子，对于序列(3)n =

5,3,16,10,15,14,9,11,6,7

从中可以选出几个递增子序列：

{}{}{}{}5,16,5,10,15,3,9,11,3,6,7,; 也可以选出如下几个递减子序列：

{}{}{}5,3,16,10,9,7,16,15,14,11,7,

证明 方法1 假设长为2

1n +的实数序列（1.2.1）中没有长度为1n +的非降子序列，下面证明其必有一长度为1n +的非升子序列。

令k m 表示从k a 开始的最长非降子序列的长度，因为实数序列（1.2.1）中没有长度为1n +的非降子序列，所以有

()211,2,1k m n k n ≤≤=+

这相当于把2

1n +个物品212,,1n m m m + 放入n 个盒子1，2，……n 中，由鸽巢原理知，必有一盒子i 里

面至少有1n +个物品，即存在：121n k k k +<<< 及：1i n ≤≤。使得

121n k k k m m m i +===

（1.2.2）

对应于这些下标的实数序列必满足：121n k k k a a a +≥≥≥ （1.2.3）

它们构成一长为1n +的非增子序列。否则，若有某个(1)j j n ≤≤，使得1j j k k a a +<，那么由从1j k a +开始的最长非降子序列加上j k a ，就得到一个从j k a 开始的长度为11j k m ++的非降子序列。由j k m 的定义知

11j j k k m m +≥+这与（1.2.2）式矛盾。因此（1.2.3）式成立，从而定理的结论成立。

方法2 对应于实数序列（1.2.1）中的每个i a ，定义一个有序偶(,)i i l m

其中，i l 为从i a 开始的最长非降子序列的长度，i m 为从i a 开始的最长非长子序列的长度，则对应于序列（1.2.1），有以下的有序偶序列

()()()2

2

112211,,,,,n n l m l m l m ++

（1.2.4）

若实数序列（1.2.1）中既没有长为1n +的非升子序列，也没有长为1n +的非降子序列，则有

21,1(1,2,1)i i l n m n i n ≤≤≤≤=+

（1.2.5）

满足条件（1.2.5）的有序偶最多只有2

n 个，由鸽巢原理知，序列（1.2.4）中至少有两个有序偶相同。即存

在2

11i j n ≤≠≤+，使得()()

,,i i j j l m l m =

即,i j i j l l m l ==

不妨设i j <，由方法1的分析知，若i j a a ≤，则i j l l >，与i j l l =矛盾；若i j a a >，则i j m m >，与i j m m =矛盾。所以，实数序列（1.2.1）中必有一长为1n +的非降子序列，或有一长为1n +的非升子序列。 例3 将1到16的16个正整数任意分成三部分，其中必有一部分中的一个元素是某两个元素之差（三个元素不一定互不相同）。

证明 用反证法。设将1到16的16个整数任意分成12,P P 和3P 三个部分，若这三部分中无一具有问题所指的性质，即其中一个元素是其中某两个元素之差，由此我们来导出矛盾，从而证明问题的结论是正确的。 （1）将1到16的整数任意分成三部分，由鸽巢原理知，其中必有一部分至少有1663??

=????

个元素，不妨设1P 中含有6个元素，为123456a a a a a a <<<<<

令{}1123456,,,,,A P a a a a a a ==，若A 中存在一个元素是某两个元素之差，则1P 满足问题的要求。否则，令

121231341451561,,,,,

b a a b a a b a a b a a b a a =-=-=-=-=-

并令{}123456,,,,,B b b b b b b =。显然，116(15)i b i ≤≤≤≤，即B 中的元素仍是1到16的整数。根据假设，

12345,,,,b b b b b 无一属于1P 。否则，与1P 中不存在一元素等于某两元素之差相矛盾。所以，B 中元素属于2P 或3P

（2）与（1）类似，不妨设B 中至少532??=????

个元素属于2P ，设为123c c c <<

并令{}123,,C c c c =。由假设，C 中不存在一元素是某两个元素之差。令121231,d c c d c c =-=- 并令{}12,D d d =。显然，D 中元素不属于2P ，否则，与2P 中不存在一元素是某两个元素之差相矛盾。且

12116d d ≤≤≤。下面再证明D 中元素不属于1P 。

设(1,2,3;15)i i j i c b i j ==≤≤，则()(

)2121211211111

11

j j j j j j d c c b b a a a a a a ++++=-=-=---=-

同理31211j j d a a ++=-

所以，12,d d 均不属于1P 。因此，D 中元素属于3P 。

（3）根据假设，在3P 中不存在一元素是另两个元素之差，所以121d d d ≠-，令21e d d =-

与（1）类似，e 不属于3P ；同（2）可以证明e 也不属于1P 和2P 。即存在一整数116e ≤≤，它不属于12,P P 和3P 中的任何一个，这与将1到16间的整数任意分成三个部分的假设相矛盾。

鸽巢原理及其应用+6

学号：20115034032 学院数学与信息科学学院 专业信息与计算科学 年级2011级 姓名陈婷婷 论文题目鸽巢原理及其应用 指导教师沈明辉职称教授 成绩 2014年3月16日

学年论文成绩评定表评语 成绩： 指导教师(签名): 201 年月日学院意见：____________________ 学院院长(签名): 201 年月日

目录 摘要 (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

鸽巢原理及其应用

鸽巢原理是组合数学中最基本的计数原理之一，也是证明存在性问题的一种重要方法．本文首先介绍了鸽巢原理的不同表述形式及其推论，然后从整除关系的证明、几何图形的分割以及解决实际问题等几个角度介绍了鸽巢原理的应用，并对例题中鸽巢的构造技巧做了分析． 关键词：鸽巢原理；简单形式；一般形式；加强形式

Abstract The pigeonhole principle is one of the basic counting principle in combinatorics, but also it is an important method to prove the problem of the existence. This paper first introduces the different expressions of the pigeonhole principle and its deduction, then the applications of the pigeonhole principle are introduced from several angles of proof of aliquot relationship, division of the geometrical figure and solving practical problems, the structured skills of the pigeonhole principle in examples are analysed. Key words: pigeonhole principle; simple form; general form; strengthend form

容斥原理与鸽巢原理的应用

摘要 容斥原理和鸽巢原理作为组合数学中的基本内容，就原理本身而言简单易懂.然而，由于此二者分别在组合计数问题和存在性问题的应用中所展现出来的魅力，国内外学者在很多书籍、学术性论文中关于容斥原理和鸽巢原理的应用进行了探讨，并且关于此方面的研究已取得一系列的成果. 本文主要是以综述的方式从起源、理论和应用三方面对容斥原理和鸽巢原理进行了介绍和分类探讨. 首先介绍了容斥原理分别与加法理论、减法理论的区别与优势，并与实际问题相结合突出其优势所在.其次本文介绍了鸽巢原理的两种具体形式及其推论，并对鸽巢原理在数学理论研究、数学竞赛题目、解决实际生活中的问题等方面的应用进行介绍后，对鸽巢原理的应用中所常见的几种构造“鸽巢”的方法进行了分类谈论. 最后，针对鸽巢原理，我们给出针对新疆某区域关于旅游产品的实际应用实例，并提出了个人见解. 关键词：容斥原理，鸽巢原理，构造方法，鸽巢，鸽子

ABSTRACT As the basic content of combinatorial mathematics, the principle of tolerance and the theory of pigeon nest the principle itself is simple and understandable. However, due to the charm of the two applications in combinatorial counting and existential problems, scholars at home and abroad have probed into the application of the principle of tolerance and the pigeon nest in many books and academic papers, And the research on this aspect has made a series of achievements. In this paper, the author introduces and classifies the theory of tolerance and doctrine and the principle of pigeon nest in the way of summarization from the origin, theory and application. Firstly, the differences and advantages between the theory of tolerance and exclusion and the theory of addition and subtraction were introduced. and the actual problem with the combination of highlighting its advantages. Secondly, this paper introduces two concrete forms of pigeon nest principle and its inference, and introduces the application of pigeon nest principle in mathematics theory research, Maths contest problem, solving real life problems and so on. , several common methods of constructing pigeon nest in the application of pigeon nest principle are classified and discussed. Finally, according to the pigeon Nest principle, we give a practical example of the tourism products in a region of Xinjiang, and put forward personal opinions. KEY WORDS: inclusion-exclusion principle, pigeonhole principle, construction method, pigeonhole, pigeon

抽屉原理又称鸽巢原理,它是组合数学的一个基本原理,最先是由德.

抽屉原理又称鸽巢原理，它是组合数学的一个基本原理，最先是由德国数学家狭利克雷明确地提出来的，因此，也称为狭利克雷原理。 把3个苹果放进2个抽屉里，一定有一个抽屉里放了2个或2个以上的苹果。这个人所皆知的常识就是抽屉原理在日常生活中的体现。用它可以解决一些相当复杂甚至无从下手的问题。 原理1：把n+1个元素分成n类，不管怎么分，则一定有一类中有2个或2个以上的元素。 原理2：把m个元素任意放入n（n＜m＝个集合，则一定有一个集合呈至少要有k个元素。 其中 k＝n （当n能整除m时） 〔 n〕＋1 （当n不能整除m时） 原理3：把无穷多个元素放入有限个集合里，则一定有一个集合里含有无穷多个元素。 二、应用抽屉原理解题的步骤 第一步：分析题意。分清什么是“东西”，什么是“抽屉”，也就是什么作“东西”，什么可作“抽屉”。 第二步：制造抽屉。这个是关键的一步，这一步就是如何设计抽屉。根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需的抽屉及其个数，为使用抽屉铺平道路。 第三步：运用抽屉原理。观察题设条件，结合第二步，恰当应用各个原则或综合运用几个原则，以求问题之解决。

例1、教室里有5名学生正在做作业，今天只有数学、英语、语文、地理四科作业 求证：这5名学生中，至少有两个人在做同一科作业。 证明：将5名学生看作5个苹果 将数学、英语、语文、地理作业各看成一个抽屉，共4个抽屉 由抽屉原理1，一定存在一个抽屉，在这个抽屉里至少有2个苹果。 即至少有两名学生在做同一科的作业。 例2、木箱里装有红色球3个、黄色球5个、蓝色球7个，若蒙眼去摸，为保证取出的球中有两个球的颜色相同，则最少要取出多少个球？ 解：把3种颜色看作3个抽屉 若要符合题意，则小球的数目必须大于3 大于3的最小数字是4 故至少取出4个小球才能符合要求 答：最少要取出4个球。 例3、班上有50名学生，将书分给大家，至少要拿多少本，才能保证至少有一个学生能得到两本或两本以上的书。 解：把50名学生看作50个抽屉，把书看成苹果 根据原理1，书的数目要比学生的人数多 即书至少需要50+1=51本 答：最少需要51本。

鸽巢原理

摘要 鸽巢原理是组合数学中最基本的计数原理之一，也是证明存在性问题的一种重要方法．本文首先介绍了鸽巢原理的不同表述形式及其推论，然后从整除关系的证明、几何图形的分割以及解决实际问题等几个角度介绍了鸽巢原理的应用，并对例题中鸽巢的构造技巧做了分析． 关键词：鸽巢原理；简单形式；一般形式；加强形式

Abstract The pigeonhole principle is one of the basic counting principle in combinatorics, but also it is an important method to prove the problem of the existence. This paper first introduces the different expressions of the pigeonhole principle and its deduction, then the applications of the pigeonhole principle are introduced from several angles of proof of aliquot relationship, division of the geometrical figure and solving practical problems, the structured skills of the pigeonhole principle in examples are analysed. Key words: pigeonhole principle; simple form; general form; strengthend form

高中数学抽屉原理容斥原理

高中数学抽屉原理容斥原理 在数学问题中有一类与“存在性”有关的问题，例如：“13个人中至少有两个人出生在相同月份”；“某校400名学生中，一定存在两名学生，他们在同一天过生日”；“2003个人任意分成200个小组，一定存在一组，其成员数不少于11”；“把[0，1]内的全部有理数放到100个集合中，一定存在一个集合，它里面有无限多个有理数”。这类存在性问题中，“存在”的含义是“至少有一个”。在解决这类问题时，只要求指明存在，一般并不需要指出哪一个，也不需要确定通过什么方式把这个存在的东西找出来。这类问题相对来说涉及到的运算较少，依据的理论也不复杂，我们把这些理论称之为“抽屉原理”。 “抽屉原理”最先是由19世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题的，所以又称“迪里赫莱原理”，也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果，任意分放在9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类数学竞赛中的重要内容，本讲就来学习它的有关知识及其应用。 （一）抽屉原理的基本形式 定理1、如果把n+1个元素分成n个集合，那么不管怎么分，都存在一

个集合，其中至少有两个元素。 证明：（用反证法）若不存在至少有两个元素的集合，则每个集合至多1个元素，从而n个集合至多有n个元素，此与共有n+1个元素矛盾，故命题成立。 在定理1的叙述中，可以把“元素”改为“物件”，把“集合”改成“抽屉”，抽屉原理正是由此得名。 同样，可以把“元素”改成“鸽子”，把“分成n个集合”改成“飞进n个鸽笼中”。“鸽笼原理”由此得名。 例题讲解 1．已知在边长为1的等边三角形内（包括边界）有任意五个点（图1）。证明：至少有两个点之间的距离不大于 2．从1-100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个是另一个的整数倍。 3．从前25个自然数中任意取出7个数，证明：取出的数中一定有两个数，这两个数中大数不超过小数的1.5倍。 4．已给一个由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。 5．在坐标平面上任取五个整点（该点的横纵坐标都取整数），证明：其中一定存在两个整点，它们的连线中点仍是整点。 6．在任意给出的100个整数中，都可以找出若干个数来（可以是一个数），它们的和可被100整除。 7．17名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而且任意两名科学家通信时只讨论一个题目，证明：其中至少有三名科学家，他们相互通信时讨论的是同一个题目。

第二章 鸽巢原理

第二章 鸽巢原理 我们在本章考虑一个重要而又初等的组合学原理，它能够用来解决各种有趣的问题，常常得出一些令人惊奇的结论。这个原理有许多的名字，但最普通的名字叫鸽巢原理，也叫做鞋盒原理。有关于鸽巢的原理阐释，粗略地说就是如果有许多鸽子飞进不足够多的鸽子巢内，那么至少要有一个鸽巢被两个或多个鸽子占据。更精确的叙述在下面给出。 2.1 鸽巢原理的简单形式 鸽巢原理的简单的形式可以描述如下： 定理2.1.1 如果n+1个物体被放进n 个盒子，那么至少有一个盒子包合两个或更多的物体。 证明：如果这n 个盒子中的每一个都至多含有一个物体，那么物体的总数最多是n 。 既然我们有n ＋1个物体，于是某个盒子就必然包含至少两个物体。 注意，无论是鸽巢原理，还是它的证明，对于找出含有两个或更多物体的盒子都没有任何帮助。它们只是简单地断言，如果人们检查每一个盒子，那么他们会发现有的盒子里面放有多于一个的物体：鸽巢原理只是保证这样的盒子存在。因此，无论何时鸽巢原理被用来证明一个排列或某种现象的存在性，除了考察所有可能性之外，它都不能对任何构造排列或寻找现象的例证给出任何指示。 我们可以把将物体放入盒子改为用n 种颜色中的一种颜色对每一个物体涂色：此时，鸽巢原理断言，如果n ＋1个物体用n 种颜色涂色，那么必然有两个物体被涂成相同的颜色。 下面是两个简单的应用。 应用1 在13个人中存在两个人，他们的生日在同一个月份里。 应用2 设有n 对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这2n 个人中选出多少人? 为了在这种情形下应用鸽巢原理，考虑n 个盒子，其中一个盒子对应一对夫妇。如果我们选择n ＋1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个人；也就是说，我们已经选择了一对已婚夫妇。选择n 个人使他们当中一对夫妻也不没有的两种方法是选择所有的丈夫或选择所有的妻子。因此，n ＋1是保证能有一对夫妇被选中的最小的人数。 还存在一些与鸽巢原理相关的其他原理，有必要正式叙述如下： 如果将n 个物体放入n 个盒子并且没有一个盒于是空的，那么每个盒子恰好包合一个物体。 如果将n 个物体放入n 个盒子并且没有盒子被放入多于一个的物体，那么每个盒子里有一个物体。 在应用2里，如果我们这样选择n 个人，从每一对夫妻中至少选一人，那么我们就从每对夫妻中恰好选出了一个人。同样，如果我们选择n 个人的方法是从每一对夫妻中至多选一人，那么我们就从每对夫妻中至少(从而也恰好)选出了一个人。 应用3 给定m 个整数m a a a ,,,21 ，存在整数k 和l ，m l k ≤<≤0o ，使得l k k a a a +++++ 21’能够被m 整除。通俗地说，就是在序列m a a a ,,,21 中存在连续i a ，这些i a 的和能被m 整除。 为了深入这个问题，考虑m 个和

最新组合数学-第一节：鸽巢原理

第1章 鸽巢原理 鸽巢原理（又叫抽屉原理）指的是一件简单明了的事实：为数众多的一群鸽子飞进不多的巢穴里，则至少有一个巢穴飞进了两只或更多的鸽子。 这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的组合问题，得到一些很重要的结论，它在数学的历史上起了很重要的作用。 1.1 鸽巢原理的简单形式 鸽巢原理的简单形式可以描述为： 定理1.1.1 如果把1n +个物品放入n 个盒子中，那么至少有一个盒子中有两个或更多的物品。 证明 如果每个盒子中至多有一个物品，那么n 个盒子中至多有n 个物品，而我们共有1n +个物品，矛盾。故定理成立。 鸽巢原理只断言存在一个盒子，该盒中有两个或两个以上的物品，但它并没有指出是哪个盒子，要想知道是哪一个盒子，则只能逐个检查这些盒子。所以，这个原理只能用来证明某种安排的存在性，而对于找出这种安排却毫无帮助。 例1 共有12个属相，今有13个人，则必有两人的属相相同。 例2 在边长为1的正方形内任取5点，则其中至少有两点，它们之间的距离不超过22。 证明 把边长为1的正方形分成4个边长为12 的小正方形，如图1.1.1所示，在大正方形内任取5点，则这5点分别落在4个小正方形中。由鸽巢原理知，至少有两点落在某一个小正方形中，从而这两点间的距离小于或等于小正方形对角线的长度 22 。 例3 给出m 个整数12,,,m a a a L ，证明：必存在整数,(0)k l k l m ≤<≤，使得 ()12k k t m a a a +++++L 证明 构造部分和序列 1121212,,m m s a s a a s a a a ==+=+++L L 则有如下两种可能：

容斥原理和抽屉原理

容斥原理 在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 容斥原理（1） 如果被计数的事物有A、B两类，那么，A类或B类元素个数= A类元素个数+ B类元素个数—既是A类又是B类的元素个数。 例1 一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？ 分析：依题意，被计数的事物有语、数得满分两类，“数学得满分”称为“A类元素”，“语文得满分”称为“B类元素”，“语、数都是满分”称为“既是A类又是B类的元素”，“至少有一门得满分的同学”称为“A类或B类元素个数”的总和。 试一试：某班学生每人家里至少有空调和电脑两种电器中的一种，已知家中有空调的有41人，有电容斥原理（2） 如果被计数的事物有A、B、C三类，那么，A类或B类或C类元素个数= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。 例2某校六（1）班有学生54人，每人在暑假里都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有34人，足球、排球都参加的有12人，足球、游泳都参加的有18人，排球、游泳都参加的有14人，问：三项都参加的有多少人？ 分析：仿照例1的分析，你能先说一说吗？ 例3 在1到1000的自然数中，能被3或5整除的数共有多少个？不能被3或5整除的数共有多少个？ 分析：显然，这是一个重复计数问题（当然，如果不怕麻烦你可以分别去数3的倍数，5的倍数）。我们可以把“能被3或5整除的数”分别看成A类元素和B类元素，能“同时被3或5整除的数（15的倍数）”就是被重复计算的数，即“既是A类又是B类的元素”。求的是“A类或B类元素个数”。现在我们还不能直接计算，必须先求出所需条件。1000÷3=333……1，能被3整除的数有333个（想一想，这是为什么？）同理，可以求出其他的条件。 例4 分母是1001的最简分数一共有多少个？ 分析：这一题实际上就是找分子中不能整除1001的数。由于1001=7×11×13，所以就是找不能被7，11，13整除的数。 例5 某个班的全体学生在进行了短跑、游泳、投掷三个项目的测试后，有4名学生在这三个项目上都没有达到优秀，其余每人至少有一项达到了优秀，达到了优秀的这部分学生情况如下表：短跑游泳投掷短跑、游泳短跑、投掷游泳、投掷短路、游泳、投掷 1 7 1 8 1 5 6 6 5 2 求这个班的学生共有多少人？ 分析：这个班的学生数，应包括达到优秀和没有达到优秀的。 试一试：一个班有42人，参加合唱队的有30人，参加美术组的有25人，有5人什么都没有参加，求两种都参加的有多少人？