组合数学在奥林匹克数学中的应用

《组合数学在奥林匹克数学中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要1关键词1Abstract1Keywords1鸽巢原理21.1鸽巢原理21.2鸽巢原理在奥林匹克数学中的应用32排列与组合52.1四个基本的计数原理52.2集合的排列与组合及其在奥林匹克数学中的应用62.3多重集的排列与组合及其在奥林匹克数学中的应用8231多重集的排列82.3.2多重集的组合93容斥原理io3.1.容斥原理113.2错位扫卡列问题123.3容斥原理在奥林匹克数学中的应用13结束语1415参考文献组合数学在奥林匹克数学中的应用学生姓名：学号：数学与信息科学学院数学与应用数学专业指导老师：职称：摘要：奥林匹克数学竞赛在中学很受欢迎，其中组合问题占了很大的一部分.本

2、文结合大学组合数学理论给出解释，并采用鸽巢原理、排列组合方法和容斥原理进行研究和讨论.关键词：奥林匹克数学竞赛；鸽巢原理；排列组合；容斥原理TheapplicationofthecombinatorialmathematicsintheOlympicmathematicsAbstract:Olympicmathematicscompetitionsinmiddleschoolareverypopular,inwhichtheCombinatorialproblemsaccountsforalargeproportion.Inthisarticlewecombineswiththeu

3、niversityofcombinatorialmathematicstheoryandexplanations,andadoptsthepigeonnestprinciple,permutationandcombinationmethodsandexclusionprincipletomaketheresearchanddiscussion.Keywords:Olympicmathematicscompetitions;pigeonnestprinciple;permutationandcombinationmethods;exclusionprinciple0前言组合数学是研究

4、离散数学结构的存在、计数、分析和优化等问题的一门学科.它源于数学游戏.组合数学早期研究的内容是对象的安排数，及符合特定条件的安排是否存在.公元1666年徳国著名数学家莱布尼茨为它命名为“组合学"(Combinatorics),并预言了这一分支的诞生.随着计算机科学的发展和口益增多的组合问题的出现，丰富和发展了组合理论.近些年，数学奥林匹克这一群众性数学课外活动，逐渐在广大学生中发展起来•对于竞赛屮的一些问题，很难把它们归类为代数问题或几何问题，但它们涉及到的解题目标和解题方法可以归入组合问题和组合分析•本论文希望结合组合数学和奥林匹克数学竞赛有关理论知识，针对竞赛中的组合问题，利用

5、大学组合数学理论给出解释•由于组合体系异常庞大，本文仅从鸽巢原理、排列组合、充斥原理三个方面在数学奥林匹克屮常见的问题进行分析、讨论、总结.1鸽巢原理鸽巢原理也叫做Dirichlet抽屉原理或鞋盒原理是一个极其初等而又应用广泛的数学原理•应用它可以解决许多有趣的问题，并且常常得到一些令人惊异的结果.它常被用来证明一些存在性的数学问题，并且在数论和密码学中也有着广泛的应用.对于一些比较特殊的问题，若用一般的数学方法去研究很复杂或根本解决不了，但用鸽巢原理往往能起到事半功倍的效果，所以鸽巢原理是奥林匹克数学竞赛中的重要内容，在数学竞赛中具有很大的应用意义.应用这个原理在解初等数学题时，

6、对启迪思维，开阔视野，掌握解题规律都是有益的.1.1鸽巢原理⑴⑵定理2.1.1（简单形式）如果斤+1个物体被放进刃个盒子，那么至少有一个盒子包含两个或更多的物体.证明：将盒子编号为：1,2,・・・/,设第i个盒子有⑺个物体，则Qi+$2+・・・+乞F+1•但若定理结论不成立，即《51，亦有$+込+…+从而有71+1=4+%+•••+9“5斤矛盾.由此定理可得到以下性质：性质1任意三个整数中，必有两个整数的和是2的倍数.性质2任意五个整数中，必有三个整数的和是3的倍数.定理3.1.2（加强形式）令q,q“・・q为正整数.如果将务+%+•••+%_〃+1个物体放入比个盒子内，则下列事

7、件至少有一个成立：即第2•个盒子的物品数不少于4个，i—1,2,...11.•证明：设将引+%+・・・+%-〃+1个物体分放到斤个盒子中.如果对于每个i=第i个盒子含有少于4个物体，那么所有盒子中的物体总数不超过（创_1）+（?2_1）+…+（乞_1）=旺+02+•••+%_〃该数比所分发的物体总数少1,因此我们断言，对于某一个心1,2,../.,第i个盒子至少包含品⑺个物体.显然当4=弘二…二％=2时，鸽巢原理的加强形式即为简单形式.根据定理的结果，不难得出下述结论