2012抽屉原理在初等数学中的运用.docVIP

抽屉原理在初等数学中的运用 摘要：抽屉原理也称为鸽原理，它是组合数学中的一个最基本的原理抽屉原理的简单形式可以描述为：“如果把个球或者更多的球放进个抽屉，必有一个抽屉至少有两个球.”它的正确性十分明显，如果将其灵活地运用，可得到一些意想不到的效果.如招生录取、就业安排、资源分配、职称评定等等都不难看到抽屉原理的作用 各种形式的抽屉原理在高等中经常采用，使用该原理的关键在于如何巧妙地抽屉，即如何找出合乎问题条件的分类原则，抽屉造得好，可得出非常巧妙的结论鸽原理有五个鸽子笼，养鸽人养了6只鸽子，当鸽子飞回 除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式.比如陈景林、阎满富编著的中国铁道出版社出版的《组合数学与图论》一书中对抽屉原理给出了比较具体的定义，概括起来主要有下面种形式把多于的元素按任一确定的方式分成个集合，则一定有一个集合中含有两个或两个以上的元素.把个元素任意放到个集合里，则至少有一个集合里个元素，其中  原理3 把无穷个元素按任一确定的方式分成有穷个集合，则至少有一个集合中仍含无穷个元素. 卢开澄在《组合数学》（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广[2]. 鸽巢原理：设k和n都是任意正整数，若至少有kn+1只鸽子分配在n个鸽巢中，则至少存在一个鸽巢中有至少k+1只鸽子. 二、抽屉的构造途径 在利用抽屉原理解题时，首先要明确哪些是“球”，哪些是“抽屉”，而这两者通常不会现成存在于题目中，尤其是“抽屉”往往需要我们用一些巧妙的方法去构造,使得任何份答卷中都存在4份，其中每2份的答案都至多3题相同.的最小可能值.(2000，中国数学奥林匹克) 解：将每道题的4种答案分别记为1，2，3，4，每份试卷上的答案记为，其中，令，=1，2，3，4，共得256个四元组. 由于2000=2567+208，故由抽屉原理知，有8份试卷上的答案属于同一个四元组.取出这8份试卷后，余下的1992份试卷中仍有8份属于同一个四元组，再取出这8份试卷，余下的1984份试卷中又有8份属于同一个四元组.又取出这8份试卷.三次共取出24份试卷，在这24份试卷中，任何4份中总有2份的答案属于同一个四元组，不满足题目的要求.所以，. 下面证明=25. 令则=256，且中去掉6个元素，当余下的250种答案中的每种答案都恰有8人选用时，共得到2000份答案，其中的25份答案中，总有4份不相同.由于它们都在中，当然满足题目要求.这表明，=25满足题目要求. 综上可知，所求的的最小可能值为25. 先运用抽屉原理给出的下界，然后用构造法给出例子.这是一道典型的运用构造法解题的好题目.在解题中合理构造抽屉往往会收到意想不到的效果. 例2： 任给7个实数，证明必存在两个实数满足01+.设七个实数为作=(),显然∈)，把)等分成六个区间：)，)，)，)，)，)，抽屉原理，必有两个属于同一区间，不妨设为,而不论，由正切函数的单调性可知，，不妨记则=,而由知0， (),1+, 从而有01+例从1-100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个是另一个的整数倍。 分析：其关键其实就在“两个数”，其中一个是另一个的整数倍。我们要构造“抽屉”，每个抽屉任取两个数，有一个是另一个的整数倍，只有把公比是正整数的整个等比数列都放同一个抽屉才行，这里用得到一个自然数分类的基本知识：任何一个正整数都可以表示成一个奇数与2的方幂的积，即若m∈N+,K∈N+，n∈N,则m=(2k-1)·2n，并且这种表示方式是唯一的，如1=1×2°，2=1×21，3=3×2°，…　　证明：因为任何一个正整数都能表示成一个奇数乘2的方幂，并且这种表示方法是唯一的，所以我们可把1-100的正整数分成如下50个抽屉（因为1-100中共有50个奇数）： 　　（1）{1，1×2，1×22，1×23，1×24，1×25，1×26}；　　（2）{3，3×2，3×22，3×23，3×24，3×25}；　　（3）{5，5×2，5×22，5×23，5×24}；　　（4）{7，7×2，7×22，7×23}；　　（5）{9，9×2，9×22，9×23}；　　　　……　　（25）{49，49×2}；　　（26）{51}；　　　　……　　（50）{99}。 　　这样，1-100的正整数就无重复，无遗漏地放进这50个抽屉内了。从这100个数中任取51个数，也即从这50个抽屉内任取51个数，根据抽屉原则，其中必定至少有两个数属于同一个抽屉，即属于（1）-（25）号中的某一个抽屉，显然，在这25个抽屉中的任何同一个抽屉内的两个数中，一个是另一个的整数倍。 说明：（1）从上面的证明中可以看出，本题能够推广到