




已阅读5页,还剩8页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
目 录 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 组合数学在数学竞赛中的应用 Combinatorial Mathematics in Applied Mathematics (0521110329 Class 2 Grade 2005 Mathematics combination; drawer principle; Exclusion principle 1. 引言 组合数学是可以追溯到公元前 2200 既古老而又年轻的数学分支, 它的源泉可以追 溯到公元前 2200 年的大禹时期,中外历史上许多著名的数字游戏是它古典部分的主要 内容. 公元 1666 年,德国著名数学家莱布尼茨为它请名为“组合学”(Combinatorics), 并预言了这一数学分支的诞生. 随着科学技术的发展,组合数学这门历史悠久的学科 得到了迅速发展 数学活动离不开解题,掌握数学的一个重要标志就是善于解题现在专门以中学 生为对象的数学竞赛成为时代的时尚,本论文希望结合组合数学和数学竞赛有关理论 知识,针对在数学竞赛中占很大比例的组合问题,利用大学组合数学理论给出解释, 并结合初等数学向学生渗透和合理讲解在此过程中,提出自己直接的见解和总结 2.组合数学与数学竞赛简介 2.1 组合数学 组合数学历史悠久,几千年前,我国的河图 、 洛书就已涉及一些简单有趣 的组合问题组合问题在日常生活中也随处可见例如,在玩扑克牌游戏中计算“同 花顺”的概率、一笔画和幻方等都是组合数学问题 组合数学自 20 世纪 60 年代急速发展的部分原因在于计算机在我们的生活中所发 挥的重要影响,而且这种影响还在继续发挥由于远算速度的持续增加,计算机已经 能够解决大型问题,这在以前是不可能做到的近年来,由于计算机科学、编码理论、 规划论、数字通讯、试验设计、社会科学、生物科学等学科的迅猛发展,大大促进了 组合数学的研究,使这一古老的数学分支成为了一门充满活力的数学学科 组合数学可以一般地描述为:组合数学是研究离散结构的存在、计数、分析和优 化等问题的一门学科 现代的组合数学几乎是与图论不可分割的图论是数学的一个分支,它以图为研 究对象,研究顶点和边组成的图形的数学理论和方法有关图论的第一篇文章是由著 名瑞士学家欧拉写于 1736 年,他探讨的是著名的哥尼斯堡七桥问题,图论在智力难题 和游戏方面有着历史根源,而今天它为许多学科的研究提供了一种非常重要的语言和 框架 2.2 数学竞赛 围绕着数学竞赛而开展的各种活动已经搭起了一个数学教育新分支的框架,其特 点是以开发智力为根本目的、以问题解决为基本形式、以竞赛数学为主要内容最本 质的是对中学生进行“竞赛数学”的教育,这种教育的性质是:较高层次的基础教育、 开发智力的素质教育、生动活泼的业余教育、现代教学的普及教育 竞赛数学是一中“中间数学” ,介乎于中小学与大学数学之间;竞赛数学是一种 “前沿数学” ,追求内容的新颖性,不断推陈出新,时刻涌现出新问题新方法和新结果; 竞赛数学是一种“艺术数学” ,它把现代化的内容与趣味性的问题有机结合,把普遍性 的问题与独创性的技巧有机结合,展示出数学美的魅力;竞赛数学是一种“教育数学” , 它称为教育数学中最接近研究数学的“先头部队” ,利用自己所处的地位,大量地、方 便地吸收着前沿成果初等化,也把古典问题高等化 3. 组合数学的几种方法在数学竞赛中的应用 3.1 抽屉原理 抽屉原理又称鸽巢原理或重叠原理,是组合数学的两大基本原理之一,是一个极 其初等而又应用较广的数学原理抽屉原理要解决的是存在性问题,即在具体的组合 问题中,要解决某些特定问题求解的方案数,其前提就是要知道这些方案的存在性 定理 3.1.1(基本形式)将1n个物品放入n个抽屉,则至少有一个抽屉中的物品数不 少于两个 证 反证之 将抽屉编号为:1,2,.n,设第i个抽屉放有 i q 个物品,则 12 .1 n qqqn 但若定理结论不成立,即1 i q ,亦有 12 . n qqqn,从而 有 12 1. n nqqqn 矛盾 定理 3.1.2(推广形式)将 12 .1 n qqqn个物品放入n个抽屉,则下列事件至少 有一个成立:即第i个抽屉的物品数不少于 i q 个,1,2,.in 证 反证不然,设第i个抽屉的物品数小于(1,2,. ) i q in(即该抽屉最多有1 i q 个物 品) ,则有 1 1 n i i qn 物品总数 11 1 nn ii ii qqn 与假设矛盾 根据定理的结果,不难得出下述结论 推论 3.1.1 将(1) 1n r 个物品放入n个抽屉,则至少有一个抽屉中的物品个数不少于 r 个 推论 3.1.2 将m个物品放入n个抽屉,则至少有一个抽屉中的物品个数不少于 1 1 mm nn 个其中 x 表示取正数x的整数部分, x 表示不小于 x的最小整 数 推论 3.1.3 若n个正整数(1,2,., ) i q in满足 12 .1 n qqqr 则至少有一个 i q ,满足 i qr 利用抽屉原理可以得到下面两个性质: 性质 1 任意三个整数中,必有两个整数的和是 2 的倍数 性质 2 任意五个整数中,必有三个整数的和是 3 的倍数 例 1 任意 15 个整数中,必有 8 个整数的和是 8 的倍数 证 15个整数是任意的,所以我们用 1231415 ,a a aaa 这 15 个字母来表示,有性质 1, 123 ,a a a 中 12 2aaa(a 为整数) ,同理可得, 456 ,a a a中有 45 2aab(b 为整数) , 789 ,a a a中 78 2aac(c 为整数) , 101112 ,aaa 中 1011 2aad(d 为整数) 。有性质 1 得 2abm(m 为整数)2cdn(n 为整数) , 13 , ,m n a 中2mne(e 为整数) 128 2()4()8aaaabcdmne 证毕 例 2 任意三个整数,必有两个之和为偶数(其差也为偶数) 证 制造两个抽屉:“奇数”和“偶数” ,3 个数放入两个抽屉,必有一个抽屉中至少 有两个数有整数求和的奇、偶性质,即知此二数之和比为偶数 同理可知,二者之差也为偶数 例 3 某俱乐部有31n名成员对每一个人,其余的人中恰好有n个愿与他打网球, n个愿与他下象棋,n个愿与他打乒乓球证明该俱乐部至少有 3 个人,他们之间玩的 游戏三种俱全 证 将每个人作为平面上的一个点,且任何三点不共线由每一点引出n条红边、n条 蓝边、n条黑边,分别代表打网球、下象棋及打乒乓球问题等价于要证明图中至少 有一个三边颜色全部相同的三角形 考虑有这个31n点的所有连边构成的异色角(即两条异色的边所构成的角)的总 数 每个顶点处有 2 3n 个异色角,所以 2 3(31)Lnn 平均每个三角形有 2 3 31 3(31)6 2 31 n nnn Cn 个异色角因此,至少有一个三角形有 3 个异色角,那么,这个三角形的三条边当然 互不同色 证毕 例 4 设ABC为一等边三角形,E是三边上点的全体对于每一个把E分成两个不 交子集的划分,问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶 点 证 如下图,在边BC CA AB上分别取三点 P、Q、R,显然 ARQ,BPR,CQP 都是直角三角形它们的锐角是 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 为一直角三角形, 从而命 题得证 【评述】此例通过分割图形构造抽屉在一个几何图形内有若干已知点,我们可以根 据问题的要求把图形进行适当的分割,用这些分割成的图形作为抽屉,再对已知点进 行分类,集中对某一个或几个抽屉进行讨论,使问题得到解决 例 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 来构造抽屉一般地,与整数集有关的存在 性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而 构成抽屉 小结: 用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围,使之在 一个特定的小范围内考虑问题,从而使问题变得简单明确 用抽屉原则解题的基本思想是根据问题的自身特点和本质,弄清对哪些元素 进行分类,找出分类的规律 用抽屉原则解题的基本思想是根据问题的自身特点和本质,找出分类的规 律 用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉” 3.2 容斥原理 当我们试图对某些对象的数目从整体上计数碰到困难时,考虑将整体分解为部分, 通过对每个部分的计数来实现对整体的计数是一种明智的选择将整体分解为部分也 就是将有限集 X 表示成它的一组两两互异的非空真子集 A1,A2,An的并集,即 ,. 2121nn AAAAAAX集合叫做集合X的一个覆盖。一个特殊情况是, 集族中的任意两个集合都不相交,这时我们称集族为集合X的一个(完全)划 分如为集合X的划分,则对集合X的计数可通过熟知的加法公式 | 321n AAAAX 进行,但是,要找到一个划分并且其中所有子集易于计数的有时并非易事我们可以 考虑通过对任意的集族中的子集的计数来计算|X|,当集族中至少存在两个集合的交 非空时,我们称这个覆盖为集合 X 的不完全划分对于集合 X 的不完全划分,显然有 有 | 21n AAAX 因为在计算|Ai|时出现了对某些元素的重复计数,为了计算|X|,就得将式右边重复 计算的部分减去,如果减得超出了,还得再加上,也就是说我们要做“多退少补”的 工作完成这项工作的准则就是容斥原理, 是十九世纪英国数学家西尔维斯提出 的容斥原理有两个公式 1、容斥公式 定理 1 设则为有限集,), 2 , 1(niAi n inji i n i n jiii n i AAAAA 11 1 1 1 |) 1(| 证明:当,/,/,1 221121 BAABAABAAn设时由加法公式有 | |)|(|)|(| | | |,| |,| 2121 21 21 2121 2211 AAAA BBABA BAA BAAAA ABAABA 结论成立 若n=k时结论成立,则由 k ikji k i iki k i k jii ii k i ki k i ki k i ki k i i k i AAAAAA AAAA AAAAA 111 1 1 1 1 1 1 1 1 1 1 1 1 1 |) 1(| | )(| |)( | kii ki k i k kjkik AAAAAAA 1 1 1 111 | )(|) 1(| )()( | 1 111 1 1 |) 1(| k ikji i k i k jii AAAA知, 1 kn时结论成立 由归纳原理知,对任意自然数n,公式成立 公式称为容斥公式,显然它是公式的推广 如果将 i A看成具有性质 i P 的元素的集合,那么 n AAAX 21 就是至少具有 n个性质 n PPP, 21 之一的元素 的集合 因此,容斥公式常用来计算至少具有某几个性质之一的元素的数目 容斥原理用法总结: 在应用容斥原理求解计数问题时,可按下列步骤进行: (1)根据问题的实际情况,构造一个有限集 12 ,. t Se ee和一个性质集 12 ,. n Pp pp, i A是S中具有性质P的所有元素的子集,问题的关键是构造的性质 集P,要使得 12 |.| k A AA容易计算出来(1,2,. )|kn (2)当统计S中恰好具有k种特征的元素的个数时,将问题转化为求S中恰好具有 P种k个性质的元素个数 (1,2,. )N k kn,可利用逐步淘汰原理或一般公式 (3)当统计S中至少有P中一种性质的元素个数1L时,利用容斥原理,或由 1 |0LSN求得 (4)注意|01 . SNNN n,故可由此求得S中至少具有k种特征的元素个数 L k如2k 时,有 2 |01LSNN 2筛法公式 与容斥公式讨论的计数问题相反,有时需要计算不具有某几个性质中的任何一个性质 的元素的个数, 为此,我们先引入下面的引理 引理 1 设 A 关于全集 I 的补集为 A,则 . |IAA每个元素 引理 2 , 11 i n i i n i AA , 11 i n i i n i AA 引理简单证略利用二引理改写公式便是 定理 2 设), 2 , 1(niAi为有限集 I 的子集,则| 111 i n i i n i i n i AIAA n inji i n i n jii AAAAI 11 1 |) 1(| 3.错排问题 利用容斥原理可以轻而易举地得出同一个公式n个元素依次给以标号1,2,n ,n个 元素的全排列中,求每个元素都不在原来自己位置上的排列数 设 i A为数i在第i位上的全体排列,1,2,in 因数字i不动,故 | (1)!,1,2, i Anin同理| (2)!, ,1,2, ij AAni jn ij每个元素都不在原 来位置上的排列数为 12 |!( ,1)(1)!( ,2)(2)!( , )1! 111 !(1) 1!2! n AAAnC nnC nnC n n n n 例 1 数1,2,3,9的全排列中,求偶数在原来位置上,其余都不在原来位置上的错排列 数目,实际上是1,3,5,7,9五个数的错排问题,总数为 5!(5,1)4!(5,2)3!(5,3)2!(5,4)1!(5,5) 1111 120()60205 144 2624120 CCCCC 例 2 某校六年级二班有 49 人参加了数学、英语、语文学习小组,其中数学有 30 人参 加,英语有 20 人参加,语文小组有 10 人老师告诉同学既参加数学小组又参加语文 小组的有 3 人,既参加数学又参加英语和既参加英语又参加语文的人数均为质数,而 三种全参加的只有 1 人,求既参加英语又参加数学小组的人数 分析与解:根据已知条件画出图 三圆盖住的总体为 49 人,假设既参加数学又参加英语的有 x 人,既参加语文又 参加英语的有 y 人,可以列出这样的方程: 整理后得: 由于 x、y 均为质数,因而这两个质数中必有一个偶质数 2,另一个质数为 7 例 3 求 1 到 100 的自然数中,所有既不是 2 的倍数又不是 3 的倍数的整数之和 S 解:1 到 100 的自然数中,所有自然数的和是: 1+2+3+100=5050 1 到 100 的自然数中,所有 2 的倍数的自然数和是: 2*1+2*2+.+2*50=2*(1+2+3+其二,是把被研究对象的本质特性推广为范围更广的包含这个对象的同类 事物的本质特性因此,学习的过程也是概括过程学生学了新知识后,若思维灵活,则 经过概括,可使新旧知识形成和谐整体,并重新组织和发展认知结构若思维呆板,不善 于概括,就会使学过的知识成为孤立、分散的东西,看不到它们的内在联系,抓不住本质 属性 5 抓住本质特征,使学生善于触类旁通,做到迁移灵活 学生在学习的过程中要重点培养发散思维,把抽象的问题具体化,掌握最基的原 理,注重知识的迁移,这样在解题时才能得心应手 4.3 培养学生的组合性思维和组合思想 所谓组合性思维就是将一些基本思维,如比较思维、分析思维、综合思维、概括思 维、有序思维、逆向思维、归纳思维、演绎思维、类比思维、发散思维、集中思维、 想象思维等,让学生根据数学认知或练习材料的特点有机地将它们组合起来的思维;它 对发展学生的思维能力及思维品质有重要的意义培养学生组合性思维可从下列两方 面着手;一、在认知中培养,数学教材中有大量的内容可用来培养学生的组合性思 维二、从实践中取培养现在教材取与生活,让学生在实践中去发现数学规律,应 用于实践当中,人人都学有价值的数学 组合数学已经积累了大量漂亮的模型、原理、典型方法与技巧通过解决大量问 题,人们形成组合思想:一种具有组合特征的数学思想,以及运用组合方法、技巧、 原则去处理各种问题的思维方式与习惯,比如将连续的问题离散
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年陕西省咸阳市彬州市中考二模历史试卷
- 财务业绩指标设定试题及答案
- 2025年考纲重点计算机试题及答案
- 公考法律面试题目及答案
- 高中计算机试题及答案
- 精益求精的2025年税法考试试题及答案
- 法律信仰面试题及答案
- 法律硕士民法试题及答案
- 法律考研试题及答案
- 法律监管面试题库及答案
- 趣味英语课件完整版
- 大学武术智慧树知到答案章节测试2023年浙江大学
- 前列腺增生症患者围手术期的护理
- 五防系统调试报告
- 日语综合教程第六册 单词表
- 市委政研室主任关于如何写稿子的讲话
- 在建项目雨季施工(防汛)安全隐患排查表
- 《广东省普通高中学生档案》模板
- YY/T 1064-2022牙科学牙科种植手术用钻头通用要求
- GB/T 40848-2021饲料原料压片玉米
- GB/T 12237-2021石油、石化及相关工业用的钢制球阀
评论
0/150
提交评论