组合数学-鸽巢原理讲义

组合数学讲义(内部资料，严禁商用) 第二章 鸽巢原理和Ramsey 定理 2008-2009学年第二学期第二章 鸽巢原理和Ramsey 定理一、鸽巢原理鸽巢原理是组合数学中的一个重要而又基本的原理，它可以用来解决很多日常生活和科学技术上的趣题，并且常能得到一些令人惊异的结果。

这个原理有各种称呼，最常用的名称是鸽巢原理、Dirichlet 抽屉原理和鞋盒原理。

1、问题的引入1) 366个人中必然有至少两个人生日相同。

2) 抽屉里散放着10双手套，从中任意抽取11只，其中至少有两只是成双的。

3) 某次会议有n 位代表参加，每位代表认识其他代表中某些人，则至少有两个人认识的人数是一样的。

4) 任给5个不同的整数，其中至少有3个数的和被3除尽。

这些例子的道理都很简单，以第一个例子为例，一年365天，366个人至少有一天是某两个人的生日。

最后一例子也有类似的道理，5个数中至少有3个同为奇数或同为偶数，无论哪种情况，它们的和都能被3除尽。

2、鸽巢原理的简单形式定理1、如果把1+n 只鸽子放入n 个鸽巢，则至少有一个鸽巢里含有两只或两只以上鸽子。

证明：反证法。

假设每个鸽巢里至多包含一只鸽子，则n 个鸽巢里鸽子的总数小于等于n ，这与已知矛盾。

注：此原理不能用来寻找究竟是那个鸽巢里含有两只或两只以上鸽子。

即此原理只能用来断定这种鸽巢的存在，并未指出怎样构造这种安排或怎样寻找出现这种现象的场合，除非检查所有的可能情况。

此原理的应用：例1、 已知每个人的头发根数都小于20万，对20万人以上的城市就可以断定，至少有两个人头发根数相等。

例2、在边长为1的正三角形中任意放5个点，证明至少有两个点之间的距离不大于21。

证明：构造鸽巢原理如图1,将5个点放在4个边长为21的小正三角形内，根据鸽巢原理，组合数学讲义(涉外学院数学本科用) 2008-2009学年第二学期 制作人 陈勇 必有一个小三角形内至少有两个点，这两个点的距离就小于或等于21。

鸽巢原理（抽屉原理）的详解抽屉原理百科名⽚桌上有⼗个苹果，要把这⼗个苹果放到九个抽屉⾥，⽆论怎样放，我们会发现⾄少会有⼀个抽屉⾥⾯放两个苹果。

这⼀现象就是我们所说的“抽屉原理”。

抽屉原理的⼀般含义为：“如果每个抽屉代表⼀个集合，每⼀个苹果就可以代表⼀个元素，假如有n+1或多于n+1个元素放到n个集合中去，其中必定⾄少有⼀个集合⾥有两个元素。

” 抽屉原理有时也被称为鸽巢原理（“如果有五个鸽⼦笼，养鸽⼈养了6只鸽⼦，那么当鸽⼦飞回笼中后，⾄少有⼀个笼⼦中装有2只鸽⼦”）。

它是组合数学中⼀个重要的原理。

第⼀抽屉原理原理1：把多于n+1个的物体放到n个抽屉⾥，则⾄少有⼀个抽屉⾥的东西不少于两件。

证明（反证法）：如果每个抽屉⾄多只能放进⼀个物体，那么物体的总数⾄多是n，⽽不是题设的n+k(k≥1)，故不可能。

抽屉原理原理2 ：把多于mn(m乘以n)个的物体放到n个抽屉⾥，则⾄少有⼀个抽屉⾥有不少于m+1的物体。

证明（反证法）：若每个抽屉⾄多放进m个物体,那么n个抽屉⾄多放进mn个物体,与题设不符，故不可能。

原理3 ：把⽆穷多件物体放⼊n个抽屉，则⾄少有⼀个抽屉⾥有⽆穷个物体。

