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

《组合数学在数学竞赛中的应用---毕业》由会员分享，可在线阅读，更多相关《组合数学在数学竞赛中的应用---毕业（13页珍藏版）》请在装配图网上搜索。

1、_目 录12_组合数学在数学竞赛中的应用 Combinatorial Mathematics in Applied Mathematics (0521110329 Class 2 Grade 2005 Mathematics & Applied Mathematics School of Mathematics & Information) Abstract: Mathematical competitions in high school and junior high school are very popular in which the portfolio problem accoun

2、ts for a large proportion. As for this issue, the writer combines with the portfolio mathematics and competitive mathematics in university, and adopts the drawer principle, exclusion principle and permutation and combination methods to make the research and discussion. Importantly, the writer carrie

3、s new research on the problems of combination in mathematical competition.Key words: order; combination; drawer principle; Exclusion principle1. 引言组合数学是可以追溯到公元前2200既古老而又年轻的数学分支, 它的源泉可以追溯到公元前2200年的大禹时期，中外历史上许多著名的数字游戏是它古典部分的主要内容. 公元1666年，德国著名数学家莱布尼茨为它请名为“组合学”(Combinatorics),并预言了这一数学分支的诞生. 随着科学技术的发展，组合

4、数学这门历史悠久的学科得到了迅速发展数学活动离不开解题，掌握数学的一个重要标志就是善于解题现在专门以中学生为对象的数学竞赛成为时代的时尚，本论文希望结合组合数学和数学竞赛有关理论知识，针对在数学竞赛中占很大比例的组合问题，利用大学组合数学理论给出解释，并结合初等数学向学生渗透和合理讲解在此过程中，提出自己直接的见解和总结2.组合数学与数学竞赛简介2.1 组合数学组合数学历史悠久，几千年前，我国的河图、洛书就已涉及一些简单有趣的组合问题组合问题在日常生活中也随处可见例如，在玩扑克牌游戏中计算“同花顺”的概率、一笔画和幻方等都是组合数学问题组合数学自20世纪60年代急速发展的部分原因在于计算机在我

5、们的生活中所发挥的重要影响，而且这种影响还在继续发挥由于远算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的近年来，由于计算机科学、编码理论、规划论、数字通讯、试验设计、社会科学、生物科学等学科的迅猛发展，大大促进了组合数学的研究，使这一古老的数学分支成为了一门充满活力的数学学科组合数学可以一般地描述为：组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科现代的组合数学几乎是与图论不可分割的图论是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法有关图论的第一篇文章是由著名瑞士学家欧拉写于1736年，他探讨的是著名的哥尼斯堡七桥问题，图论在智力

6、难题和游戏方面有着历史根源，而今天它为许多学科的研究提供了一种非常重要的语言和框架2.2 数学竞赛围绕着数学竞赛而开展的各种活动已经搭起了一个数学教育新分支的框架，其特点是以开发智力为根本目的、以问题解决为基本形式、以竞赛数学为主要内容最本质的是对中学生进行“竞赛数学”的教育，这种教育的性质是：较高层次的基础教育、开发智力的素质教育、生动活泼的业余教育、现代教学的普及教育竞赛数学是一中“中间数学”，介乎于中小学与大学数学之间；竞赛数学是一种“前沿数学”，追求内容的新颖性，不断推陈出新，时刻涌现出新问题新方法和新结果；竞赛数学是一种“艺术数学”，它把现代化的内容与趣味性的问题有机结合，把普遍性的

7、问题与独创性的技巧有机结合，展示出数学美的魅力；竞赛数学是一种“教育数学”，它称为教育数学中最接近研究数学的“先头部队”，利用自己所处的地位，大量地、方便地吸收着前沿成果初等化，也把古典问题高等化3. 组合数学的几种方法在数学竞赛中的应用3.1 抽屉原理抽屉原理又称鸽巢原理或重叠原理，是组合数学的两大基本原理之一，是一个极其初等而又应用较广的数学原理抽屉原理要解决的是存在性问题，即在具体的组合问题中，要解决某些特定问题求解的方案数，其前提就是要知道这些方案的存在性定理3.1.1（基本形式）将个物品放入个抽屉，则至少有一个抽屉中的物品数不少于两个证 反证之 将抽屉编号为：，设第个抽屉放有个物品，

8、则 但若定理结论不成立，即，亦有，从而有 矛盾定理3.1.2（推广形式）将个物品放入个抽屉，则下列事件至少有一个成立：即第个抽屉的物品数不少于个，证 反证不然，设第个抽屉的物品数小于（即该抽屉最多有个物品），则有 物品总数 与假设矛盾根据定理的结果，不难得出下述结论推论3.1.1将个物品放入个抽屉，则至少有一个抽屉中的物品个数不少于 个推论3.1.2将个物品放入个抽屉，则至少有一个抽屉中的物品个数不少于个其中表示取正数的整数部分，表示不小于 的最小整数推论3.1.3若个正整数满足则至少有一个，满足利用抽屉原理可以得到下面两个性质：性质 1 任意三个整数中，必有两个整数的和是2的倍数性质 2 任

