- 鸽巢原理
天上有十个鸽子，这十个鸽子要飞到九个鸽巢里，无论怎样飞，我们会发现至少会有一 个鸽巢里面放两个鸽子，这一现象就是我们所说的“鸽巢原理”。鸽巢定理由狄里克利于1834 年提出，当时命名为 Schubfachprinzip (drawer principle)。
鸽巢原理的一般含义为：“如果每个鸽巢代表一个集合，每一个鸽子就可以代表一个元素，假如有 n 或多于n 个元素放到n-1 个集合中去，其中必定至少有一个集合里有两个元素。” 这是组合数学中一个重要的原理。
第一鸽巢原理:
-
- 把多于 n 个的物体放到 n-1 个鸽巢里，则至少有一个鸽巢里的东西不少于两件。
- 把多余 mn+1（n!=0）个的物体放到 n 个鸽巢里，则至少有一个鸽巢里有不少于（m+1）的物体。
- 把无穷多件物体放入 n 个鸽巢，则至少有一个鸽巢里有无穷个物体。第二鸽巢原理：
把（mn-1）个物体放入 n 个鸽巢里，其中必有一个鸽巢中至多有（m-1）个物体。
- 鸽巢原理应用技巧
运用鸽巢原理的核心是分析清楚问题中，哪个是鸽子，哪个是鸽巢，而鸽巢往往是问题中数量较少的那一方。先来看一个有意思的问题，众所周知世界上没有两个人的手指纹是一样的，因此警方在追查犯罪问题时很重视手指纹，希望通过手指纹来找到嫌疑人。可是大家或许不知道：在 12 亿中国人当中，最少有两个人的头发是一样的多。道理很简单，人的头发数目是不会超过 12 亿这么大的数目字！假定人最多有 N 根头发。现在我们想像有编上号码 1，2，3，4，…一直到 N 的房子。 谁有多少头发，谁就进入那编号和他的头发数相同的房子去。现在假定每间房巳进入一个人，那么还剩下“九亿减 N”个人，这数目不会等于零， 我们现在随便挑一个放进一间和他头发数相同的房子，他就会在里面遇到和他有相同头发数目的人了。
制造鸽巢是运用鸽巢原理的关键，很多时候可以帮助我们更方便地去求解一些问题。例 如现在我们从 2 至 30 之间的 15 个偶数中，任取 9 个数，则其中一定有两个数之和是 34。
这一点是如何得知的呢？我们可以用上诉 15 个偶数制造 8 个鸽巢，要求制造的鸽巢中有凡是两个数的，都具有一个共同的特点：这两个数的和是 34。现从题目中的 15 个偶数中任取9 个数，由鸽巢原理（因为鸽巢只有 8 个），必有两个数可以在同一个鸽巢中（符合上述特点）.由制造的鸽巢的特点，这两个数的和是 34。
对于整除问题，可以把所有整数按照除以某个自然数 m 的余数分为 m 类，叫做 m 的剩余类或同余类，用[0]，[1]，[2]，…，[m-1]表示。每一个类含有无穷多个数，例如[1]中含有1，m+1，2m+1，3m+1，….在研究与整除有关的问题时，常用剩余类作为鸽巢。根据鸽巢原理，可以证明：任意 n+1 个自然数中，总有两个自然数的差是 n 的倍数。可以证明这样一个例子，我们任取 8 个自然数，必有两个数的差是 7 的倍数。在与整除有关的问题中有这样的性质，如果两个整数 a、b，它们除以自然数 m 的余数相同，那么它们的差 a-b 是 m 的倍数.根据这个性质，本题只需证明这 8 个自然数中有 2 个自然数，它们除以 7 的余数相同. 我们可以把所有自然数按被 7 除所得的 7 种不同的余数 0、1、2、3、4、5、6 分成七类.也就是 7 个鸽巢.任取 8 个自然数，根据鸽巢原理，必有两个数在同一个鸽巢中，也就是它们
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/11974.html