鸽笼原理的一个问题-991灵签网

鸽笼原理的一个问题

发布在新闻页面，知道MP3图片，视频，百科，求助。

添加搜索返回百度百科首页编辑词条鸽巢原理，也叫鸽子洞原理，是拉姆齐定理的特例。

它的简单形式是:将n+1个对象放入n个盒子中，至少一个盒子中包含两个或两个以上的对象。

下面给出一个简单形式的拉姆齐定理:

设p和q为正整数，p，q >；= 2，存在一个最小正整数R(p，q)，使得当n >；当=R(p，Q)时，如果Kn的边被涂上红色和蓝色，则要么存在一个蓝色的完全P形，要么存在一个红色的完全Q形。

拉姆齐定理的适用范围更广，这里就不赘述了。有兴趣的话可以看看组合数学方面的书。

已知N+1个正整数，都小于等于2n。证明了一定有两个数互质*。

这个问题被伟大的匈牙利数学家保罗·埃尔德解决了？s，1913-1996)到博沙(路易P？Sa)提出，而小波沙思考不到半分钟就能给出正确的答案，而且他的回答是如此巧妙和精彩，以致鄂尔多斯大为惊异。

在列举波萨解之前，学生可以自己思考解，然后才能深刻理解波萨解的奥秘。

波沙的解决方案是这样的:

假设有n个盒子，把1和2放在1的盒子里，3和4放在第二个盒子里，5和6放在第三个盒子里，...，2n-1和第n个框中的2n。

如果从这n个盒子中随机抽取n+1个数字，将抽取至少一个盒子的两个数字。由此可知，这个数n+1中一定有一对连续数，显然这两个连续数是互质的。

这个问题好容易解决啊！

以一种相对浅薄的方式来阐明上述问题，可以说:

对于一个每层有4个间隔的6层鸽舍，它有6 ^ 4 = 24个鸽舍。现在把25只鸽子放进鸽舍，你一定会看到其中一个鸽舍里有两只鸽子挤在一起！

*互质:设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。

具有这种特殊性质的数叫做素数。

我们小学没学过分解整数因子吗？也就是用质数的乘积来表示一个整数。比如50 = 2× 5× 5，108 = 2× 2× 3× 3× 3。

两个自然数叫做互质。如果把它们表示为质数的乘积，就不能发现它们有一个共同的质因数。比如{8，11}一对数互质。10和108不是互质的，因为它们有一个共同的质因数2。

现在我们来了解一下鄂尔多斯的问题。首先考虑一些特殊情况:

当n=2时，我们手头有三个小于等于4的整数，只能选择{2，3，4}，不包括1。显然，{2，3}或{3，4}是互质的。

当n=3时，在小于等于6的整数中找出四个整数组(不包括1)，可能的有{2，3，4，5}、{2，3，4，6}、{3，4，5，6}、{2，4，5，6}等。逐一检查，你会发现每组至少有一对互质数。

可以看出，随着n的增加，n+1个不同数的数组数量会大大增加。如果我们把这些数组一个一个的检查证明，那真的会变成:“我的生命是有限的，但数量是无限的”。到时候不仅用不完，最后还会“唉”！

如果读者中有人说:“我有吃苦耐劳的精神！”“我还是想劝他不要用那么辛苦的功夫，要学会‘巧做’，这才是最重要的。不然别的孩子不到半分钟就能解决问题，而我们靠努力和勤奋一辈子都解决不了。这不是浪费生命吗？

我现在就来介绍一下Posa对这个问题的解决方案。但希望读者先自己思考，看看如何解决这个问题。如果你能找到不同于下面的解决方案，请写信告诉我。如果你花了一段时间也想不通，请继续读下去，你会欣赏到波萨解决方案的别出心裁，最重要的是，你会学到“鸽笼原理”，也许你将来成为业余数学家或职业数学家时会用到这个原理！

Posa是这样考虑问题的:取n个盒子，第一个盒子我们放1和2，第二个盒子放3和4，第三个盒子放5和6，以此类推，直到第n个盒子放2n-1和2n。

