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

《组合数学在数学竞赛中的应用 毕业论文》由会员分享，可在线阅读，更多相关《组合数学在数学竞赛中的应用 毕业论文（13页珍藏版）》请在金锄头文库上搜索。

1、目 录 1.1.引言引言 1 1 2 2 组合数学与数学竞赛简介组合数学与数学竞赛简介. .1 1 2.1 组合数学.1 2.2 数学竞赛.1 3 3 组合数学的几种方法在数学竞赛中的应用组合数学的几种方法在数学竞赛中的应用 2 2 3.1 抽屉原理.2 3.2 容斥原理.2 3.3 排列组合.8 4.4.探索高中数学竞赛中的组合问题探索高中数学竞赛中的组合问题 1010 4.1 熟练掌握四个基本的技术原理10 4.2 学习组合数学的几点建议10 4.3 培养学生的组合性思维和组合思想11 4.4 常见排列组合的解题策略11 参考文献参考文献 1212 致致 谢谢 1212 组合数学在数学竞赛

2、中的应用 Combinatorial Mathematics in Applied Mathematics (0521110329 Class 2 Grade 2005 Mathematics combination; drawer principle; Exclusion principle 1. 引言 组合数学是可以追溯到公元前 2200 既古老而又年轻的数学分支, 它的源泉可以追 溯到公元前 2200 年的大禹时期，中外历史上许多著名的数字游戏是它古典部分的主要 内容. 公元 1666 年，德国著名数学家莱布尼茨为它请名为“组合学”(Combinatorics), 并预言了这一数学分支的

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

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

5、章是由著 名瑞士学家欧拉写于 1736 年，他探讨的是著名的哥尼斯堡七桥问题，图论在智力难题 和游戏方面有着历史根源，而今天它为许多学科的研究提供了一种非常重要的语言和 框架 2.2 数学竞赛 围绕着数学竞赛而开展的各种活动已经搭起了一个数学教育新分支的框架，其特 点是以开发智力为根本目的、以问题解决为基本形式、以竞赛数学为主要内容最本 质的是对中学生进行“竞赛数学”的教育，这种教育的性质是：较高层次的基础教育、 开发智力的素质教育、生动活泼的业余教育、现代教学的普及教育 竞赛数学是一中“中间数学” ，介乎于中小学与大学数学之间；竞赛数学是一种 “前沿数学” ，追求内容的新颖性，不断推陈出新，

6、时刻涌现出新问题新方法和新结果； 竞赛数学是一种“艺术数学” ，它把现代化的内容与趣味性的问题有机结合，把普遍性 的问题与独创性的技巧有机结合，展示出数学美的魅力；竞赛数学是一种“教育数学” ， 它称为教育数学中最接近研究数学的“先头部队” ，利用自己所处的地位，大量地、方 便地吸收着前沿成果初等化，也把古典问题高等化 3. 组合数学的几种方法在数学竞赛中的应用 3.1 抽屉原理 抽屉原理又称鸽巢原理或重叠原理，是组合数学的两大基本原理之一，是一个极 其初等而又应用较广的数学原理抽屉原理要解决的是存在性问题，即在具体的组合 问题中，要解决某些特定问题求解的方案数，其前提就是要知道这些方案的存在

7、性 定理 3.1.1（基本形式）将个物品放入个抽屉，则至少有一个抽屉中的物品数不1nn 少于两个 证 反证之 将抽屉编号为：，设第 个抽屉放有个物品，则 1,2,.ni i q 但若定理结论不成立，即，亦有，从而 12 .1 n qqqn1 i q 12 . n qqqn 有 矛盾 12 1. n nqqqn 定理 3.1.2（推广形式）将个物品放入个抽屉，则下列事件至少 12 .1 n qqqnn 有一个成立：即第 个抽屉的物品数不少于个，i i q1,2,.in 证 反证不然，设第 个抽屉的物品数小于（即该抽屉最多有个物i(1,2,. ) i q in1 i q 品） ，则有 物品总数 与

8、假设矛盾 1 1 n i i qn 11 1 nn ii ii qqn 根据定理的结果，不难得出下述结论 推论 3.1.1 将个物品放入个抽屉，则至少有一个抽屉中的物品个数不少于 (1) 1n r n 个r 推论 3.1.2 将个物品放入个抽屉，则至少有一个抽屉中的物品个数不少于mn 个其中表示取正数的整数部分，表示不小于 的最小整 1 1 mm nn x xx x 数 推论 3.1.3 若个正整数满足n(1,2,., ) i q in 12 .1 n qqqr 则至少有一个，满足 i q i qr 利用抽屉原理可以得到下面两个性质： 性质 1 任意三个整数中，必有两个整数的和是 2 的倍数

9、性质 2 任意五个整数中，必有三个整数的和是 3 的倍数 例 1 任意 15 个整数中，必有 8 个整数的和是 8 的倍数 证 个整数是任意的，所以我们用这 15 个字母来表示，有性质 1，15 1231415 ,a a aaa 中（a 为整数） ，同理可得，中有（b 为整数） ， 123 ,a a a 12 2aaa 456 ,a a a 45 2aab 中（c 为整数） ，中（d 为整数） 。有性质 1 得 789 ,a a a 78 2aac 101112 ,aaa 1011 2aad （m 为整数）（n 为整数） ，中（e 为整数）2abm2cdn 13 , ,m n a2mne 12

10、8 2()4()8aaaabcdmne 证毕 例 2 任意三个整数，必有两个之和为偶数（其差也为偶数） 证 制造两个抽屉：“奇数”和“偶数” ，3 个数放入两个抽屉，必有一个抽屉中至少 有两个数有整数求和的奇、偶性质，即知此二数之和比为偶数 同理可知，二者之差也为偶数 例 3 某俱乐部有名成员对每一个人，其余的人中恰好有个愿与他打网球，31nn 个愿与他下象棋，个愿与他打乒乓球证明该俱乐部至少有 3 个人，他们之间玩的nn 游戏三种俱全 证 将每个人作为平面上的一个点，且任何三点不共线由每一点引出条红边、条nn 蓝边、条黑边，分别代表打网球、下象棋及打乒乓球问题等价于要证明图中至少n 有一个三

11、边颜色全部相同的三角形 考虑有这个点的所有连边构成的异色角（即两条异色的边所构成的角）的总31n 数 每个顶点处有个异色角，所以 2 3n 2 3(31)Lnn 平均每个三角形有 2 3 31 3(31)6 2 31 n nnn Cn 个异色角因此，至少有一个三角形有 3 个异色角，那么，这个三角形的三条边当然 互不同色 证毕 例 4 设为一等边三角形，是三边上点的全体对于每一个把分成两个不ABCEE 交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶 点 证 如下图，在边上分别取三点BC CA AB P、Q、R，显然 ARQ，BPR，CQP 都是直角三角形它们的锐角是

12、 30及 60 设 E1，E2是 E 的两个非空子集，且 1212 ,EEE EE 由抽屉原则 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 为一直角三角形， 从而命 题得证 【评述】此例通过分割图形构造抽屉在一个几何图形内有若干已知点，我们可以根 据问

13、题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进 行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决 例 5：在中任选出 20 个数，其中至少有不同的两组数，和都等于1,4,7,10,13,100 104，试证明之 （第 39 届美国普特南数学竞赛题） 证 给定的数共有 34 个，其相邻两数的差均为 3，我们把这些数分成如下 18 个不相交 的集合 1,52,4,100,7,97,49,55 且把它们分作是 18 个抽屉，从已知的 34 个数中任取 20 个数，即把前面两个抽屉中的 数 1 和 52 都取出，则剩下的 18 个数在后面的 16 个抽屉中至少有不同的两个

14、抽屉中的 数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是 104 【评述】此例是根据某两个数的和为 104 来构造抽屉一般地，与整数集有关的存在 性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而 构成抽屉 小结： 用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在 一个特定的小范围内考虑问题，从而使问题变得简单明确 用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素 进行分类，找出分类的规律 用抽屉原则解题的基本思想是根据问题的自身特点和本质，找出分类的规 律 用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”

15、3.2 容斥原理 当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分， 通过对每个部分的计数来实现对整体的计数是一种明智的选择将整体分解为部分也 就是将有限集 X 表示成它的一组两两互异的非空真子集 A1，A2，An的并集，即 叫做集合X的一个覆盖。一个特殊情况是，,. 2121nn AAAAAAX集合 集族中的任意两个集合都不相交，这时我们称集族为集合X的一个（完全）划 分如为集合X的划分，则对集合X的计数可通过熟知的加法公式 | 321n AAAAX 进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事我们可以 考虑通过对任意的集族中的子集的计数来计算|X|，当集族中至少存在两个集合的交 非空时，我们称这个覆盖为集合 X 的不完全划分对于集合 X 的不完全划分，显然有 有 | 21n AAAX 因为在计算|Ai|时出现了对某些元素的重复计数，为了计算|X|，就得将式右边重复 计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的 工作完成这项工作的准则就是容斥原理， 是十九世纪英国数学家西尔维斯提出 的容斥原理有两个公式 1、容斥公式 定