当前位置:首页 >> 学科竞赛 >>

柳铁一中组合高中数学竞赛同步讲义


高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

高中数学竞赛同步讲义——组合数学基础 一、基础知识梳理 1、集合覆盖、分类、拆分 2、分类原理 3、容斥原理 4、加法原理 5、极端原理 6、抽屉原理 7、平均量重叠原则 8、面积的重叠原理 一、基础题型例析 1、抽屉原理 在数学问题中有一类与“存在性”有关的问题,例如: (1)13 个人中

至少有两个人出生在相同月份; (2)某校 400 名学生中,一定存在两名学生,他们在同一天过生日; (3)2003 个人任意分成 200 个小组,一定存在一组,其成员数不少于 11; (4)把[0,1]内的全部有理数放到 100 个集合中,一定存在一个集合,它里面有无限多 个有理数. 这类存在性问题中, “存在”的含义是“至少有一个” 。在解决这类问题时,只 要求指明存在,一般并不需要指出哪一个, 也不需要确定通过什么方式把这个存在的东西 找出来。这类问题相对来说涉及到的运算较少,依据的理论也不复杂,我们把这些理论称 之为“抽屉原理” 抽屉原理”最先是由 19 世纪的德国数学家迪里赫莱(Dirichlet)运用 于解决数学问题的,所以又称“迪里赫莱原理” ,也称“鸽巢原理” (一) 抽屉原理的基本形式 定理 1、如果把 n+1 个元素分成 n 个集合,那么不管怎么分,都存在一个集合,其中至少 有两个元素。 例 1. (1978 年广东省数学竞赛题)已知在边长为 1 的等边三角形内(包括边界)有任 意五个点(图 1) 。证明:至少有两个点之间的距离不大于 1/2.

例 2 (第 14 届 1M0 试题)一个集合含有 10 个互不相同的两位数,试证明:这两个集 合必有两个无公共元素的子集合,此两子集的各元素之和相等.

1

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

例 3.从 1-100 的自然数中,任意取出 51 个数,证明其中一定有两个数,它们中的一个 是另一个的整数倍。

例 4.从前 25 个自然数中任意取出 7 个数,证明:取出的数中一定有两个数,这两个数 中大数不超过小数的 1.5 倍。

例 4 说明: (2)如果我们按照(1)中的递推方法依次造“抽屉” ,则第 7 个抽屉为 {26, 27,28,29,30,31,32,33,34,35,36,37,38,39};第 8 个抽屉为:{40,41,42,?, 60};第 9 个抽屉为:{61,62,63,?,90,91};?? 那么我们可以将例 3 改造为如下 一系列题目: (1)从前 16 个自然数中任取 6 个自然数; ?? (2)从前 39 个自然数中任取 8 个自然数; ?? (3)从前 60 个自然数中任取 9 个自然数; ?? (4)从前 91 个自然数中任取 10 个自然数;?? 上述第(4)个命题,就是前苏联基辅第 49 届数学竞赛试题。 例 5:在坐标平面上任取五个整点(该点的横纵坐标都取整数) ,证明:其中一定存在两 个整点,它们的连线中点仍是整点.

2

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

例 5 说明:我们可以把整点的概念推广:如果(x1,x2,?xn)是 n 维(元)有序数组,且 x1,x2,?xn 中的每一个数都是整数, 则称 (x1,x2,?xn) 是一个 n 维整点 (整点又称格点) 。 如果对所有的 n 维整点按每一个 xi 的奇偶性来分类,由于每一个位置上有奇、偶两种 可能性,因此共可分为 2×2×?×2=2n 个类。这是对 n 维整点的一种分类方法。当 n=3 时,23=8,此时可以构造命题: “任意给定空间中九个整点,求证它们之中必有两点存在, 使连接这两点的直线段的内部含有整点” 。这就是 1971 年的美国普特南数学竞赛题。 (二) 抽屉原理的其它形式: 定理 2、把 m 个元素分成 n 个集合(m>n) (1)当 n 能整除 m 时,至少有一个集合 含有 m/n 个元素; (2)当 n 不能整除 m 时, 则至少有一个集合含有至少[m/n]+1 个元素, ([m/n]表示不超过 的最大整数) 说明:定理 2 有时候也可叙述成:把 m×n+1 个元素放进 n 个集合,则必有一个集合中 至少放有 m+1 个元素。 例 6. (1963 年北京市数学竞赛题)在边长为 1 的正方形内任意放入九个点,求证:存 在三个点,以这三个点为顶点的三角形的面积不超过 1/8。