原理1 、2 、3都是第⼀抽屉原理的表述。

第⼆抽屉原理把（mn－1）个物体放⼊n个抽屉中，其中必有⼀个抽屉中⾄多有（m—1）个物体。

证明（反证法）：若每个抽屉都有不少于m个物体，则总共⾄少有mn个物体，与题设⽭盾，故不可能。

应⽤基本介绍应⽤抽屉原理解题抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作⽤。

许多有关存在性的证明都可⽤它来解决。

例1：同年出⽣的400⼈中⾄少有2个⼈的⽣⽇相同。

解：将⼀年中的365天视为365个抽屉，400个⼈看作400个物体，由抽屉原理1可以得知：⾄少有2⼈的⽣⽇相同. 400/365=1…35,1+1=2　⼜如：我们从街上随便找来13⼈，就可断定他们中⾄少有两个⼈属相相同。

“从任意5双⼿套中任取6只，其中⾄少有2只恰为⼀双⼿套。

第五章 抽屉原理和Ramsey 理论抽屉原理又称鸽巢原理或重叠原理，是组合数学中两大基本原理之一，是一个极其初等而又应用较广的数学原理。

其道理并无深奥之处，且正确性也很明显。

但若能灵活运用，便可能得到一些意料不到的结果。

抽屉原理要解决的是存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。

1930年英国逻辑学家F. P. Ramsey 将这个简单原理作了深刻推广，即Ramsey 定理，也被称为广义抽屉原理。

它是一个重要的组合定理，有许多应用。

5.1 抽屉原理（一）基本形式定理5.1.1 （基本形式）将n ＋1个物品放入n 个抽屉，则至少有一个抽屉中的物品数不少于两个。

证 反证之。

将抽屉编号为：1,2, …,n ，设第i 个抽屉放有i q 个物品，则 121+=+++n q q q n但若定理结论不成立，即1≤iq ，即有n q q q +++ 21≤n ，从而有 n q q q n n ≤+++=+ 211矛盾。

例 5.1.1 一年365天，今有366人，那么，其中至少有两人在同一天过生日。

注：与概率的区别：抽屉原理讲的是所给出的结论是必然成立的，即100%成立。

而概率反映的是不确定性现象发生的可能性问题，不讨论100%成立的确定性概率问题。

生日悖论：随机选出n 个人，则其中至少有二人同一天出生的概率为()A P n =n n P 3651365-特例：()A P 23=50.73%，()A P 100=99.99997%例 5.1.2 箱子中放有10双手套，从中随意取出11只，则至少有两只是完整配对的。

（二）推广形式定理5.1.2 （推广形式）将121+-+++n q q q n 个物品放入n 个抽屉，则下列事件至少有一个成立：即第i 个抽屉的物品数不少于i q 个。

（证）反证。

不然，设第i 个抽屉的物品数小于i q （i ＝1,2, …,n ）(即该抽屉最多有1-i q 个物品)，则有11+-∑=n q n i i ＝物品总数≤()n q q ni i n i i -=-∑∑==111与假设矛盾。

第1章鸽巢原理鸽巢原理〔又叫抽屉原理〕指是一件简单明了事实：为数众多一群鸽子飞进不多巢穴里，那么至少有一个巢穴飞进了两只或更多鸽子。

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

1.1 鸽巢原理简单形式鸽巢原理简单形式可以描述为：定理1.1.1 如果把个物品放入个盒子中，那么至少有一个盒子中有两个或更多物品。

证明如果每个盒子中至多有一个物品，那么个盒子中至多有个物品，而我们共有个物品，矛盾。

故定理成立。

鸽巢原理只断言存在一个盒子，该盒中有两个或两个以上物品，但它并没有指出是哪个盒子，要想知道是哪一个盒子，那么只能逐个检查这些盒子。

