组合数学在数学竞赛中的应用---毕业论文

目录1.引言..................................................................12组合数学与数学竞赛简介.................................................12.1组合数学............................................................12.2数学竞赛............................................................13组合数学的几种方法在数学竞赛中的应用..................................23.1抽屉原理............................................................23.2容斥原理............................................................23.3排列组合............................................................84.探索高中数学竞赛中的组合问题..........................................94.1熟练掌握四个基本的技术原理..........................................94.2学习组合数学的几点建议.............................................104.3培养学生的组合性思维和组合思想.....................................114.4常见排列组合的解题策略.............................................11参考文献...............................................................12致谢..................................................................12组合数学在数学竞赛中的应用CombinatorialMathematicsinAppliedMathematics(0521110329Class2Grade2005Mathematics&AppliedMathematicsSchoolofMathematics&Information)Abstract:Mathematicalcompetitionsinhighschoolandjuniorhighschoolareverypopularinwhichtheportfolioproblemaccountsforalargeproportion.Asforthisissue,thewritercombineswiththeportfoliomathematicsandcompetitivemathematicsinuniversity,andadoptsthedrawerprinciple,exclusionprincipleandpermutationandcombinationmethodstomaketheresearchanddiscussion.Importantly,thewritercarriesnewresearchontheproblemsofcombinationinmathematicalcompetition.Keywords:order;combination;drawerprinciple;Exclusionprinciple1.引言组合数学是可以追溯到公元前2200既古老而又年轻的数学分支,它的源泉可以追溯到公元前2200年的大禹时期，中外历史上许多著名的数字游戏是它古典部分的主要内容.公元1666年，德国著名数学家莱布尼茨为它请名为“组合学”(Combinatorics),并预言了这一数学分支的诞生.随着科学技术的发展，组合数学这门历史悠久的学科得到了迅速发展．数学活动离不开解题，掌握数学的一个重要标志就是善于解题．现在专门以中学生为对象的数学竞赛成为时代的时尚，本论文希望结合组合数学和数学竞赛有关理论知识，针对在数学竞赛中占很大比例的组合问题，利用大学组合数学理论给出解释，并结合初等数学向学生渗透和合理讲解．在此过程中，提出自己直接的见解和总结．2.组合数学与数学竞赛简介2.1组合数学组合数学历史悠久，几千年前，我国的《河图》、《洛书》就已涉及一些简单有趣的组合问题．组合问题在日常生活中也随处可见．例如，在玩扑克牌游戏中计算“同花顺”的概率、一笔画和幻方等都是组合数学问题．组合数学自20世纪60年代急速发展的部分原因在于计算机在我们的生活中所发挥的重要影响，而且这种影响还在继续发挥．由于远算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的．近年来，由于计算机科学、编码理论、规划论、数字通讯、试验设计、社会科学、生物科学等学科的迅猛发展，大大促进了组合数学的研究，使这一古老的数学分支成为了一门充满活力的数学学科．组合数学可以一般地描述为：组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科．现代的组合数学几乎是与图论不可分割的．图论是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法．有关图论的第一篇文章是由著名瑞士学家欧拉写于1736年，他探讨的是著名的哥尼斯堡七桥问题，图论在智力难题和游戏方面有着历史根源，而今天它为许多学科的研究提供了一种非常重要的语言和框架．2.2数学竞赛围绕着数学竞赛而开展的各种活动已经搭起了一个数学教育新分支的框架，其特点是以开发智力为根本目的、以问题解决为基本形式、以竞赛数学为主要内容．最本质的是对中学生进行“竞赛数学”的教育，这种教育的性质是：较高层次的基础教育、开发智力的素质教育、生动活泼的业余教育、现代教学的普及教育．竞赛数学是一中“中间数学”，介乎于中小学与大学数学之间；竞赛数学是一种“前沿数学”，追求内容的新颖性，不断推陈出新，时刻涌现出新问题新方法和新结果；竞赛数学是一种“艺术数学”，它把现代化的内容与趣味性的问题有机结合，把普遍性的问题与独创性的技巧有机结合，展示出数学美的魅力；竞赛数学是一种“教育数学”，它称为教育数学中最接近研究数学的“先头部队”，利用自己所处的地位，大量地、方便地吸收着前沿成果初等化，也把古典问题高等化．3.组合数学的几种方法在数学竞赛中的应用3.1抽屉原理抽屉原理又称鸽巢原理或重叠原理，是组合数学的两大基本原理之一，是一个极其初等而又应用较广的数学原理．抽屉原理要解决的是存在性问题，即在具体的组合问题中，要解决某些特定问题求解的方案数，其前提就是要知道这些方案的存在性．定理3.1.1（基本形式）将1n个物品放入n个抽屉，则至少有一个抽屉中的物品数不少于两个．证反证之．将抽屉编号为：1,2,...n，设第i个抽屉放有iq个物品，则12...1nqqqn但若定理结论不成立，即1iq，亦有12...nqqqn，从而有121...nnqqqn矛盾．定理3.1.2（推广形式）将12...1nqqqn个物品放入n个抽屉，则下列事件至少有一个成立：即第i个抽屉的物品数不少于iq个，1,2,...in．证反证．不然，设第i个抽屉的物品数小于(1,2,...)iqin（即该抽屉最多有1iq个物品），则有11niiqn物品总数111nniiiiqqn与假设矛盾．根据定理的结果，不难得出下述结论．推论3.1.1将(1)1nr个物品放入n个抽屉，则至少有一个抽屉中的物品个数不少于r个．推论3.1.2将m个物品放入n个抽屉，则至少有一个抽屉中的物品个数不少于11mmnn个．其中x表示取正数x的整数部分，x表示不小于x的最小整数．推论3.1.3若n个正整数(1,2,...,)iqin满足12...1nqqqr则至少有一个iq，满足iqr．利用抽屉原理可以得到下面两个性质：性质1任意三个整数中，必有两个整数的和是2的倍数．性质2任意五个整数中，必有三个整数的和是3的倍数．例1任意15个整数中，必有8个整数的和是8的倍数．证15个整数是任意的，所以我们用1231415,,....,aaaaa这15个字母来表示，有性质1，123,,aaa中122aaa（a为整数），同理可得，456,,aaa中有452aab（b为整数），789,,aaa中782aac（c为整数），101112,,aaa中10112aad（d为整数）。有性质1得2abm（m为整数）2cdn（n为整数），13,,mna中2mne（e为整数）128....2()4()8aaaabcdmne．证毕例2任意三个整数，必有两个之和为偶数（其差也为偶数）．证制造两个抽屉：“奇数”和“偶数”，3个数放入两个抽屉，必有一个抽屉中至少有两个数．有整数求和的奇、偶性质，即知此二数之和比为偶数．同理可知，二者之差也为偶数．例3某俱乐部有31n名成员．对每一个人，其余的人中恰好有n个愿与他打网球，n个愿与他下象棋，n个愿与他打乒乓球．证明该俱乐部至少有3个人，他们之间玩的游戏三种俱全．证将每个人作为平面上的一个点，且任何三点不共线．由每一点引出n条红边、n条蓝边、n条黑边，分别代表打网球、下象棋及打乒乓球．问题等价于要证明图中至少有一个三边颜色全部相同的三角形．考虑有这个31n点的所有连边构成的异色角（即两条异色的边所构成的角）的总数．每个顶点处有23n个异色角，所以23(31)Lnn平均每个三角形有23313(31)6231nnnnCn个异色角．因此，至少有一个三角形有3个异色角，那么，这个三角形的三条边当然互不同色．证毕．例4设ABC为一等边三角形，E是三边上点的全体．对于每一个把E分成两个不交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点证如下图，在边BCCAAB上分别取三点P、Q、R，显然△ARQ，△BPR，△CQP都是直角三角形．它们的锐角是30°及60°．设E1，E2是E的两个非空子集，且1212,EEEEE由抽屉原则P、Q、R中至少有两点属于同一子集，不妨设P、Q∈E1．如果BC边上除P之外还有属于E1的点，那么结论已证明．设BC的点除P之外全属于E2，那么只要AB上有异于B的点S属于E2，设S在BC上的投影点为S′，则△SS′B为直角三角形．再设AB内的每一点均不属于E2，即除B之外全属于E1，特别，R、A∈E1，于是A、Q、R∈E1，且AQR为一直角三角形，从而命题得证．【评述】此例通过分割图形构造抽屉．在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决．例5：在1,4,7,10,13,,100中任选出20个数，其中至少有不同的两组数，和都等于104，试证明之．（第39届美国普特南数学竞赛题）证给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合．{1},{52},{4,100},{7,97},{49,55}．且把它们分作是18个抽屉，从已知的34个数中任取20个数，即把前面两个抽屉中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104．【评述】此例是根据某两个数的和为104来构造抽屉．一般地，与整数集有关的存在性问题也可根据不同的需要利用整数间的倍数关系、同余关系来