例 6.说明:以下两个题目可以看作是本例的平凡拓广: (1)在边长为 2 的正方形内,随意放置 9 个点,证明:必有 3 个点,以它们为顶点 的三角形的面积不超过 1/2。 (2)在边长为 1 的正方形内任意给出 13 个点。求证:必有 4 个点,以它们为顶点的 四边形的面积不超过 1/4。

3

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

例 7. (北京市高中一年级数学竞赛 1990 年复赛试题) 910 瓶红、蓝墨水,排成 130 行,每行 7 瓶。证明:不论怎样排列,红、蓝墨水瓶的颜色 次序必定出现下述两种情况之一种: 1.至少三行完全相同; 2.至少有两组(四行) ,每组的两行完全相同。

(三) 抽屉原理的无限形式 定理 3.如果把无穷多个元素分成 n 个集合,那么不管怎么分,都至少存在一个集合,其中 有无穷多个元素。 例 8.在坐标平面上给出无限多个矩形,它们的顶点的直角坐标都具有如下形式:(0,0), (0,m),(n,0),(n,m)。 其中 m,n 是正整数,并且 m>3,n<6,求证:在这些矩形 中一定存在无限多个矩形,其中任意两个矩形必有一个被包含在另一个之中。

(四)抽屉原理的多次应用 例 9.有苹果、梨、桔子若干个,任意分成 9 堆,求证一定可以找到两堆,其苹果数、 梨数、桔子数分别求和都是偶数。

4

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

例 10. (根据 1995 年全国高中数学联赛试题改编)将平面上每个点以红蓝两色之一着色, 证明:存在这样的两个相似三角形,它们的相似比为 2009,并且每一个三角形的三个顶 点同色。

例 10.说明: (1)这里连续用了两次抽屉原理(以染色作抽屉) 。也可以一开始就取位似比为 2009 的 9 个位似点组(Ai,Bi)i=1,2,3,?,9) ,对 4 个抽屉(红,红) , (红,蓝) , (蓝,红) , (蓝, 蓝)应用抽屉原理,得出必有 3 个位似点属于同一抽屉, (2)从题目的证明过程中可以看出,位似比 2009 可以改换成另外一个任意的正整数、正 实数。 (3)一般地可以证明,在这个二染色的平面上存在无数个内角为 30°,60°,90°的直 角三角形三顶点同色。 (4)进一步还可得到:对任何 a∈R+,可得到两个相似比为 a 的顶点同色的相似三角形。 对于多染色的情形,还可以得出多个相似三角形的结论:用红、黄、蓝三种颜色对平面上 的点染色,对任意的 a,b∈R+,必存在三个三角形,它们彼此相似,相似比为 1∶a∶b, 且每个三角形的三顶点同色。 (五) 抽屉原理的拓广形式 面积重叠定理:设平面上给定 r 个面积分别为 S1,S2,?Sr 的图形, S1+S2+?+Sr=m.将 这 r 个图形以任意方式移植到一个已知面积为 n 的平面图形 F 的内部,则至少有(m/n)个 图形在 F 中有公共点((x)表示不小于 x 的最小整数) 。 例 11、半径为 19 的圆 C 内有 650 个点,证明:存在内半径为 2,外半径为 3 的圆环,它 至少盖住其中的 10 个点

5

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

平均值重叠原理 1 (1)若 n 个实数 x1,x2,?xn 满足 x1+x2+?+xn≥A(或≤A) ,则至少有一个 xi≥A/n (或≤A/n) 。 (2)若 n 个实数 x1,x2,?xn 满足 x1+x2+?+xn=A,则至少有 xi、xj, 满足 xi≥ A/n≥ xj。 平均值重叠原理 2 (1)若 n 个正数 x1,x2,?xn,满足 x1x2?xn≥An(或≤An) ,则至少有一个 xi≥A(或 ≤A) 。 (2)若 n 个正数 x1,x2,?xn,满足 x1x2?xn=An,则至少有 xi、xj,满足 xi≥ A ≥ xj。

6

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