所以，这个原理只能用来证明某种安排存在性，而对于找出这种安排却毫无帮助。

例1 共有12个属相，今有13个人，那么必有两人属相一样。

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

证明把边长为1正方形分成4个边长为小正方形，如图1.1.1所示，在大正方形内任取5点，那么这5点分别落在4个小正方形中。

由鸽巢原理知，至少有两点落在某一个小正方形中，从而这两点间距离小于或等于小正方形对角线长度。

例3 给出个整数，证明：必存在整数，使得证明构造局部与序列那么有如下两种可能：〔i〕存在整数，使得，此时，取即满足题意。

〔ii〕对任一整数i，均有，令，那么有，这样，个余数均在1到m-1之间。

由鸽巢原理知，存在整数，使得。

不妨设，那么综合〔i〕与〔ii〕，即知题设结论成立。

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

证明令分别为这11周期间他每天下棋次数，并作局部与根据题意，有且所以有〔1.1.1〕考虑数列它们都在1与之间，共有154项，由鸽巢原理知，其中必有两项相等，由〔1.1.1〕式知这77项互不相等，从而这77项也互不相等，所以一定存在，使得因此这说明从第天到第天这连续天中，他刚好下了21盘棋。

第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则有如下两种可能：（i ）存在整数(1)h h m ≤≤，使得h m s ，此时，取0,k l h ==即满足题意。

（ii ）对任一整数i ，均有(1)i m s i m ≤≤，令(mod)i i r s m =，则有11(1)i r m i m ≤≤-≤≤，这样，m 个余数均在1到m-1之间。

《鸽巢问题》课件一、引言鸽巢问题，又称鸽笼原理，是组合数学中的一个基本定理，它揭示了有限集合与无限集合之间的关系。

在日常生活中，鸽巢问题有着广泛的应用，如安排座位、分配任务等。

本课件旨在阐述鸽巢问题的基本概念、证明方法及其在实际中的应用。

二、鸽巢问题的基本概念2.抽象鸽巢原理：设有两个集合A和B，其中A的元素个数大于B的元素个数。

如果存在一个从A到B的映射，那么至少有一个B中的元素，其对应的A中元素个数不少于两个。

三、鸽巢问题的证明方法2.构造法：将n个容器编号为1,2,,n，将n+1个物体编号为1,2,,n+1。

将第i个物体放入编号为i%n+1的容器中（%表示取余数）。

由于n+1不能被n整除，至少有一个容器内有编号为i和i+n+1的两个物体。

四、鸽巢问题的应用1.安排座位：在教室、会议室等场所，如果人数超过座位数，那么至少有两个座位被两个人共同使用。

2.分配任务：在项目或团队中，如果任务数超过人数，那么至少有两个人共同完成一个任务。

3.证明存在性问题：在数学、物理等领域，鸽巢问题可以用来证明某些存在性问题，如质数定理、素数定理等。

五、总结鸽巢问题作为一个基本定理，揭示了有限集合与无限集合之间的关系。

通过归谬法、构造法、反证法等方法，我们可以证明鸽巢原理的正确性。

在实际应用中，鸽巢问题有着广泛的应用，如安排座位、分配任务等。

掌握鸽巢问题，有助于我们更好地理解和解决实际问题。

一、归谬法的详细解释二、构造法的详细解释构造法是一种证明方法，它通过构造一个具体的例子来证明命题的正确性。

在鸽巢问题中，我们可以构造一个具体的放置物体的方式。

将n个容器编号为1,2,,n，将n+1个物体编号为1,2,,n+1。

将第i个物体放入编号为i%n+1的容器中。

由于n+1不能被n整除，至少有一个容器内有编号为i和i+n+1的两个物体。

这个具体的构造例子证明了鸽巢原理的正确性。

三、反证法的详细解释四、鸽巢问题证明方法的应用鸽巢问题的证明方法不仅可以用来证明鸽巢原理本身，还可以用来解决其他问题。