9、意五个整数中，必有三个整数的和是3的倍数例1 任意15个整数中，必有8个整数的和是8的倍数证 个整数是任意的，所以我们用这15个字母来表示，有性质1，中（a为整数），同理可得，中有（b为整数），中（c为整数），中（d为整数）。有性质1得（m为整数）（n为整数），中（e为整数）证毕例2 任意三个整数，必有两个之和为偶数（其差也为偶数）证 制造两个抽屉：“奇数”和“偶数”，3个数放入两个抽屉，必有一个抽屉中至少有两个数有整数求和的奇、偶性质，即知此二数之和比为偶数同理可知，二者之差也为偶数例 3 某俱乐部有名成员对每一个人，其余的人中恰好有个愿与他打网球，个愿与他下象棋，个愿与他打乒乓球证明该俱乐

10、部至少有3个人，他们之间玩的游戏三种俱全证 将每个人作为平面上的一个点，且任何三点不共线由每一点引出条红边、条蓝边、条黑边，分别代表打网球、下象棋及打乒乓球问题等价于要证明图中至少有一个三边颜色全部相同的三角形考虑有这个点的所有连边构成的异色角（即两条异色的边所构成的角）的总数每个顶点处有个异色角，所以平均每个三角形有个异色角因此，至少有一个三角形有3个异色角，那么，这个三角形的三条边当然互不同色证毕例4设为一等边三角形，是三边上点的全体对于每一个把分成两个不交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点证 如下图，在边上分别取三点P、Q、R，显然ARQ，BPR，

11、CQP都是直角三角形它们的锐角是30及60设E1，E2是E的两个非空子集，且由抽屉原则P、Q、R中至少有两点属于同一子集，不妨设P、QE1如果BC边上除P之外还有属于E1的点，那么结论已证明设BC的点除P之外全属于E2，那么只要AB上有异于B的点S属于E2，设S在BC上的投影点为S，则SSB为直角三角形再设AB内的每一点均不属于E2，即除B之外全属于E1，特别，R、AE1，于是A、Q、RE1，且AQR为一直角三角形， 从而命题得证【评述】此例通过分割图形构造抽屉在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个

12、或几个抽屉进行讨论，使问题得到解决例5：在中任选出20个数，其中至少有不同的两组数，和都等于104，试证明之（第39届美国普特南数学竞赛题）证 给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合且把它们分作是18个抽屉，从已知的34个数中任取20个数，即把前面两个抽屉中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104【评述】此例是根据某两个数的和为104来构造抽屉一般地，与整数集有关的存在性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成抽屉小

13、结： 用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律 用抽屉原则解题的基本思想是根据问题的自身特点和本质，找出分类的规律 用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉” 3.2 容斥原理 当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择将整体分解为部分也就是将有限集X表示成它的一组两两互异的非空真子集A1，A2，An的并集，即叫做集合X的一个

14、覆盖。一个特殊情况是，集族中的任意两个集合都不相交，这时我们称集族为集合X的一个（完全）划分如为集合X的划分，则对集合X的计数可通过熟知的加法公式 进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事我们可以考虑通过对任意的集族中的子集的计数来计算|X|，当集族中至少存在两个集合的交非空时，我们称这个覆盖为集合X的不完全划分对于集合X的不完全划分，显然有有 因为在计算|Ai|时出现了对某些元素的重复计数，为了计算|X|，就得将式右边重复计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的工作完成这项工作的准则就是容斥原理， 是十九世纪英国数学家西尔维斯提出的容

15、斥原理有两个公式1、容斥公式定理1 设 证明：当由加法公式有 结论成立若n=k时结论成立，则由 知，时结论成立由归纳原理知，对任意自然数n，公式成立公式称为容斥公式，显然它是公式的推广如果将看成具有性质的元素的集合，那么就是至少具有n个性质之一的元素的集合 因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目容斥原理用法总结：在应用容斥原理求解计数问题时，可按下列步骤进行：（1）根据问题的实际情况，构造一个有限集和一个性质集，是中具有性质的所有元素的子集，问题的关键是构造的性质集，要使得容易计算出来（2）当统计中恰好具有种特征的元素的个数时，将问题转化为求中恰好具有种个性质的元素个数，可