2、容斥原理 容斥原理的基本形式 定义:所谓容斥,是指我们计算某类物的数目时,要排斥那些不应包含在这个计数中 的数目, 但同时要包容那些被错误地排斥了的数目, 以此补偿。 这种原理称为容斥原理 (The Principle of Inclusion-exclusion) ,又称为包含排斥原理。 (1)加法原理 加法原理:设 M 为非空有限集,A1,A2 , ? ,An 是 M 的两两不交的子集,且 A1 ∪ A2 ∪ ? ∪ An=M,那么|M|=|A1|+|A2|+?+|An|. 注:i) |M|即 card(M),表示集合 M 中元素的个数,简称为集合 M 的阶。 ii) 加法原理是组合数学中的一个基本的计数原理, 在实际运用中可根据问题的不同 背景赋予有限集 M 的元素不同的含义。 (2)容斥原理的基本形式 定理 1:|A∪B|=|A|+|B|-|A∩B|. 例 1、 对 24 名科技人员进行掌握外语情况的调查,其统计资料如下:会英、日、德、法 语的人数分别为 13、5、10 和 9。其中同时会英语、日语的人数为 2;同时会英语和德语、 同时会英语和法语、同时会德语和法语两种语言的人数均为 4;会日语的人既不会法语也 不会德语。试求只会一种语言的人数各为多少?又同时会英、德、法语的人数为多少?

7

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

例 2、求 1,2,3,?,100 中不能被 2,3,5 整除的数的个数.

(3)容斥原理的一般形式 定理 3: 设 A1,A2,?,An 是任意有限集合,有

定理 4:

例3、 (匈牙利数学竞赛试题)由数字1、2和3组成 n 位数,要求 n 位数中1、2 和3的每一个至少出现一次,求所有这种 n 位数的个数.

例4、计算不超过120的合数和素数的个数。

例 5、将与 105 互质的所有正整数从小到大排列,求这个数列的第 1000 项.
思路分析: 先研究较简单情况: 在 (0, 105]中有多少个数与 105 互质; 而 105=3×5×7??

8

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

例 6、 如果记小于正整数 n 且与 n 互质的数的个数为φ (n), 则在数论上叫函数φ (n)为欧拉 函数.试求φ (n).

例 7、 (1960-1961 波兰数学竞赛试题)某人给 6 个不同的收信人写了 6 封信,并且准备了 6 个写有收信人地址的信封,有多少种投放信笺的方法,使每份信笺于信封上的收信人不 相符?

例 8、 (贝努力-欧拉错装信封问题)某人写了 n 封信及 n 个相应收信人地址的信封,现把 所有的信一一装进信封,求所有的信全都装错信封的装法总数.

例 9、已知集合 A、B、C 满足: (1)|A|+|B|+|C|=|A∪B∪C|, (2)|A|=|B|=100. 求|A∩B∩C|的最小值.

3、极端原理 例 1、 (鸡兔同笼问题)鸡兔同笼不知数,三十六头笼中露,看足却有一百整,不知多 少鸡和兔? 例 2、 (智力游戏)一张圆桌,两人轮流往上方大小相等的硬币,只许平放,不许重叠, 谁在桌上放下最后一枚硬币,谁就是最后的胜利者,你选择先下还是后下,为什么? 集合理论重要性的一个侧面是它的方法论意义. 我们知道, 有些数学问题所涉及的各个元 素的地位是不平衡的, 其中的某个极端元素往往具有优于其它元素的特殊性质, 能为解题 提供方便,而利用这种极端性的依据之一就是下面所要介绍的有关集合的一条简单性质.

9

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

最小数原理 1:设 M 是正整数集的一个有非空子集,则 M 中必有最小数. 最小数原理 2:设 M 是实数集的一个有限的非空子集,则 M 中必有最小数. 推论:设 M 是实数集的一个有限的非空子集,则 M 中必有最大数. 例 3、设 S 为整数的非空集,满足:①如果 x,y∈S,那么 x-y ∈S ;②如果 x∈S ,那么 kx ∈S,k ∈Z. 求证:在 S 中存在一个整数 d,使得 S 由 d 的所有倍数组成.

例 4、若干人聚会,其中某些人彼此认识.已知:若某两人在聚会者中有相同数目的熟 人,则他俩便没有共同的熟人,证明:若聚会者中有人至少有 20 个熟人,则必然也有人 恰好有 20 个熟人.

例 5、在平面上任给 2n 个点,其中任意三点不共线,并把其中 n 个点染成红色,n 个点染 成蓝色.求证:可以一红一蓝地把它们连成 n 条线段,使这些线段互不相交.

例 6、一次 10 名选手参加的循环赛中无平局,胜者得 1 分,负者得 O 分.证明:各选手 得分的平方和不超过 285 .

10

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

例7、某地区网球俱乐部有 20 名成员,举行 14 场单打比赛,每人至少上场一次.求证: 必有 6 场比赛,其 12 个参赛者各不相同.

例8、 (第24届莫斯科数学奥林匹克)在平面上有100个点,其中任何两点的距离都不超过 1,并且任何3点为顶点都构成钝角三角形。证明能够做出一个半径为1/2的圆,使得所有

例9、 (第25届莫斯科数学奥林匹克)在平面上给定25个点,其中任何3点都有两点间的距 离小于1,求证:其中必可选出13个点,使得它们都位于一个半径为1/2的圆内.

