《组合数学在数学竞赛中的应用毕业论文.doc》由会员分享，可在线阅读，更多相关《组合数学在数学竞赛中的应用毕业论文.doc（13页珍藏版）》请在金锄头文库上搜索。
1、目 录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组合数学在数学竞赛中的应用 Combinatorial Mathematics in Applied Mathematics (0521110329 Class 2 Grade 2005 Mathematics & Applied Ma
2、thematics School of Mathematics & Information) Abstract: Mathematical competitions in high school and junior high school are very popular in which the portfolio problem accounts for a large proportion. As for this issue, the writer combines with the portfolio mathematics and competitive mathematics
3、in university, and adopts the drawer principle, exclusion principle and permutation and combination methods to make the research and discussion. Importantly, the writer carries new research on the problems of combination in mathematical competition.Key words: order; combination; drawer principle; Ex
4、clusion principle1. 引言组合数学是可以追溯到公元前2200既古老而又年轻的数学分支, 它的源泉可以追溯到公元前2200年的大禹时期，中外历史上许多著名的数字游戏是它古典部分的主要内容. 公元1666年，德国著名数学家莱布尼茨为它请名为“组合学”(Combinatorics),并预言了这一数学分支的诞生. 随着科学技术的发展，组合数学这门历史悠久的学科得到了迅速发展数学活动离不开解题，掌握数学的一个重要标志就是善于解题现在专门以中学生为对象的数学竞赛成为时代的时尚，本论文希望结合组合数学和数学竞赛有关理论知识，针对在数学竞赛中占很大比例的组合问题，利用大学组合数学理论给出解释
5、，并结合初等数学向学生渗透和合理讲解在此过程中，提出自己直接的见解和总结2.组合数学与数学竞赛简介2.1 组合数学组合数学历史悠久，几千年前，我国的河图、洛书就已涉及一些简单有趣的组合问题组合问题在日常生活中也随处可见例如，在玩扑克牌游戏中计算“同花顺”的概率、一笔画和幻方等都是组合数学问题组合数学自20世纪60年代急速发展的部分原因在于计算机在我们的生活中所发挥的重要影响，而且这种影响还在继续发挥由于远算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的近年来，由于计算机科学、编码理论、规划论、数字通讯、试验设计、社会科学、生物科学等学科的迅猛发展，大大促进了组合数学的研究，
6、使这一古老的数学分支成为了一门充满活力的数学学科组合数学可以一般地描述为：组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科现代的组合数学几乎是与图论不可分割的图论是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法有关图论的第一篇文章是由著名瑞士学家欧拉写于1736年，他探讨的是著名的哥尼斯堡七桥问题，图论在智力难题和游戏方面有着历史根源，而今天它为许多学科的研究提供了一种非常重要的语言和框架2.2 数学竞赛围绕着数学竞赛而开展的各种活动已经搭起了一个数学教育新分支的框架，其特点是以开发智力为根本目的、以问题解决为基本形式、以竞赛数学为主要内容最本质的是对中
7、学生进行“竞赛数学”的教育，这种教育的性质是：较高层次的基础教育、开发智力的素质教育、生动活泼的业余教育、现代教学的普及教育竞赛数学是一中“中间数学”，介乎于中小学与大学数学之间；竞赛数学是一种“前沿数学”，追求内容的新颖性，不断推陈出新，时刻涌现出新问题新方法和新结果；竞赛数学是一种“艺术数学”，它把现代化的内容与趣味性的问题有机结合，把普遍性的问题与独创性的技巧有机结合，展示出数学美的魅力；竞赛数学是一种“教育数学”，它称为教育数学中最接近研究数学的“先头部队”，利用自己所处的地位，大量地、方便地吸收着前沿成果初等化，也把古典问题高等化3. 组合数学的几种方法在数学竞赛中的应用3.1 抽屉
8、原理抽屉原理又称鸽巢原理或重叠原理，是组合数学的两大基本原理之一，是一个极其初等而又应用较广的数学原理抽屉原理要解决的是存在性问题，即在具体的组合问题中，要解决某些特定问题求解的方案数，其前提就是要知道这些方案的存在性定理3.1.1（基本形式）将个物品放入个抽屉，则至少有一个抽屉中的物品数不少于两个证 反证之 将抽屉编号为：，设第个抽屉放有个物品，则 但若定理结论不成立，即，亦有，从而有 矛盾定理3.1.2（推广形式）将个物品放入个抽屉，则下列事件至少有一个成立：即第个抽屉的物品数不少于个，证 反证不然，设第个抽屉的物品数小于（即该抽屉最多有个物品），则有 物品总数 与假设矛盾根据定理的结果，
9、不难得出下述结论推论3.1.1将个物品放入个抽屉，则至少有一个抽屉中的物品个数不少于 个推论3.1.2将个物品放入个抽屉，则至少有一个抽屉中的物品个数不少于个其中表示取正数的整数部分，表示不小于 的最小整数推论3.1.3若个正整数满足则至少有一个，满足利用抽屉原理可以得到下面两个性质：性质 1 任意三个整数中，必有两个整数的和是2的倍数性质 2 任意五个整数中，必有三个整数的和是3的倍数例1 任意15个整数中，必有8个整数的和是8的倍数证 个整数是任意的，所以我们用这15个字母来表示，有性质1，中（a为整数），同理可得，中有（b为整数），中（c为整数），中（d为整数）。有性质1得（m为整数）（
10、n为整数），中（e为整数）证毕例2 任意三个整数，必有两个之和为偶数（其差也为偶数）证 制造两个抽屉：“奇数”和“偶数”，3个数放入两个抽屉，必有一个抽屉中至少有两个数有整数求和的奇、偶性质，即知此二数之和比为偶数同理可知，二者之差也为偶数例 3 某俱乐部有名成员对每一个人，其余的人中恰好有个愿与他打网球，个愿与他下象棋，个愿与他打乒乓球证明该俱乐部至少有3个人，他们之间玩的游戏三种俱全证 将每个人作为平面上的一个点，且任何三点不共线由每一点引出条红边、条蓝边、条黑边，分别代表打网球、下象棋及打乒乓球问题等价于要证明图中至少有一个三边颜色全部相同的三角形考虑有这个点的所有连边构成的异色角（即两
11、条异色的边所构成的角）的总数每个顶点处有个异色角，所以平均每个三角形有个异色角因此，至少有一个三角形有3个异色角，那么，这个三角形的三条边当然互不同色证毕例4设为一等边三角形，是三边上点的全体对于每一个把分成两个不交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点证 如下图，在边上分别取三点P、Q、R，显然ARQ，BPR，CQP都是直角三角形它们的锐角是30及60设E1，E2是E的两个非空子集，且由抽屉原则P、Q、R中至少有两点属于同一子集，不妨设P、QE1如果BC边上除P之外还有属于E1的点，那么结论已证明设BC的点除P之外全属于E2，那么只要AB上有异于B的点S属
12、于E2，设S在BC上的投影点为S，则SSB为直角三角形再设AB内的每一点均不属于E2，即除B之外全属于E1，特别，R、AE1，于是A、Q、RE1，且AQR为一直角三角形， 从而命题得证【评述】此例通过分割图形构造抽屉在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决例5：在中任选出20个数，其中至少有不同的两组数，和都等于104，试证明之（第39届美国普特南数学竞赛题）证 给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合且把它们分作是18个抽屉，
13、从已知的34个数中任取20个数，即把前面两个抽屉中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104【评述】此例是根据某两个数的和为104来构造抽屉一般地，与整数集有关的存在性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成抽屉小结： 用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律 用抽屉原则解题的基本思想是根据问题的
14、自身特点和本质，找出分类的规律 用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉” 3.2 容斥原理 当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择将整体分解为部分也就是将有限集X表示成它的一组两两互异的非空真子集A1，A2，An的并集，即叫做集合X的一个覆盖。一个特殊情况是，集族中的任意两个集合都不相交，这时我们称集族为集合X的一个（完全）划分如为集合X的划分，则对集合X的计数可通过熟知的加法公式 进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事我们可以考虑通过对任意的集族中的子集的计数来计算|X|，当集族中至少存在两个集合的交非空时，我们称这个覆盖为集合X的不完全划分对于集合X的不完全划分，显然有有 因为在计算|Ai|时出现了对某些元素的重复计数，为了计算|X|，就得将式右边重复计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的工作完成这项工作的准则就是容斥原理， 是十九世纪英国数学家西尔维斯提出的容斥原理有两个公式1、容斥公式定理1 设 证明：当由加法公式有 结论成立若n=k时结论成立，则由 知，时结论成立由归纳原理知，对任意自然数n，公式成立公式称为容斥公式，显然它是公式的推广如果将看成具有性质的元素的集合，那么就是至少