现在我们从n个盒子里随机抽取n+1个数字。我们立刻看到一个箱子肯定被抽空了。所以n+1中有两个数是连续数，显然这两个连续数是互质的。所以这个问题就解决了！

你觉得这个解决方案是不是很好理解，很聪明？！

三、鸽子笼原理

波萨在他的证明中使用了数学上称为鸽子洞原理的东西。这个原理是这样的:如果你把n+1个东西放进n个盒子里，有些盒子里至少要装2个东西。

有六层的鸽笼，每层有四个空间，所以总共有6× 4 = 24个鸽笼。现在我在里面放了25只鸽子，你一定看到有一个鸽子笼，两只鸽子会挤在一起。

鸽笼的原理这么简单，3岁以上的孩子都会懂。

然而，这个原理在数学中有非常重要的应用。

19世纪，一位名叫狄利克雷(1805-1859)的数学家，在数论研究中，巧妙地运用鸽笼原理解决问题。后来，德国数学家闵·古斯基(Minkowski 1864-1909)也利用这个原理得到了一些结果。

20世纪初，图雷(A. Thue1863-1922)在不知道狄利克雷和闵古斯基工作的情况下，巧妙地利用鸽子笼原理解决了不定方程有理数解的问题，12篇论文使用了这一原理。

后来，西格尔(C.L.Siegel，1896-？)我们利用图雷的结果发现了现在所说的Siegen引理，这个引理是研究超越数最基本最必要的工具。

所以，读者不要小看这个看似简单的原理。如果你善于使用它，它可以帮助你解决一些数学问题。

四、鸽笼原理的日常应用

我给你一些和日常生活相关的问题，你可以在这里看到数学的应用。

(1)天黑穿袜子。

有一天晚上，你房间的灯突然坏了，你看不到你的手指，你想出去，于是你摸到了床底下的袜子。你有三双红、白、蓝三种颜色的袜子，但是平时做事很随便，一脱下来就扔了。在黑暗中你无法知道哪一双是同色的。

你想拿出最少的袜子，借外面的路灯做一双同色的。最小数量应该是多少？

如果你知道鸽笼原理，你就会知道你只需要拿出四只袜子。

为什么？因为如果我们有三个画着红白蓝的盒子，里面放着颜色相反的袜子，只要拿出四只袜子，其中一个盒子一定是空的，那么从这个空盒子里拿出来的袜子就可以穿了。

(2)指纹和头发

据说世界上没有两个人的指纹是相同的，所以警方在处理犯罪时非常重视指纹，希望通过指纹来破案或验证犯人。

但你知道吗，在中国654.38+0.2亿人口中，至少有两个人的头发量是一样的？

原因很简单，人类头发的数量不会超过654.38+0.2亿！假设一个人最多有n根头发。现在让我们想象一个编号为1，2，3，4，…一直到n的房子。

谁有同样数量的头发，谁就进房子。所以张乐平先生的《三毛》应该进《三号院》。

现在假设每个房间进了一个人，还剩下“9亿减N”个人，这个数字不会等于零。现在，我们会随机选择一个，放在一个和他一样头发数的房子里，他会遇到和他一样头发数的战友。

(3)剧院观众的生日

在一个能容纳1500个座位的剧场里，证明如果剧场满座，至少要有5个观众在同一个月的同一天出生。

现在假设一年有365天。想象一个大鸽笼，上面有标着“1月1日”、“1月2日”、“12月31日”的区间。

假设现在每个区间塞进四个人，那么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，1，1，1，…

如果你把每一项除以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)如果你把17随机钉在一个每边2个单位的正三角形板上。

(3)如果将五个钉子随机钉在每边有两个单元的正方形板上，

(4)我们必须能够在一个每边长2个单位的正方形板上恰当地钉上9个钉子，使其中没有钉子，两个钉子之间的距离小于1个单位。

(5)(英国数学奥林匹克1975题)如果在一个半径为1的圆板上钉了七个钉子，使两个钉子之间的距离大于等于1，那么这七个钉子一定有一个位置正好在圆心上。