文库精心推荐：鸽笼原理

鸽笼原理_学习方法网 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 一、一个匈牙利数学家小时的故事 路易middot;波萨（Louis Poacute;sa）是匈牙利的年青数学家，1988年时约40岁。他在14岁时就已能够发表有相当深度的数学论文。大学还没有读完，就已获得科学博士的头衔。 他的妈妈是一个数学家。小时他受母亲的影响，很爱思考问题。母亲看他对数学有兴趣，也鼓励他在这方面发展。她给他一些数学游戏，或数学玩具启发他独立思考问题。在母亲的循循善诱之下，他在读小学时已经自己拿高中的数学书来看了。真正训练他成为一个数学家的是匈牙利鼎鼎有名的大数学家。 厄杜斯在数论、图论等数学分支有很深入的研究，他把一生献给数学，从来没有想到结婚，只和自己的母亲为伴，他经常离开自己的祖国到外国去作研究和演讲。在东欧国家里像厄杜斯能这样随意离开自己的国家进出西方世界的数学家并不太多。他到处以数学会友，他在数学方面的多产，以及在解决问题上有巧妙的方法，使他在世界数学界上享有甚高的声誉。对于他的祖国来讲，他重要的贡献不单是在数学的研究，而是他一回到自己的国家就专心致志地培养年青一代的数学家，告诉他们外国目前数学家注意的问题，扩大他们的视野。 我这里要讲他怎么样发现路易middot;波萨的才能的故事。 有一次他从国外回来后，听到朋友讲起有一个很聪明的小东西，在小学能解决许多困难的数学问题，于是就登门拜访这小鬼的家庭。 波萨的家人很高兴请厄杜斯教授共进晚餐。在喝汤的时候，厄杜斯想考一考坐在他旁边的12岁小孩的能力，于是就问他这样的一个问题 ldquo;如果你手头上有n1个整数，而这些整数是小于或等于2n，那么你一定会有一对数是互素的。你知道这是什么原因吗rdquo; 这小鬼不到半分钟的思考，就很快给出这个问题的解答。他的解答又是那么巧妙，使得厄杜斯教授叹服。认为这是一个难得的ldquo;英才rdquo;，应该好好地培养。 厄杜斯以后系统地教这小鬼数学，不到两年的时间波萨就成为一个ldquo;小数学家rdquo;了，而且发现在图论一些深湛的定理。 二、波萨怎样解决厄杜斯提的问题 对于许多离开学校很久的读者，我想做一点解释厄杜斯提出的问题。 首先我们解释一对数是互素是什么意思 我们知道如果把自然数1，2，3，4，5，hellip;照大小排起来，从2开始像2，3，5，7，11，13，17，19，23，hellip;，等数都有这样特别的性质除1和本身以外，再找不到比它小的数能整除它。 具有这样特殊性质的数我们称它为素数（Prime number）。 我们小学时不是学习过把整数因子分解吗那就是把整数用素数的乘积来表示。例如50＝2times;5times;5，1082times;2times;3times;3times;3＝22times;33。 两个自然数称为互素（Coprime），如果把它们表示成素数乘积时，找不到它们有公共的素因数。例如{8，11}一对数是互素。10和108不是互素，因为它们有公共的素因数2。 现在让我们来理解厄杜斯的问题。先对一些特殊的情况来考虑 当n2时，我们手头上有3个整数，这些整数是小于或等于4，可以选出的只是{2，3，4}，不包含1，很明显的看出{2，3}或{3，4}是互素的。 n3时，在小于或等于6的整数找4个整数组（不要包含1），可能找出的有{2，3，4，5}，{2，3，4，6}，{3，4，5，6}，{2，4，5，6}等等。你一个个检查一定会在每组中找出最少一对互素的数。 可以看出随着n增大时，构造n＋1个不同数的数组的个数就会增加很大。如果我们是这样一个一个地对这些数组来检查证明，这真会成为ldquo;吾生也有涯，而数无涯rdquo;，那时候皓首不但穷尽不了，最后真是要ldquo;呜呼哀哉rdquo;了 如果读者中有人说ldquo;我有苦干和拚命干的精神rdquo;我还是要劝他不要用这样的苦干法，应该学会ldquo;巧干rdquo;，这才是最重要的。不然的话，人家小孩子用不到半分钟就解决了的问题，而我们苦干再加上拚命干却花一生还没法子解决，这不是太浪费生命吗 我现在准备介绍波萨对这问题的解法。可是我希望读者先自己想想看怎么样解决这问题。如果你能找到和下面不同的解决方法，请来信告诉我。如果你花过一些时间还想不出，那么就请读下去，你这时就会欣赏波萨解决方法的巧妙，而最重要的你会学懂ldquo;鸽笼原理rdquo;，说不定以后你成为业余数学家或者专业数学家还会用到这个原理呢 波萨是这样考虑问题取n个盒子，在第一个盒子我们放1和2，在第二个盒子我们放3和4，第三个盒子是放5和6，依此类推直到第n个盒子放2n-1和2n这两个数。 现在我们在n个盒子里随意抽出n＋1个数。我们马上看到一定有一个盒子是被抽空的。因此在这n1个数中曾有两个数是连续数，很明显的连续数是互素的。因此这问题就解决了 你说这个解法是不是很容易明白又非常巧妙呢 三、鸽笼原理 波萨在证明过程中用到在数学上称为鸽笼原理（PigeonholePrinciple）的东西。这原理是这样说的如果把n1个东西放进n个盒子里，有一些盒子必须包含最少2个东西。 有高六层的鸽笼，每一层有四个间隔，所以总共有6times;4＝24个鸽笼。现在我放进25只鸽进去，你一定看到有一个鸽笼会有2只鸽要挤在一起。 鸽笼原理就是这么简单，3岁以上的小孩子都会明白。 可是这原理在数学上却是有很重要的应用。 在19世纪时一个名叫狄利克雷（Dirichlet 1805mdash;1859）的数学家，在研究数论的问题时最早很巧妙运用鸽笼原理去解决问题。后来德国数学家敏古斯基（Minkowski 1864mdash;1909）也运用这原理得到一些结果。 到了20世纪初期杜尔（A．Thue 1863mdash;1922）在不知道狄利克雷和敏古斯基的工作情况下，很机巧地利用鸽笼原理来解决不定方程的有理数解的问题，有12篇论文是用到这个原理。 后来西根（C．L．Siegel，1896mdash;）利用杜尔的结果发现了现在称为西根引理的东西，这引理（Lemma）是在研究超越数时是最基本必用的工具。 因此读者不要小看这个看来简单的原理，你如果善于运用是能帮助你解决一些数学难题的。 四、鸽笼原理的日常运用 我这里举一些和日常生活有关的一些问题，你可以看到数学在这里的运用。 （1）月黑风高穿袜子 有一个晚上你的房间的电灯忽然间坏了，伸手不见五指，而你又要出去，于是你就摸床底下的袜子。你有三双分别为红、白、蓝颜色的袜子，可是你平时做事随便，一脱袜就乱丢，在黑暗中不能知道哪一双是颜色相同的。 你想拿最少数目的袜子