16、利用逐步淘汰原理或一般公式（3）当统计中至少有中一种性质的元素个数时，利用容斥原理，或由求得（4）注意，故可由此求得中至少具有种特征的元素个数如时，有2筛法公式与容斥公式讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性质的元素的个数，为此，我们先引入下面的引理引理1 设A关于全集I的补集为，则每个元素引理2 引理简单证略利用二引理改写公式便是定理2 设为有限集I的子集，则 3.错排问题利用容斥原理可以轻而易举地得出同一个公式个元素依次给以标号,个元素的全排列中，求每个元素都不在原来自己位置上的排列数设为数在第位上的全体排列，因数字不动,故同理每个元素都不在原来位置上的排列数为例1

17、数的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排列数目，实际上是五个数的错排问题，总数为 例2某校六年级二班有49人参加了数学、英语、语文学习小组，其中数学有30人参加，英语有20人参加，语文小组有10人老师告诉同学既参加数学小组又参加语文小组的有3人，既参加数学又参加英语和既参加英语又参加语文的人数均为质数，而三种全参加的只有1人，求既参加英语又参加数学小组的人数 分析与解：根据已知条件画出图 三圆盖住的总体为49人，假设既参加数学又参加英语的有x人，既参加语文又参加英语的有y人，可以列出这样的方程：整理后得： 由于x、y均为质数，因而这两个质数中必有一个偶质数2，另一个质数为7

18、例 3求1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和S解：1到100的自然数中，所有自然数的和是： 1到100的自然数中，所有2的倍数的自然数和是：1到100的自然数中，所有3的倍数的自然数和是：1到100的自然数中，所有既是2的倍数又是3的倍数，即是6的倍数的自然数和是：所以，1到100的自然数中，所有既不是2的倍数又不是3的倍数的整数之和3.3 排列组合定义一（排列Permutation）设元集，从中取出个不同元素按次序排列，称为的一个排列，其个数称为排列数，记作或当时的排列又称为的全排列，其个数又称全排列数命题1 证明 的一个排列由个不同的元素组成，其中第一位有种可能

19、第二位有种可能； 第位有种可能。由乘法原理,元集 的不同排列数为推论 例1 从 中任取两个不同的字母构成的字共有 个罗列如下：定义2 （组合Combination）设元集，从中取出个不同元素构成一组，称为的一个组合，其个数称为组合数，记作，或命题2 有个不同的元素共可构成种组合，即证明 由定义组合与排列的区别在于前者不计较元素的先后顺序，因此由每个组合可以作出个不同的排列于是若有种组合，则有种排列，因此推论 1 任意个相继的正整数之积可被整除形成多少条，即有推论 2 推论3 推论 4 元集的元子集的个数等于推论5 设元集，其字典序如下标所示，则从中每次取出满足条件的个元的方式数等于证明 的任一

20、组合都可调整为并使其满足；另一方面，任一满足条件的个元都是的一个组合例2 平面上任三点都不共线的25个点，可形成多少条直线？可形成多少个三角形？解 25点中任取2点即可惟一确定一条直线，故可形成条直线；同理，任取3点即可惟一确定一个三角形，故三角形的数目等于例 3 把个有标号的珠子排成一个圆圈，共有多少种不同的排法？解 这是典型的圆排列问题对于围成圆圈的个元素，同时按同一方向旋转，即每个元素都向左（或向右）转动一个位置，虽然元素的绝对位置发生了变化但相对位置未变，即元素之间的相邻关系未变，这样的圆排列认为是同一种，否则便是不同的圆排列下面从两种角度推导圆排列数的计算公式方法一：先令个相异元素任

21、意排成一行（称为线排列），共有种排法，再将其首位相接围成一个圆，当圆转动一个角度时，对应另一个线排列，当每个元素又转回到原先的位置时，相当于个不同的线排列，故圆排列数为.方法二：先取出某一元素，放于圆上某确定位置，再另余下的个元素作为一个线排列，首尾置于的两侧构成一个圆排列同样可得到.4. 探究高中数学竞赛中的组合问题4.1 掌握四个基本的计数原理4.1.1加法原理 设集合划分为部分则的元素个数可以通过找出它的每一个部分的元素的个数来确定，我们把这些数相加，得到如果集合可以重叠，我们能够使用一个跟深刻的原理来计数中元素的个数容斥原理4.1.2乘法原理 令是元素的序偶的集合，其中第一个元素来自大

22、小为的一个集合，而对于的每个选择，元素存在着种选择于是，的大小为: .4.1.3减法原理 令是一个集合，而是包含的更大的集合设是在中的补,那么中的元素个数有下列法则给出：.4.1.3除法原理 令是一个有限集，它以下述方式被划分成部分，每一部分包含相同数目的元素此时，划分中的部分的数目由下述公式给出于是，如果我们知道元素个数以及各部分所含元素的个数相同，则可以确定部分的数目4.2 学习组合数学的几点建议1提倡一题多解,使学生善于从不同角度思考问题,做到思维起点灵活思维起点灵活,就是能从不同角度、方向、方面思考问题,从同一信息源产生多种多样的联想,形成多个起点,用多种方法解决问题一题多解正好适应这

