鸽巢原理及其应用的论文答辩

Lon_fee 经理 五级(3414) | 我的百科 | 我的知道 | 我的消息(0/39) | 我的空间 | 百度首页 | 退出 新闻 网页 贴吧 知道 MP3 图片 视频 百科 帮助 添加到搜藏 返回百度百科首页 编辑词条 鸽巢原理 鸽巢原理也叫抽屉原理，是Ramsey定理的特例 。 它的简单形式是 ： 把n＋1个物体放入n个盒子里，则至少有一个盒子里含有两个或两个以上的物体 。 下面再给出Ramsey定理的简单形式： 设p,q是正整数，p,q>= 2,则存在最小的正整数R(p,q),使得当n>=R(p,q)时，用红蓝两色涂色Kn的边，则或者存在一个蓝色的完全p边形，或者存在一个红色的完全q边形 。 Ramsey的定理还有适用范围更广的推广形式，这里不再赘述 。有兴趣的可以查看组合数学方面的书籍。 已知n + 1个正整数，它们全都小于或等于2n，证明当中一定有两个数是互质*的。 这道问题由匈牙利大数学家厄杜斯 (Paul Erdös, 1913 - 1996) 向当年年仅11岁的波沙 (Louis PÓsa) 提出，而小波沙思考了不足半分钟便能给出正确的答案，而他的解答又是那么巧妙和精采，令厄杜斯赞叹不已。 在列出波沙的解答前，同学可先自己想一想解决方法，之后便能更深刻体会小波沙的解答的奥妙之处。 波沙的解法是这样的： 假设有n个盒子，在第1个盒子中放1和2、在第2个盒子中放3和4、在第3个盒子中放5和6、……、在第n个盒子中放2n - 1和2n。 若从在这n个盒子中随意抽出n + 1个数，其中最少有一个盒子的两个数均会被抽出。由此，可知这n + 1个数中必定有一对连续数，而明显地连续数是互质的。 这道问题便这样轻易解决了！ 以较显浅的说法来阐明上述的问题，可以这样说： 对于一个高6层，而每层有4个间隔的鸽巢，它共有6 4 = 24个鸽房。现把25只鸽子放进鸽巢，必定可以看到其中一个鸽房会有2只鸽子挤在一起！ * 互质：设a和b为正整数，若a和b的最大公因数是1，则a和b互质。 一、一个匈牙利数学家小时的故事 路易·波萨（Louis Pósa）是匈牙利的年青数学家，1988年时约40岁。他在14岁时就已能够发表有相当深度的数学论文。大学还没有读完，就已获得科学博士的头衔。 他的妈妈是一个数学家。小时他受母亲的影响，很爱思考问题。母亲看他对数学有兴趣，也鼓励他在这方面发展。她给他一些数学游戏，或数学玩具启发他独立思考问题。在母亲的循循善诱之下，他在读小学时已经自己拿高中的数学书来看了。真正训练他成为一个数学家的是匈牙利鼎鼎有名的大数学家。 厄杜斯在数论、图论等数学分支有很深入的研究，他把一生献给数学，从来没有想到结婚，只和自己的母亲为伴，他经常离开自己的祖国到外国去作研究和演讲。在东欧国家里像厄杜斯能这样随意离开自己的国家进出西方世界的数学家并不太多。他到处以数学会友，他在数学方面的多产，以及在解决问题上有巧妙的方法，使他在世界数学界上享有甚高的声誉。对于他的祖国来讲，他重要的贡献不单是在数学的研究，而是他一回到自己的国家就专心致志地培养年青一代的数学家，告诉他们外国目前数学家注意的问题，扩大他们的视野。 我这里要讲他怎么样发现路易·波萨的才能的故事。 有一次他从国外回来后，听到朋友讲起有一个很聪明的小东西，在小学能解决许多困难的数学问题，于是就登门拜访这小鬼的家庭。 波萨的家人很高兴请厄杜斯教授共进晚餐。在喝汤的时候，厄杜斯想考一考坐在他旁边的12岁小孩的能力，于是就问他这样的一个问题： “如果你手头上有n+1个整数，而这些整数是小于或等于2n，那么你一定会有一对数是互素的。你知道这是什么原因吗？” 这小鬼不到半分钟的思考，就很快给出这个问题的解答。他的解答又是那么巧妙，使得厄杜斯教授叹服。认为这是一个难得的“英才”，应该好好地培养。 厄杜斯以后系统地教这小鬼数学，不到两年的时间波萨就成为一个“小数学家”了，而且发现在图论一些深湛的定理。 二、波萨怎样解决厄杜斯提的问题 对于许多离开学校很久的读者，我想做一点解释厄杜斯提出的问题。 首先我们解释：一对数是互素是什么意思？ 我们知道如果把自然数1，2，3，4，5，…照大小排起来，从2开始像2，3，5，7，11，13，17，19，23，…，等数都有这样特别的性质：除1和本身以外，再找不到比它小的数能整除它。 具有这样特殊性质的数我们称它为素数（Prime number）。 我们小学时不是学习过把整数因子分解吗？那就是把整数用素数的乘积来表示。例如50＝2×5×5，108=2×2×3×3×3 两个自然数称为互素（Coprime），如果把它们表示成素数乘积时，找不到它们有公共的素因数。例如{8，11}一对数是互素。10和108不是互素，因为它们有公共的素因数2。 现在让我们来理解厄杜斯的问题。先对一些特殊的情况来考虑： 当n=2时，我们手头上有3个整数，这些整数是小于或等于4，可以选出的只是{2，3，4}，不包含1，很明显的看出{2，3}或{3，4}是互素的。 n=3时，在小于或等于6的整数找4个整数组（不包含1），可能找出的有{2，3，4，5}，{2，3，4，6}，{3，4，5，6}，{2，4，5，6}等等。你一个个检查一定会在每组中找出最少一对互素的数。 可以看出随着n增大时，构造n＋1个不同数的数组的个数就会增加很大。如果我们是这样一个一个地对这些数组来检查证明，这真会成为：“吾生也有涯，而数无涯”，那时候皓首不但穷尽不了，最后真是要“呜呼哀哉”了！ 如果读者中有人说：“我有苦干和拚命干的精神！”我还是要劝他不要用这样的苦干法，应该学会“巧干”，这才是最重要的。不然的话，人家小孩子用不到半分钟就解决了的问题，而我们苦干再加上拚命干却花一生还没法子解决，这不是太浪费生命吗？ 我现在准备介绍波萨对这问题的解法。可是我希望读者先自己想想看怎么样解决这问题。如果你能找到和下面不同的解决方法，请来信告诉我。如果你花过一些时间还想不出，那么就请读下去，你这时就会欣赏波萨解决方法的巧妙，而最重要的你会学懂“鸽笼原理”，说不定以后你成为业余数学家或者专业数学家还会用到这个原理呢！ 波萨是这样考虑问题：取n个盒子，在第一个盒子我们放1和2，在第二个盒子我们放3和4，第三个盒子是放5和6，依此类推直到第n个盒子放2n-1和2n这两个数。 现在我们在n个盒子里随意抽出n＋1个数。我们马上看到一定有一个盒子是被抽空的。因此在这n+1个数中曾有两个数是连续数，很明显的连续数是互素的。因此这问题就解决了！ 你说这个解法是不是很容易明白又非常巧妙呢？！ 三、鸽笼原理 波萨在证明过程中用到在数学上称为鸽笼原理（PigeonholePrinciple）的东西。这原理是这样说的：如果把n+1个东西放进n个盒子里，有一些盒子必须包含最少2个东西。 有高六层的鸽笼，每一层有四个间隔，所以总共有6×4＝24个鸽笼。现在我放进25只鸽进去，你一定看到有一个鸽笼会有2只鸽要挤在一起。 鸽笼原理就是这么简单，3岁以上的小孩子都会明白。 可是这原理在数学上却是有很重要的应用。 在19世纪时一个名叫狄利克雷（Dirichlet 1805—1859）的数学家，在研究数论的问题时最早很巧妙运用鸽笼原理去解决问题。后来德国数学家敏古斯基（Minkowski 1864—1909）也运用这原理得到一些结果。 到了20世纪初期杜尔（A．Thue 1863—1922）在不知道狄利克雷和敏古斯基的工作情况下，很机巧地利用鸽笼原理来解决不定方程的有理数解的问题，有12篇论文是用到这个原理。 后来西根（C．L．Siegel，1896—？）利用杜尔的结果发现了现在称为西根引理的东西，这引理（Lemma）是在研究超越数时是最基本必用的工具。 因此读者不要小看这个看来简单的原理，你如果善于运用是能帮助你解决一些数学难题的。 四、鸽笼原理的日常运用 我这里举一些和日常生活有关的一些问题，你可以看到数学在这里的运用。 （1）月黑风高穿袜子 有一个晚上你的房间的电灯忽然间坏了，伸手不见五指，而你又要出去，于是你就摸床底下的袜子。你有三双分别为红、白、蓝颜色的袜子，可是你平时做事随便，一脱袜就乱丢，在黑暗中不能知道哪一双是颜色相同的。 你想拿最少数目的袜子出去，在外面借街灯配成同颜色的一双。这最少数目应该是多少？ 如果你懂得鸽笼原理，你就会知道只需拿出去四只袜子就行了。 为什么呢？因为如果我们有三个涂上红、白、蓝的盒子，里面各放进相对颜色的袜子，只要我们抽出4只袜子一定有一个盒子是空的，那么这空的盒子取出的袜子是可以拿来穿。 （2）手指纹和头发 据说世界上没有两个人的手指纹是一样的，因此警方在处理犯罪问题时很重视手指纹，希望通过手指纹来破案或检定犯人。 可是你知道不知道：在12亿中国人当中，最少有两个人的头发是一样的多？ 道理是很简单，人的头发数目是不会超过12亿这么大的数目字！假定人最多有N根头发。现在我们想像有编上号码1，2，3，4，…一直到N的房子。 谁有多少头发，谁就进入那编号和他的头发数相同的房子去。因此张乐平先生的“三毛”应该进入“3号房子”。 现在假定每间房巳进入一个人，那么还剩下“九亿减N”个人，这数目不会等于零，我们现在随便挑一个放进一间和他头发数相同的房子，他就会在里面遇到和他有相同头发数目的同志了。 （3）戏院观众的生日 在一间能容纳1500个座位的戏院里，证明如果戏院坐满人时，一定最少有五个观众是同月同日生。 现在假定一年有三百六十五天。想像有一个很大的鸽子笼，这笼有编上“一月一日”，“一月二日”，至到“十二月三十一日”为止的标志的间隔。 假定现在每个间隔都塞进四个人，那么 4×365=1460个是进去鸽子笼子里去，还剩下1500-1460=40人。只要任何一人进入鸽子笼，就有五个人是有相同的生日了。 五、鸽笼原理在数学上的运用 现在我想举一些数学上的问题说明鸽笼原理的运用。 （1）斐波那契数的一个性质 斐波那契数列是这样的数列：1，1，2，3，5，8，13，21，34，…。从1，1以后的各项是前面两项的数的和组成。 在18世纪时法国大数学家和物理学家拉格朗日（J．L．La-grange）发现这斐波那契数有这样有趣的性质： 如果你用2来除各项，并写下它的余数，你会看到这样的情形1，1，0，1，1，0，1，1，0，… 如果用3来除各项，写下它的余数，你就得到 1，1，2，0，2，2，1，0，1，1，2，0，2，2，1，0，… 如果用4来除各项，写下它的余数，你就会得到 1，1，2，3，1，0，1，1，2，3，1，0，… 现在观察用2除所得的数列，从开头算起每隔三段，后面的数列就重复前面的数列。用3除所得的数列，从开头算起每隔八段，后面的数列就重复前面的数列样子。对于以4除所得的余数数列也有同样的情况：每隔六段，后面的数列就重复前面的数列样子。 拉格朗日发现不管你用什么数字去除，余数数列会出现有规律的重复现象。 为什么会有这样的现象呢？ 如果我们用一个整数K来除斐波那契数列的数，它可能的余数是0，1，2，…，K－1。 由于在斐波那契数的每一项是前面两项的和，它被K除后的余数是等于前两项被K除余数的和。（注意：如果这和是大过K，我们取它被K除后的余数）只要有一对相邻的余数重复出现，那么以后的数列从那对数开始就会重复出现了。不同对相邻余数可能的数目有K2个，因此由鸽笼原理，我们知道只要适当大的项数，一定会有一对相邻余数重复。因此斐波那契数列的余数数列会有周期重复现象。 （2）五个大头钉在等边三角板里的位置 有一个每边长2单位的正三角形（即三边都相等的三角形）的三角板。 你随便在上面钉上五个大头钉，一定会有一对大头钉的距离是小过一单位。 你不相信的话，可以做几次实验看看是否一直是如此。我现在要用鸽笼原理来解决这个问题。 在三角板的每边取中点，然后用线段连结这些中点，把这正三角形分成四个全等的小正三角形图。现在在每一个小三角形里任何两点的距离是不会超过1个单位。 由于我们有五个大头钉，不管怎么样放一定有两个要落进同一个小正三角形里，因此这两个大头钉的距离是不会超过一个单位。 六、动脑筋 想想看 （1）给出任意12个数字，证明当用11来除时，一定有一对数的余数是相同。 （2）如果在一个每边都是2单位的正三角形板上随便钉上17个大 （3）如果在一个每边都是2单位的正方形板上随便钉上5根钉， （4）我们一定能够在一个每边都是2单位长的正方形板上适当的钉上9根钉，使它们之中不存在有两根钉的距离是小于1单位。 （5）（英国数学奥林匹克1975年的问题）在一个半径为1单位的圆板上钉7个钉，使得两个钉的距离是大过或等于1，那么这7个钉一定会有一个位置恰好是在圆心上。 （6）任意6个人在一起，一定会有其中两种情形之一发生：第一种情形——有3个人互相认识。第二种情形——有3个人，他们之间完全不认识。 （7）（a）你能不能在从1到200的整数里挑选出100个自然数，使到任何其中之一不能整除剩下的99个数。 （b）证明如果在从1到200间随便取101个自然数，那么一定最少有两个自然数，其中之一能整除另外的数。 （8）随便给出10个10位数的数字，我们一定能把它分成两部分，使到每一部分的整数的和是等于其他一部分的整数的和。[编辑本段]简单形式 如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。 例1：在13个人中存在两个人，他们的生日在同一月份里。 例2：设有n对已婚夫妇。为保证有一对夫妇被选出，至少要从这2n个人中选出多少人？（n+1）[编辑本段]加强形式 令q1,q2,...qn为正整数。如果将 q1+q2+...+qn-n+1个物体放入n个盒子内,那么或者第一个盒子至少含有q1个物体,或者第二个盒子 至少含有q2个物体,...,或者第n个盒子含有qn个物体. 例1:一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9 个橘子，则放入篮子中的水果的最小件数是多少？（21件）

把这2n个数分成n组 （1，2）（3，4）。。。（2n－1，2n）即n个鸽巢 之后取n＋1个数 就是有n＋1只鸽子 必然有两数字属于同一组数 那么他们两就互素了 关键在于构造鸽巢