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

目录1.引言 12组合数学与数学竞赛简介. 12.1组合数学 12.2数学竞赛 13组合数学的几种方法在数学竞赛中的应用 23.1抽屉原理 23.2容斥原理 23.3排列组合 84.探索高中数学竞赛中的组合问题 104.1熟练掌握四个基本的技术原理 104.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（基本形式）将SKIPIF1<0个物品放入SKIPIF1<0个抽屉，则至少有一个抽屉中的物品数不少于两个．证反证之．将抽屉编号为：SKIPIF1<0，设第SKIPIF1<0个抽屉放有SKIPIF1<0个物品，则SKIPIF1<0但若定理结论不成立，即SKIPIF1<0，亦有SKIPIF1<0，从而有SKIPIF1<0矛盾．定理3.1.2（推广形式）将SKIPIF1<0个物品放入SKIPIF1<0个抽屉，则下列事件至少有一个成立：即第SKIPIF1<0个抽屉的物品数不少于SKIPIF1<0个，SKIPIF1<0．证反证．不然，设第SKIPIF1<0个抽屉的物品数小于SKIPIF1<0（即该抽屉最多有SKIPIF1<0个物品），则有SKIPIF1<0物品总数SKIPIF1<0与假设矛盾．根据定理的结果，不难得出下述结论．推论3.1.1将SKIPIF1<0个物品放入SKIPIF1<0个抽屉，则至少有一个抽屉中的物品个数不少于SKIPIF1<0个．推论3.1.2将SKIPIF1<0个物品放入SKIPIF1<0个抽屉，则至少有一个抽屉中的物品个数不少于SKIPIF1<0个．其中SKIPIF1<0表示取正数SKIPIF1<0的整数部分，SKIPIF1<0表示不小于SKIPIF1<0的最小整数．推论3.1.3若SKIPIF1<0个正整数SKIPIF1<0满足SKIPIF1<0则至少有一个SKIPIF1<0，满足SKIPIF1<0．利用抽屉原理可以得到下面两个性质：性质1任意三个整数中，必有两个整数的和是2的倍数．性质2任意五个整数中，必有三个整数的和是3的倍数．例1任意15个整数中，必有8个整数的和是8的倍数．证SKIPIF1<0个整数是任意的，所以我们用SKIPIF1<0这15个字母来表示，有性质1，SKIPIF1<0中SKIPIF1<0（a为整数），同理可得，SKIPIF1<0中有SKIPIF1<0（b为整数），SKIPIF1<0中SKIPIF1<0（c为整数），SKIPIF1<0中SKIPIF1<0（d为整数）。有性质1得SKIPIF1<0（m为整数）SKIPIF1<0（n为整数），SKIPIF1<0中SKIPIF1<0（e为整数）SKIPIF1<0．证毕例2任意三个整数，必有两个之和为偶数（其差也为偶数）．证制造两个抽屉：“奇数”和“偶数”，3个数放入两个抽屉，必有一个抽屉中至少有两个数．有整数求和的奇、偶性质，即知此二数之和比为偶数．同理可知，二者之差也为偶数．例3某俱乐部有SKIPIF1<0名成员．对每一个人，其余的人中恰好有SKIPIF1<0个愿与他打网球，SKIPIF1<0个愿与他下象棋，SKIPIF1<0个愿与他打乒乓球．证明该俱乐部至少有3个人，他们之间玩的游戏三种俱全．证将每个人作为平面上的一个点，且任何三点不共线．由每一点引出SKIPIF1<0条红边、SKIPIF1<0条蓝边、SKIPIF1<0条黑边，分别代表打网球、下象棋及打乒乓球．问题等价于要证明图中至少有一个三边颜色全部相同的三角形．考虑有这个SKIPIF1<0点的所有连边构成的异色角（即两条异色的边所构成的角）的总数．每个顶点处有SKIPIF1<0个异色角，所以SKIPIF1<0平均每个三角形有SKIPIF1<0个异色角．因此，至少有一个三角形有3个异色角，那么，这个三角形的三条边当然互不同色．证毕．例4设SKIPIF1<0为一等边三角形，SKIPIF1<0是三边上点的全体．对于每一个把SKIPIF1<0分成两个不交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点证如下图，在边SKIPIF1<0上分别取三点P、Q、R，显然△ARQ，△BPR，△CQP都是直角三角形．它们的锐角是30°及60°．设E1，E2是E的两个非空子集，且SKIPIF1<0由抽屉原则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：在SKIPIF1<0中任选出20个数，其中至少有不同的两组数，和都等于104，试证明之．（第39届美国普特南数学竞赛题）证给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合．SKIPIF1<0．且把它们分作是18个抽屉，从已知的34个数中任取20个数，即把前面两个抽屉中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104．【评述】此例是根据某两个数的和为104来构造抽屉．一般地，与整数集有关的存在性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成抽屉．小结：用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确． 用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律． 用抽屉原则解题的基本思想是根据问题的自身特点和本质，找出分类的规律． 用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”．3.2容斥原理当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择．将整体分解为部分也就是将有限集X表示成它的一组两两互异的非空真子集A1，A2，…An的并集，即SKIPIF1<0叫做集合X的一个覆盖。一个特殊情况是，集族SKIPIF1<0中的任意两个集合都不相交，这时我们称集族SKIPIF1<0为集合X的一个（完全）划分．如SKIPIF1<0为集合X的划分，则对集合X的计数可通过熟知的加法公式 SKIPIF1<0①进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事．我们可以考虑通过对任意的集族中的子集的计数来计算|X|，当集族SKIPIF1<0中至少存在两个集合的交非空时，我们称这个覆盖为集合X的不完全划分．对于集合X的不完全划分，显然有有SKIPIF1<0②因为在计算|Ai|时出现了对某些元素的重复计数，为了计算|X|，就得将②式右边重复计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的工作．完成这项工作的准则就是容斥原理，是十九世纪英国数学家西尔维斯提出的．容斥原理有两个公式．1、容斥公式定理1设SKIPIF1<0 SKIPIF1<0③证明：当SKIPIF1<0由加法公式有 SKIPIF1<0结论成立．若n=k时结论成立，则由 SKIPIF1<0SKIPIF1<0SKIPIF1<0知，SKIPIF1<0时结论成立．由归纳原理知，对任意自然数n，公式③成立．公式③称为容斥公式，显然它是公式①的推广． 如果将SKIPIF1<0看成具有性质SKIPIF1<0的元素的集合，那么SKIPIF1<0就是至少具有n个性质SKIPIF1<0之一的元素的集合．因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目．容斥原理用法总结：在应用容斥原理求解计数问题时，可按下列步骤进行：（1）根据问题的实际情况，构造一个有限集SKIPIF1<0和一个性质集SKIPIF1<0，SKIPIF1<0是SKIPIF1<0中具有性质SKIPIF1<0的所有元素的子集，问题的关键是构造的性质集SKIPIF1<0，要使得SKIPIF1<0容易计算出来SKIPIF1<0．（2）当统计SKIPIF1<0中恰好具有SKIPIF1<0种特征的元素的个数时，将问题转化为求SKIPIF1<0中恰好具有SKIPIF1<0种SKIPIF1<0个性质的元素个数SKIPIF1<0，可利用逐步淘汰原理或一般公式．（3）当统计SKIPIF1<0中至少有SKIPIF1<0中一种性质的元素个数SKIPIF1<0时，利用容斥原理，或由SKIPIF1<0求得．（4）注意SKIPIF1<0，故可由此求得SKIPIF1<0中至少具有SKIPIF1<0种特征的元素个数SKIPIF1<0如SKIPIF1<0时，有SKIPIF1<0．2．筛法公式与容斥公式讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性质的元素的个数，为此，我们先引入下面的引理．引理1设A关于全集I的补集为SKIPIF1<0，则SKIPIF1<0每个元素引理2SKIPIF1<0SKIPIF1<0引理简单证略．利用二引理改写公式③便是定理2设SKIPIF1<0为有限集I的子集，则SKIPIF1<0SKIPIF1<03.错排问题利用容斥原理可以轻而易举地得出同一个公式．SKIPIF1<0个元素依次给以标号SKIPIF1<0,SKIPIF1<0个元素的全排列中，求每个元素都不在原来自己位置上的排列数．设SKIPIF1<0为数SKIPIF1<0在第SKIPIF1<0位上的全体排列，SKIPIF1<0．因数字SKIPIF1<0不动,故SKIPIF1<0同理SKIPIF1<0．每个元素都不在原来位置上的排列数为SKIPIF1<0例1数SKIPIF1<0的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排列数目，实际上是SKIPIF1<0五个数的错排问题，总数为SKIPIF1<0．例2某校六年级二班有49人参加了数学、英语、语文学习小组，其中数学有30人参加，英语有20人参加，语文小组有10人．老师告诉同学既参加数学小组又参加语文小组的有3人，既参加数学又参加英语和既参加英语又参加语文的人数均为质数，而三种全参加的只有1人，求既参加英语又参加数学小组的人数．分析与解：根据已知条件画出图．SKIPIF1<0三圆盖住的总体为49人，假设既参加数学又参加英语的有x人，既参加语文又参加英语的有y人，可以列出这样的方程：SKIPIF1<0整理后得：SKIPIF1<0由于x、y均为质数，因而这两个质数中必有一个偶质数2，另一个质数为7．例3求1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和S．解：1到100的自然数中，所有自然数的和是：SKIPIF1<01到100的自然数中，所有2的倍数的自然数和是：SKIPIF1<01到100的自然数中，所有3的倍数的自然数和是：SKIPIF1<01到100的自然数中，所有既是2的倍数又是3的倍数，即是6的倍数的自然数和是：SKIPIF1<0所以，1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和SKIPIF1<03.3排列组合定义一（排列Permutation）设SKIPIF1<0元集SKIPIF1<0，从SKIPIF1<0中取出SKIPIF1<0个不同元素按次序排列，称为SKIPIF1<0的一个SKIPIF1<0排列，其个数称为SKIPIF1<0排列数，记作SKIPIF1<0或SKIPIF1<0．当SKIPIF1<0时．SKIPIF1<0的SKIPIF1<0排列又称为SKIPIF1<0的全排列，其个数SKIPIF1<0又称全排列数．命题1SKIPIF1<0．证明SKIPIF1<0的一个SKIPIF1<0排列由SKIPIF1<0个不同的元素组成，其中第一位有SKIPIF1<0种可能．第二位有SKIPIF1<0种可能；·······第SKIPIF1<0位有SKIPIF1<0种可能。由乘法原理,SKIPIF1<0元集SKIPIF1<0的不同排列数为SKIPIF1<0推论SKIPIF1<0例1从SKIPIF1<0中任取两个不同的字母构成的字共有SKIPIF1<0个．罗列如下：SKIPIF1<0定义2（组合Combination）设SKIPIF1<0元集SKIPIF1<0，从SKIPIF1<0中取出SKIPIF1<0个不同元素构成一组，称为SKIPIF1<0的一个SKIPIF1<0组合，其个数称为SKIPIF1<0组合数，记作SKIPIF1<0，或SKIPIF1<0．命题2有SKIPIF1<0个不同的元素共可构成SKIPIF1<0种组合，即SKIPIF1<0．证明由定义SKIPIF1<0组合与SKIPIF1<0排列的区别在于前者不计较元素的先后顺序，因此由每个SKIPIF1<0组合可以作出SKIPIF1<0个不同的SKIPIF1<0排列．于是若有SKIPIF1<0种SKIPIF1<0组合，则有SKIPIF1<0种排列，因此SKIPIF1<0．推论1任意SKIPIF1<0个相继的正整数之积可被SKIPIF1<0整除形成多少条，即有SKIPIF1<0．推论2SKIPIF1<0．推论3SKIPIF1<0．推论4SKIPIF1<0元集SKIPIF1<0的SKIPIF1<0元子集的个数等于SKIPIF1<0．推论5设SKIPIF1<0元集SKIPIF1<0，其字典序如下标所示，则从SKIPIF1<0中每次取出满足条件SKIPIF1<0的SKIPIF1<0个元的方式数等于SKIPIF1<0．证明SKIPIF1<0的任一组合都可调整为SKIPIF1<0并使其满足SKIPIF1<0；另一方面，任一满足条件SKIPIF1<0的SKIPIF1<0个元都是SKIPIF1<0的一个SKIPIF1<0组合．例2平面上任三点都不共线的25个点，可形成多少条直线？可形成多少个三角形？解25点中任取2点即可惟一确定一条直线，故可形成SKIPIF1<0条直线；同理，任取3点即可惟一确定一个三角形，故三角形的数目等于SKIPIF1<0．例3把SKIPIF1<0个有标号的珠子排成一个圆圈，共有多少种不同的排法？解这是典型的圆排列问题对于围成圆圈的SKIPIF1<0个元素，同时按同一方向旋转，即每个元素都向左（或向右）转动一个位置，虽然元素的绝对位置发生了变化．但相对位置未变，即元素之间的相邻关系未变，这样的圆排列认为是同一种，否则便是不同的圆排列．下面从两种角度推导圆排列数的计算公式．方法一：先令SKIPIF1<0个相异元素任意排成一行（称为线排列），共有种SKIPIF1<0排法，再将其首位相接围成一个圆，当圆转动一个角度时，对应另一个线排列，当每个元素又转回到原先的位置时，相当于SKIPIF1<0个不同的线排列，故圆排列数为SKIPIF1<0.方法二：先取出某一元素SKIPIF1<0，放于圆上某确定位置，再另余下的SKIPIF1<0个元素作为一个线排列，首尾置于SKIPIF1<0的两侧构成一个圆排列同样可得到SKIPIF1<0.4.探究高中数学竞赛中的组合问题4.1掌握四个基本的计数原理4.1.1加法原理设SKIPIF1<0集合划分为部分SKIPIF1<0．则SKIPIF1<0的元素个数可以通过找出它的每一个部分的元素的个数来确定，我们把这些数相加，得到SKIPIF1<0如果集合SKIPIF1<0可以重叠，我们能够使用一个跟深刻的原理来计数SKIPIF1<0中元素的个数—容斥原理．4.1.2乘法原理令SKIPIF1<0是元素的序偶SKIPIF1<0的集合，其中第一个元素SKIPIF1<0来自大小为SKIPIF1<0的一个集合，而对于SKIPIF1<0的每个选择，元素SKIPIF1<0存在着SKIPIF1<0种选择．于是，SKIPIF1<0的大小为SKIPIF1<0:SKIPIF1<0.4.1.3减法原理令SKIPIF1<0是一个集合，而是包含SKIPIF1<0的更大的集合．设SKIPIF1<0是SKIPIF1<0在SKIPIF1<0中的补,那么SKIPIF1<0中的元素个数SKIPIF1<0有下列法则给出：SKIPIF1<0.4.1.3除法原理令SKIPIF1<0是一个有限集，它以下述方式被划分成SKIPIF1<0部分，每一部分SKIPIF1<0包含相同数目的元素．此时，划分中的部分的数目由下述公式给出．SKIPIF1<0于是，如果我们知道元素个数以及各部分所含元素的个数相同，则可以确定部分的数目．4.2学习组合数学的几点建议1提倡一题多解,使学生善于从不同角度思考问题,做到思维起点灵活．思维起点灵活,就是能从不同角度、方向、方面思考问题,从同一信息源产生多种多样的联想,形成多个起点,用多种方法解决问题．一题多解正好适应这一要求,因此,加强一题多解的训练是达到这一目的的有效方法．2剖析解题过程,使学生善于克服思维定势,做到思维过程灵活．思维过程灵活,就是要善于从分析到综合,从综合到分析,能根据客观情况的变化而变化,随机应变地调整解题策略．在学习中,若知识和经验按着一定的“现成途经”反复认识,就容易使思维产生一种先入之见或固定模式,在解题时,只知道按熟悉的规律、方式、方法来思考,形成思维定势．此时若碰到形式类同,但本质不同的问题,往往感到束手无策,思维显得比较呆板．竞赛中的组合问题,往往没有一个固定的解题模式,许多题形式上十分相似,而解题过程却大不相同,需要根据具体情况,采取不同的对策．这些题目正是训练学生克服呆板性,增强灵活性的极好材料．3鼓励大胆联想,使学生善于引申、推广,做到接受和运用知识灵活．接受和运用知识灵活,就是要提倡发展学生的发散思维,使学生在面对一个问题时,能产生各种各样的联想,从而得到各种合理的结论,或者把许多有关问题联系起来．4强调新旧知识的联系,使学生善于形成新的认知结构,做到概括灵活．概括是一种思维过程,它包括两种意义:其一,指