您所在位置：主题：[原创]鸽笼原理
killercat
[专家分：1330] 发布于 2005-05-13 17:42:00
问题一：
如果你手头上有n+1个整数，而这些整数是小于或等于2n，那么你一定会有一对数是互素的。
解答：把1～2n的整数排成一列，1,2,3,4,5,...,2n 。我们这样组一系列有序对：（1,2），（3,4)，（5,6)，（7,8)，...（2n-1,2n) 一共有n组，现在取n+1个数，必然有一个数取于同一个集合，又由于相邻两个数一定互素，所以，必定有一对数是互数的。
思路说明：
每一个利用鸽笼原理的题目必须找到鸽子和笼子，但是重要的是，如何找到鸽子和笼子，以及它们的特点。下面我们做仔细的分析：
1)寻找鸽子，笼子。
在解决鸽笼问题，我们所要做的事，就是放鸽子，正是由于这个原因，鸽子一定“受动”，比如上题，是取数，取数这个动作对象是“n+1个整数”，也就说明了这n+1个整数将作为鸽子。而“非受动”的就是“2n个数”，为笼子。
现在我们由“非受动”，“受动”决定鸽笼。非受动＝鸽笼，受动＝鸽子。
2)鸽笼特点。
特点很简单，在可以使用鸽笼原理的地方，鸽子数目一定大于笼子数目。
所以，我们要做的就是找到 鸽子>笼子。就上面题目说明，我们由1步骤得到的鸽子是n-1<2n，笼子>鸽子，不合理，所以，必须转化，显然鸽子数目无法改变，所以改变笼子，把2n个数重新两两组合，得到一个新的笼子，n个有序对（2原组），这样我们要的条件就满足了。不过在构造新的时候，一定要注意，每个笼子一定一样大，比如我们构造（1,2,3),(4,5)就不对了，不对的原因是由鸽笼原理所决定的，这里就不多说了。
问题二：五个大头钉在等边三角板里的位置问题。
有一个每边长2单位的正三角形（即三边都相等的三角形）的三角板。
你随便在上面钉上五个大头钉，一定会有一对大头钉的距离是小过1单位。
解答：受动的是大头针（鸽子）。非受动的是三角形（笼子）。
现在大头针>三角形，看似乎满足原理，但这里是一个笼子，所以，这里又引出一点要注意的，就是一个笼子来解决鸽笼问题是没有意义的，大家从鸽笼原理的定义是可以分析出来的。那么我们应该如何划分，显然这题目是要划大，把1个笼子化为小于5个笼子，而且上面我们强调了，划分的笼子一定要一样大，现在对象是一个边长为2的等边三角形，划分一样大的，怎么划，大家一定都想到了，就是取每边的中点，划成4个等边三角形，它们显然都是边长为1的等边三角形，现在笼子定好了，放5个钉子，至少有2个在一个边为1的等边三角形里面，很容易就可以证明它们距离小于1。
问题三：斐波那契数列的一个性质的证明。
斐波那契数列：1，1，2，3，5，8，13，21，34，…
如果你用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除后的余数），现在用鸽笼原理证明：鸽子（受动）前两项之和与K取余，笼子余数是0，1，2，…，K－1。鸽子数目未定，根据前面原理，鸽子>笼子，所以我们可重复做前两项之和与K取余，直到余数K个时，那么必定有一组同余。得证。
其实同样的一个分数 P/Q 一定可以化为一个循环小数，也是对余数用鸽笼原理来证明的。
问题四：已给一个由10个互不相等的两位十进制正整数组成的集合。
求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。
证明：２的１０次方，为１０２４。它的子集合的取值范围是：１０～９０＋９１＋９２＋９３＋９４＋９５＋９６＋９７＋９８＋９９＝８５５，所以和的取值有８４６种。由于鸽笼原理，至少有２个集合，使得A中各数之和=B中各数之和。若A∩B=φ，则命题得证，若A∩B=C≠φ，即A与B有公共元素，这时只要剔除A与B中的一切公有元素，得出两个不相交的子集A1与B1，很显然 A1中各元素之和=B1中各元素之和，因此A1与B1就是符合题目要求的子集。
总结：用鸽笼问题时
１） 用“静态”和“非静态”来决定鸽笼；
２） 判断鸽子和笼子是否满足 鸽子>笼子，不满足转化；（笼子数目永远大于１）
３） 转化时，经常是转化笼子，划分笼子时，一定是等大小划分。
由于时间问题，还有题目我就不在举例了，这里只是提供个大家一个思路，当然，在一些深奥的问题中也许不适用，但这样分析的思想，也许能对明白鸽笼原理而使用有一定困难的朋友带来一点帮助。以上纯属于个人观点，希望大家指点。
如果你手头上有n+1个整数，而这些整数是小于或等于2n，那么你一定会有一对数是互素的。
解答：把1～2n的整数排成一列，1,2,3,4,5,...,2n 。我们这样组一系列有序对：（1,2），（3,4)，（5,6)，（7,8)，...（2n-1,2n) 一共有n组，现在取n+1个数，必然有一个数取于同一个集合，又由于相邻两个数一定互素，所以，必定有一对数是互数的。
思路说明：
每一个利用鸽笼原理的题目必须找到鸽子和笼子，但是重要的是，如何找到鸽子和笼子，以及它们的特点。下面我们做仔细的分析：
1)寻找鸽子，笼子。
在解决鸽笼问题，我们所要做的事，就是放鸽子，正是由于这个原因，鸽子一定“受动”，比如上题，是取数，取数这个动作对象是“n+1个整数”，也就说明了这n+1个整数将作为鸽子。而“非受动”的就是“2n个数”，为笼子。
现在我们由“非受动”，“受动”决定鸽笼。非受动＝鸽笼，受动＝鸽子。
2)鸽笼特点。
特点很简单，在可以使用鸽笼原理的地方，鸽子数目一定大于笼子数目。
所以，我们要做的就是找到 鸽子>笼子。就上面题目说明，我们由1步骤得到的鸽子是n-1<2n，笼子>鸽子，不合理，所以，必须转化，显然鸽子数目无法改变，所以改变笼子，把2n个数重新两两组合，得到一个新的笼子，n个有序对（2原组），这样我们要的条件就满足了。不过在构造新的时候，一定要注意，每个笼子一定一样大，比如我们构造（1,2,3),(4,5)就不对了，不对的原因是由鸽笼原理所决定的，这里就不多说了。
问题二：五个大头钉在等边三角板里的位置问题。
有一个每边长2单位的正三角形（即三边都相等的三角形）的三角板。
你随便在上面钉上五个大头钉，一定会有一对大头钉的距离是小过1单位。
解答：受动的是大头针（鸽子）。非受动的是三角形（笼子）。
现在大头针>三角形，看似乎满足原理，但这里是一个笼子，所以，这里又引出一点要注意的，就是一个笼子来解决鸽笼问题是没有意义的，大家从鸽笼原理的定义是可以分析出来的。那么我们应该如何划分，显然这题目是要划大，把1个笼子化为小于5个笼子，而且上面我们强调了，划分的笼子一定要一样大，现在对象是一个边长为2的等边三角形，划分一样大的，怎么划，大家一定都想到了，就是取每边的中点，划成4个等边三角形，它们显然都是边长为1的等边三角形，现在笼子定好了，放5个钉子，至少有2个在一个边为1的等边三角形里面，很容易就可以证明它们距离小于1。
问题三：斐波那契数列的一个性质的证明。
斐波那契数列：1，1，2，3，5，8，13，21，34，…
如果你用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除后的余数），现在用鸽笼原理证明：鸽子（受动）前两项之和与K取余，笼子余数是0，1，2，…，K－1。鸽子数目未定，根据前面原理，鸽子>笼子，所以我们可重复做前两项之和与K取余，直到余数K个时，那么必定有一组同余。得证。
其实同样的一个分数 P/Q 一定可以化为一个循环小数，也是对余数用鸽笼原理来证明的。
问题四：已给一个由10个互不相等的两位十进制正整数组成的集合。
求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。
证明：２的１０次方，为１０２４。它的子集合的取值范围是：１０～９０＋９１＋９２＋９３＋９４＋９５＋９６＋９７＋９８＋９９＝８５５，所以和的取值有８４６种。由于鸽笼原理，至少有２个集合，使得A中各数之和=B中各数之和。若A∩B=φ，则命题得证，若A∩B=C≠φ，即A与B有公共元素，这时只要剔除A与B中的一切公有元素，得出两个不相交的子集A1与B1，很显然 A1中各元素之和=B1中各元素之和，因此A1与B1就是符合题目要求的子集。
总结：用鸽笼问题时
１） 用“静态”和“非静态”来决定鸽笼；
２） 判断鸽子和笼子是否满足 鸽子>笼子，不满足转化；（笼子数目永远大于１）
３） 转化时，经常是转化笼子，划分笼子时，一定是等大小划分。
由于时间问题，还有题目我就不在举例了，这里只是提供个大家一个思路，当然，在一些深奥的问题中也许不适用，但这样分析的思想，也许能对明白鸽笼原理而使用有一定困难的朋友带来一点帮助。以上纯属于个人观点，希望大家指点。
