组合数学论文

1抽屉世界——从小抽屉中看大组合作者：李……2摘要抽屉原理又称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原则。它是组合数学中一个很重要的原理。抽屉原理的内容简明朴素，易于接受，它在数学问题的解决中有重要的作用。许多有关存在性的证明都可用它来解决。但在有些问题中，“抽屉”和“物体”不是很明显的，需要精心制造“抽屉”和“物体”.如何制造“抽屉”和“物体”有时会很困难的，往往这时我们首先需要认真地分析题目中的条件和问题，再根据以往做题所积累的经验进行制造。懂得制造抽屉是运用抽屉原则的一大关键。3关键词：组合数学，抽屉原理，应用实例，心得感受。18*14=252抽屉世界——从小抽屉中看大组合抽屉原理作为组合数学中一个重要的组成部分，其应用之广泛可想而知。第一抽屉原理：○1把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。○2把多于mn+1(m乘以n加一)个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。○3把无穷多件物体放入n个抽屉，则至少有一个抽屉里有无穷个物体。第二抽屉原理：把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体。抽屉原理虽然简单，但应用却很广泛，它可4以解答很多有趣的问题，其中有些问题还具有相当的难度。就我做过需要利用到抽屉原理的题目中，有一道很经典的题目，同时也是1958年6/7月号的《美国数学月刊》上的一道题目。即：证明在任意6个人的集会上，或者有3个人以前彼此相识，或者有三个人以前彼此不相识。一开始看到这道题我觉得这不可能呀，我觉得所要证明的内容本身就是错的。所以我没有立即进行证明，而是举例来进行反驳，可是无论我怎么假设，所要证明的结论总是成立。我这才开始思考该从何入手来进行证明。我只知道这道题一定会用到抽屉原理，但到底是在哪用如何用还是不清楚，短暂的思考之后，终于有了头绪。首先用六个点分别代表六个人，任取一个点M，把M点到其他五点间连五条线段，用红黑两种颜色分别代表相互认识和彼此不认识，用这两种色将五条线段分别着色，由抽屉定理[5/2]+1=3可知,至少有三条线段是同一种颜色，不妨假设是红色，且这三条线段的另一端点分别为A，B，C(见图)。再来讨论A，B，C三点间的连线的颜色问题，只要5它们间的三条线段有任意一条为红色，则该线段的两个端点和M点构成了一个红色的三角形，即有三个人以前相互认识。若三条线段全为黑色，则表示有三人彼此互不相识。从而结论得证。这样一个看似无法解决的难题，只是稍稍运用了抽屉原理就迎刃而解了，只是这个转化的过程不是太容易想到，这类组合问题往往都是这样的，制造“抽屉”和“物体”是解决问题的关键，懂得制造抽屉是运用抽屉原则的一大关键。还有一个问题也很有趣，在我没有看答案之前，我一直没有想通。那是一个关于重叠和覆盖的问题：有21个点在边长为12的6三角形中，证明用一个半径为√3（）的圆纸片总可以盖住其中的三个点。一看到这题我就想到要用抽屉原理，由21和3可知，这道题需将这个三角形分为7~10份。于是我就将三角形如下图般分割：。可分割完后发现每一小个三角形无法用半径为√3（）的圆纸片盖住。所以我继续分析，发现半径为√3（）的圆纸片正好是边长为3的正三角形的外接圆。于是我将三角形如下图般分割：。但这样分割后我觉得用10个圆不可能完全覆盖，这里一共有16个三角形，10个圆只能完全覆盖十个7三角形，还是不能证明结果。可看完答案后我才知道我的思路并没有错，只是我没有去尝试，而是直接就否定了自己的方案，如果我动手去画一画，就可以依靠自己的能力解决这道题了。最终的方法是：用十个圆覆盖，每个圆覆盖一个，同时每相交的三个圆共同再覆盖一个，这样就将整个大三角形完全覆盖了。又因为[21/10]+1=3，从而结论得证。从做这个问题的整个过程中，我有很多感触：做有些题目不可能一次就做对的，需要不断的尝试，而且要勇于尝试，并且不能光用脑袋想，要动笔把思考的内容大概的描述一下，只有这样才能更进一步的确认自己的思路是否正确。总之，抽屉原理是组合数学中一个很重要的原理，在日常生活中也有很重要的应用。