11

高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品!

例10,证明方程 x3 ? 2 y 3 ? 4 z 3 ? 0 没有正整数解 x, y , z.

4、集合的划分与覆盖 定义1:设所研究的对象的全体形成集合 M,A1,A2, ?An 是集合 M 的一组非空子集,且 A1∪A2 ∪ ? ∪ An=M ,则称 A1,A2, ?An 为集合的一个覆盖. 定义2:设所研究的对象的全体形成集合 M , A1,A2, ?An 是集合 M 的一组非空子集, 满足 A1∪A2 ∪ ? ∪ An=M , 且任意两子集的交集为空集, 那么这组子集叫做全集 M 的一个 n-划分. 定义3:设所研究的对象的全体形成集合 M , A1,A2, ?An 是集合 M 的一组非空子集, 满足 A1∪A2 ∪ ? ∪ An=M ,且任意两子集的交集为空集,那么这组子集叫做研究对 象全体的一个 n-分类,其中每一个子集叫做研究对象的的一个类. 例1、集合{1,2,?,3n}可以划分成 n 个互不相交的三元集合{x,y,z},其中 x+y=3z, 求满足条件的最小正整数 n.

12


相关文章:
柳铁一中组合高中数学竞赛同步讲义
柳铁一中组合高中数学竞赛同步讲义_学科竞赛_高中教育_教育专区。高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品! 高中数学竞赛同步讲义——组合数学基...
柳铁一中2012级高三“悟道”001
柳铁一中2012级高三“悟道”001_数学_高中教育_教育专区。英国物理学家麦克斯韦预言...“轨道康复者”的速度是地球同步卫星速度的 倍 C. 站在赤道上的人观察到“...
【高中资源】广西南宁三中、柳铁一中、玉林高中2016届高三上学期联考数学理试题 Word版含答案
南宁三中、柳铁一中、玉林高中 2015~2016 学年度上学期高三 联考 数学(理)试题 第Ⅰ卷一.选择题:本大题共 12 小题.每小题 5 分,在每个小题给出的四个...
广西南宁三中、柳铁一中、玉林高中2016届高三上学期联考数学【理】试题及答案
南宁三中、柳铁一中、玉林高中 2015~2016 学年度上学期高三联考 数学(理)试题 2015.9.24 第Ⅰ卷一.选择题:本大题共 12 小题.每小题 5 分,在每个小题给...
2015年高中各科试题_广西柳铁一中高二下学期第一次月考:数学(文)(解析版)
2015年高中各科试题_广西柳铁一中高二下学期第一次月考:数学(文)(解析版)_语文_高中教育_教育专区。柳铁一中 2014—2015 学年高二下学期第一次月考 数学(文)...
广西柳铁一中09-10学年高二数学上学期期考(理)【会员独享】
广西柳铁一中 09-10 学年高二上学期期考(数学理)命题人:宋程 审题人:桂芳 说明:本套试卷分第Ⅰ卷(选择题)和第Ⅱ卷(非选择题)两部分,所有答案写在答卷上,...
柳铁一中2012届高三第一次月考数学(文)试题及解析
高一数学重要知识点归纳1/2 相关文档推荐 2012届广西柳铁一中高三上... 8页...2 3 【解题说明】本试题考查了等可能事件的古典概率的求解,并结合组合数公 式...
广西南宁三中、柳铁一中、玉林高中2016届高三上学期联考数学理试题
南宁三中、柳铁一中、玉林高中 2015~2016 学年度上学期高三 联考 数学(理)试题命题人:李春阳 韦国亮 审题人:陈康 2015.9.24 第Ⅰ卷一.选择题:本大题共 12...
广西南宁三中、柳铁一中、玉林高中2016届高三上学期联考数学理试题 (1)
南宁三中、柳铁一中、玉林高中 2015~2016 学年度上学期高三联考 数学(理)试题命题人:李春阳 韦国亮 审题人:陈康 2015.9.24 第Ⅰ卷一.选择题:本大题共 12 ...
柳铁一中 高考模拟试卷理科综合8
柳铁一中 高考模拟试卷理科综合8_高三理化生_理化生_高中教育_教育专区。柳铁一中...(欧)和 T(特) ,由它们组合成的单位与电压单位 V(伏)等 效的是 A.J/A...
更多相关标签:
柳铁一中 | 柳铁一中周斌 | 柳铁一中官网 | 柳铁一中2016高考 | 柳铁一中初中部 | 柳铁一中吧 | 柳铁一中安磊 | 柳铁一中李江涛 |