23、一要求,因此,加强一题多解的训练是达到这一目的的有效方法2剖析解题过程,使学生善于克服思维定势,做到思维过程灵活思维过程灵活,就是要善于从分析到综合,从综合到分析,能根据客观情况的变化而变化,随机应变地调整解题策略在学习中,若知识和经验按着一定的“现成途经”反复认识,就容易使思维产生一种先入之见或固定模式,在解题时,只知道按熟悉的规律、方式、方法来思考,形成思维定势此时若碰到形式类同,但本质不同的问题,往往感到束手无策,思维显得比较呆板竞赛中的组合问题,往往没有一个固定的解题模式,许多题形式上十分相似,而解题过程却大不相同,需要根据具体情况,采取不同的对策这些题目正是训练学生克服呆板性,增强灵

24、活性的极好材料3鼓励大胆联想,使学生善于引申、推广,做到接受和运用知识灵活接受和运用知识灵活,就是要提倡发展学生的发散思维,使学生在面对一个问题时,能产生各种各样的联想,从而得到各种合理的结论,或者把许多有关问题联系起来4强调新旧知识的联系,使学生善于形成新的认知结构,做到概括灵活概括是一种思维过程,它包括两种意义:其一,指在思想上把具有相同本质特性的事物联合起来;其二,是把被研究对象的本质特性推广为范围更广的包含这个对象的同类事物的本质特性因此,学习的过程也是概括过程学生学了新知识后,若思维灵活,则经过概括,可使新旧知识形成和谐整体,并重新组织和发展认知结构若思维呆板,不善于概括,就会使学过

25、的知识成为孤立、分散的东西,看不到它们的内在联系,抓不住本质属性5抓住本质特征,使学生善于触类旁通,做到迁移灵活学生在学习的过程中要重点培养发散思维，把抽象的问题具体化，掌握最基的原理，注重知识的迁移，这样在解题时才能得心应手4.3 培养学生的组合性思维和组合思想所谓组合性思维就是将一些基本思维,如比较思维、分析思维、综合思维、概括思维、有序思维、逆向思维、归纳思维、演绎思维、类比思维、发散思维、集中思维、想象思维等,让学生根据数学认知或练习材料的特点有机地将它们组合起来的思维;它对发展学生的思维能力及思维品质有重要的意义培养学生组合性思维可从下列两方面着手;一、在认知中培养，数学教材中有大量

26、的内容可用来培养学生的组合性思维二、从实践中取培养现在教材取与生活，让学生在实践中去发现数学规律，应用于实践当中，人人都学有价值的数学组合数学已经积累了大量漂亮的模型、原理、典型方法与技巧通过解决大量问题，人们形成组合思想：一种具有组合特征的数学思想，以及运用组合方法、技巧、原则去处理各种问题的思维方式与习惯，比如将连续的问题离散化，将离散的事物进行排列、组合、分类对比、并联构造等培养学生的组合性思维和组合思想,让学生在解题中得心应手4.4 常见排列组合的解题策略在解决排列组合综合性问题时，必须深刻理解排列与组合的概念，能够熟练确定一个问题是排列问题还是组合问题，牢记排列数、组合数计算公式与组

27、合数性质容易产生的错误是重复与遗漏计数常见的解题策略有以下几种：(1)特殊元素优先安排的策略；(2)合理分类与准确分布的策略；(3)排列、组合混合问题先选后排的策略；(4)正难则反、等价转化的策略；(5)相邻问题捆绑处理的策略；例 1 数字组成无重复数字的七位数，求三个偶数必相邻的七位数的个数解 因为三个偶数2，4，6必然相邻，所以要得到一个符合条件的七位数可以分为以下三步：第一步将1、3、5、7排好有种排法；第二步将2，4，6“捆绑”在一起有种排法；第三步将第二步“捆绑”的整体插入到第一步所排的四个数字形成的五个空隙中去有种排法所以根据乘法原理共有种排法所以共有720个符合条件的数(6)不相邻问题插空处理的策略；(7)定序问题除法处理的策略；(8)分排问题直接处理的策略；(9)“小集团”排列问题中先整体后局部的策略；(10)构造模型的策略参考文献1姜建国、岳建国著，组合数学.西安：西安电子科技大学出版社，2003.2马光思著.组合数学. 西安：西安电子科技大学出版社，20023陈传理 张同君著.竞赛数学教程北京：高等教育出版社，1996. 4田秋成等编著.组合数学北京：电子工业出版社，20065 （美）RichardA.Brualdi著，冯舜玺 罗平 裴伟东译 组合数学。机械工业出版社，20056 方世昌 著 离散数学西安：西安电子科技大学出版社，1985致 谢