tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

第二讲组合数学基础


高中数学竞赛同步讲义

第二讲 组合数学基础

自来也明发帖QQ:1772874116

高中数学竞赛同步讲义——2、组合数学基础 一、基础知识梳理

1、集合覆盖、分类、拆分
2、分类原理

3、容斥原理
4、加法原理 5、极端原理 6、抽屉原理 7、平均量

重叠原则 8、面积的重叠原理

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
在数学问题中有一类与“存在性”有关的问题,例如:

(1)13个人中至少有两个人出生在相同月份;
(2)某校400名学生中,一定存在两名学生,他们在同一 天过生日;

(3)2003个人任意分成200个小组,一定存在一组,其成 员数不少于11;
(4)把[0,1]内的全部有理数放到100个集合中,一定存 在一个集合,它里面有无限多个有理数.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
这类存在性问题中,“存在”的含义是“至少有一个”。

在解决这类问题时,只要求指明存在,一般并不需要指 出哪一个,也不需要确定通过什么方式把这个存在的东西找 出来。这类问题相对来说涉及到的运算较少,依据的理论也 不复杂,我们把这些理论称之为“抽屉原理”
“抽屉原理”最先是由19世纪的德国数学家迪里赫莱 (Dirichlet)运用于解决数学问题的,所以又称“迪里赫莱原 理”,也称“鸽巢原理”。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(一) 抽屉原理的基本形式

定理1、如果把n+1个元素分成n个集合,那么不管怎么 分,都存在一个集合,其中至少有两个元素。
证明:(用反证法)若不存在至少有两个元素的集合, 则每个集合至多1个元素,从而n个集合至多有n个元素,此与 共有n+1个元素矛盾,故命题成立。 在定理1的叙述中,可以把“元素”改为“物件”,把 “集合”改成“抽屉”,抽屉原理正是由此得名。 同样,可以把“元素”改成“鸽子”,把“分成n个集合” 改成“飞进n个鸽笼中”。“鸽笼原理”由此得名。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例1. (1978年广东省数学竞赛题)已知在边长为1的等 边三角形内(包括边界)有任意五个点(图1)。证明:至少 有两个点之间的距离不大于1/2. A 分析:5个点的分布是任意的。如果要 证明“在边长为1的等边三角形内(包括边 界)有5个点,那么这5个点中一定有距离 F E 不大于1/2的两点”,则顺次连接三角形三 边中点,即三角形的三条中位线,可以分 C 原等边三角形为4个全等的边长为1/2的小 B D 等边三角形,则5个点中必有2点位于同一 图1 个小等边三角形中(包括边界),其距离 便不大于1/2。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例1. (1978年广东省数学竞赛题)已知在边长为1的等 边三角形内(包括边界)有任意五个点(图1)。证明:至少 有两个点之间的距离不大于1/2. A 以上结论要由定理“三角形内(包括 边界)任意两点间的距离不大于其最大边 F E 长”来保证,下面我们就来证明这个定理。
B D 图1 C

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析 定理:三角形内(包括边界)任意两点间的距离不大 于其最大边长. A 证明:如图2,设BC是△ABC 的最大边,P,M是△ABC内(包 N 括边界)任意两点, M P 连接PM,过P分别作AB、BC Q 边的平行线,过M作AC边的平行 B C 线,设各平行线交点为P、Q、N, 图2 那么:∠PQN=∠C,∠QNP=∠A. 因为BC≥AB,所以∠A≥∠C,则∠QNP≥∠PQN,而 ∠QMP≥∠QNP≥∠PQN(三角形的外角大于不相邻的内 角),所以 PQ≥PM。显然BC≥PQ,故BC≥PM.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例1. (1978年广东省数学竞赛题)已知在边长为1的等 边三角形内(包括边界)有任意五个点(图1)。证明:至少 有两个点之间的距离不大于1/2.

说明: (1)这里是用等分三角形的方法来构造“抽屉”。类似地, 还可以利用等分线段、等分正方形的方法来构造“抽屉”。 例如:任取n+1个正数ai,满足0<ai≤1(i=1,2, …,n+1), 试证明:这n+1个数中必存在两个数,其差的绝对值小于1/n”。 又如:“在边长为1的正方形内任意放置五个点,求证:其 中必有两点,这两点之间的距离不大于 2 。
2

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例1. (1978年广东省数学竞赛题)已知在边长为1的等 边三角形内(包括边界)有任意五个点(图1)。证明:至少 有两个点之间的距离不大于1/2. 说明: (2)例1中,如果把条件(包括边界)去掉,则结论可以 修改为:至少有两个点之间的距离小于1/2",请读者试证之, 并比较证明的差别。 (3)用同样的方法可证明以下结论: i)在边长为1的等边三角形中有n2+1个点,这n2+1个点 中一定有距离不大于的两点1/n。 ii)在边长为1的等边三角形内有n2+1个点,这n2+1个点 中一定有距离小于1/n的两点。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例1. (1978年广东省数学竞赛题)已知在边长为1的等 边三角形内(包括边界)有任意五个点。证明:至少有两个 点之间的距离不大于1/2. 说明: (4)将(3)中两个命题中的等边三角形换成正方形,相
应的结论中的1/n换成
2 ,命题仍然成立。 n

(5)读者还可以考虑相反的问题:一般地,“至少需要多 少个点,才能够使得边长为1的正三角形内(包括边界)有两 点其距离不超过1/n”。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例2 (第14届1M0试题)一个集合含有10个互不相同的 两位数,试证明:这两个集合必有两个无公共元素的子集 合,此两子集的各元素之和相等.
解:10个元素的集合一共有1024个不同的子集,1022个非空 真子集。用N表示真子集中一切数字之和。则:N≤855 又1022>855,所以一定存在两个子集A与B,使得A中各 数之和=B中各数之和。 若A∩B=φ,则命题得证,若A∩B=C≠φ,即A与B有公共 元素,这时只要剔除A与B中的一切公有元素,得出两个不相 交的子集A1与B1,很显然A1中各元素之和=B1中各元素之和, 因此A1与B1就是符合题目要求的子集。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例2 (第14届1M0试题)一个集合含有10个互不相同的 两位数,试证明:这两个集合必有两个无公共元素的子集 合,此两子集的各元素之和相等.
说明:本例能否推广为如下命题: 已给一个由m个互不相等的n位十进制正整数组成的集合。 求证:这个集合必有两个无公共元素的子集合,各子集合中 各数之和相等。 请读者自己来研究这个问题。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例3.从1-100的自然数中,任意取出51个数,证明其 中一定有两个数,它们中的一个是另一个的整数倍。 略证:把1-100的正整数分成如下50个抽屉: (1){1,1×2,1×22,1×23,1×24,1×25,1×26}; (2){3,3×2,3×22,3×23,3×24,3×25}; (3){5,5×2,5×22,5×23,5×24}; …… (25){49,49×2}; (26){51}; …… (50){99}。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例4.从前25个自然数中任意取出7个数,证明:取出 的数中一定有两个数,这两个数中大数不超过小数的1.5倍。 证明:把前25个自然数分成下面6组: 1; ① 2,3; ② 4,5,6; ③ 7,8,9,10; ④ 11,12,13,14,15,16; ⑤ 17,18,19,20,21,22,23,24,25 ⑥ 因为从前25个自然数中任意取出7个数,所以至少有两个 数取自上面第②组到第⑥组中的某同一组,这两个数中大数 就不超过小数的1.5倍。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例4.从前25个自然数中任意取出7个数,证明:取出 的数中一定有两个数,这两个数中大数不超过小数的1.5倍。 说明:(1)本题可以改变叙述如下:在前25个自然数中 任意取出7个数,求证其中存在两个数,它们相互的比值在 [2/3,3/2]内。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析 1、抽屉原理 例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届数学竞赛试 题。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析 1、抽屉原理 例5:在坐标平面上任取五个整点(该点的横纵坐标都取 整数),证明:其中一定存在两个整点,它们的连线中点仍 是整点. 分析:坐标平面上的任意整点按照横纵两个坐标的奇偶 性考虑有且只有如下四种:(奇数、奇数),(偶数,偶 数),(奇数,偶数),(偶数,奇数)以此构造四个“抽 屉”,则在坐标平面上任取五个整点,那么至少有两个整点, 属于同一个“抽屉”因此它们连线的中点就必是整点。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析 1、抽屉原理 例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、组合数学基础 一、基础题型例析

1、抽屉原理
(2) 抽屉原理的其它形式 定理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个元素。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例6. (1963年北京市数学竞赛题)在边长为1的正方 形内任意放入九个点,求证:存在三个点,以这三个点为 顶点的三角形的面积不超过1/8。
解答:四等分正方形,得到四个矩形 (抽屉,面积为1/4)。 在正方形内任意放入九个点,则至少 有一个矩形内存在[9/4]+1=3个或3个以上 的点,设三点为A、B、C, 只需证明△ABC的面积不大于所在小矩 形面积的一半(1/8)

如何证明?

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例6.说明:把正方形分成四个区域,可以得出“至少 有一个区域内有3个点”的结论,这就为确定三角形面积的 取值范围打下了基础。本题构造“抽屉”的办法不是唯一的, 还可以将正方形等分成边长为1/2的四个小正方形等。但是 如将正方形等分成四个全等的小三角形却是不可行的(想一 想为什么?)。所以适当地构造“抽屉”,正是应用抽屉原 则解决问题的关键所在。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

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

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

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

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理 例7.证明:910瓶红、蓝墨水,排成130行,每行7瓶。 每行中的7个位置中的每个位置都有红、蓝两种可能,因而总 计共有27=128种不同的行式(当且仅当两行墨水瓶颜色及次 序完全相同时称为“行式”相同) 任取130行中的129行,依抽屉原理可知,必有两行(记 为A,B)“行式”相同。 在除A、B外的其余128行中若有一行P与A(B)“行式” 相同,则P,A,B满足“至少有三行完全相同”;在其余(除 A,B外)的128行中若没有与A(B)行式相同者,则128行至 多有127种不同的行式,依抽屉原则,必有两行(不妨记为C、 D)行式相同,这样便找到了(A,B)、(C,D)两组(四 行),每组两行完全相同。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(3) 抽屉原理的无限形式

定理3.如果把无穷多个元素分成n个集合,那么不管怎么 分,都至少存在一个集合,其中有无穷多个元素。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(3) 抽屉原理的无限形式 例8.在坐标平面上给出无限多个矩形,它们的顶点的 直角坐标都具有如下形式:(0,0),(0,m),(n,0),(n, m)。 其中m,n是正整数,并且m>3,n<6,求证:在这 些矩形中一定存在无限多个矩形,其中任意两个矩形必有一 个被包含在另一个之中。 证明:由n<6知,n=1,2,3,4,5,只有5种情形,由定理3知, 将所给的无穷多个矩形按n的取值分成5类,当作5个抽屉, 其中必有一个抽屉(一类)里包含有无穷多个矩形。不妨设 这一类矩形的n的取值为n。对于这一类矩形中的任意两个矩 形而言,由于n的取值相同,因此m取值较小的一个矩形必然 被包含在m取值较大的一个矩形之中。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(4) 抽屉原理的多次应用 例9.有苹果、梨、桔子若干个,任意分成9堆,求证一 定可以找到两堆,其苹果数、梨数、桔子数分别求和都是偶 数。 证明:因为每一堆里的每一种水果数或为奇数或为偶数 (两个抽屉),而9=2×4+1,故对于苹果,9堆中必有5堆的 奇偶性相同;这5堆对于梨数来说,由于5=2×2+1,故必有3 堆的奇偶性相同;这3堆对于桔子数也必有2堆的奇偶性相同。 于是,就找到这样的两堆,它们的苹果数、梨数,桔子数的 奇偶性都分别相同,从而其和数分别都是偶数。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(4) 抽屉原理的多次应用 例10.(根据1995年全国高中数学联赛试题改编)将平 面上每个点以红蓝两色之一着色,证明:存在这样的两个相 似三角形,它们的相似比为2009,并且每一个三角形的三个 顶点同色。 证明:作两个半径分别为1和2009的同心圆,在内圆上 任取9个点,必有5点同色,记为A1,A2,A3,A4,A5。连半 径0Ai交大圆于Bi(i=1,2,3,4,5),对B1,B2,B3,B4,B5, 必有3点同色,记为Bi,Bj,Bk,则△BiBjBk与△AiAjAk为三项 点同色的位似三角形,位似比等于2009,满足题设条件。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(4) 抽屉原理的多次应用 例10.说明: (1)这里连续用了两次抽屉原理(以染色作抽屉)。 也可以一开始就取位似比为2009的9个位似点组(Ai,Bi) i=1,2,3,…,9),对4个抽屉(红,红),(红,蓝),(蓝, 红),(蓝,蓝)应用抽屉原理,得出必有3个位似点属于 同一抽屉, (2)从题目的证明过程中可以看出,位似比2009可以 改换成另外一个任意的正整数、正实数。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(4) 抽屉原理的多次应用 例10.说明: (3)一般地可以证明,在这个二染色的平面上存在无 数个内角为30°,60°,90°的直角三角形三顶点同色。 (4)进一步还可得到:对任何a∈R+,可得到两个相 似比为a的顶点同色的相似三角形。对于多染色的情形,还 可以得出多个相似三角形的结论:用红、黄、蓝三种颜色 对平面上的点染色,对任意的a,b∈R+,必存在三个三角形, 它们彼此相似,相似比为1∶a∶b,且每个三角形的三顶点 同色。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(4) 抽屉原理的多次应用 例10.说明: (3)一般地可以证明,在这个二染色的平面上存在无 数个内角为30°,60°,90°的直角三角形三顶点同色。 (4)进一步还可得到:对任何a∈R+,可得到两个相 似比为a的顶点同色的相似三角形。对于多染色的情形,还 可以得出多个相似三角形的结论:用红、黄、蓝三种颜色 对平面上的点染色,对任意的a,b∈R+,必存在三个三角形, 它们彼此相似,相似比为1∶a∶b,且每个三角形的三顶点 同色。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(5) 抽屉原理的拓广形式 面积重叠定理:设平面上给定r个面积分别为S1,S2,…Sr 的图形, S1+S2+…+Sr=m.将这r个图形以任意方式移植到一个 已知面积为n的平面图形F的内部,则至少有(m/n)个图形在F 中有公共点((x)表示不小于x的最小整数)。 例11、半径为19的圆C内有650个点,证明:存在内半径 为2,外半径为3的圆环,它至少盖住其中的10个点 提示:半径为19的圆C面积为192π=361π ,每个内半径 为2,外半径为3的圆环的面积为5π。650个的面积总和为 3250π。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

1、抽屉原理
(5) 抽屉原理的拓广形式 平均值重叠原理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。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(1)加法原理

加法原理:设M为非空有限集,A1,A2 , … ,An是M的 两两不交的子集,且A1 ∪ A2 ∪ … ∪ An=M,那么 |M|=|A1|+|A2|+…+|An|. 注:i) |M|即card(M),表示集合M中元素的个数,简称为 集合M的阶。 ii) 加法原理是组合数学中的一个基本的计数原理,在实 际运用中可根据问题的不同背景赋予有限集M的元素不同的含 义。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(2)容斥原理的基本形式

定义:所谓容斥,是指我们计算某类物的数目时,要排 斥那些不应包含在这个计数中的数目,但同时要包容那些被 错误地排斥了的数目,以此补偿。这种原理称为容斥原理 (The Principle of Inclusion-exclusion),又称为包含排斥原 理。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(2)容斥原理的基本形式 ①

定理1:|A∪B|=|A|+|B|-|A∩B|. 证明:记A1=A-B,A2=B-A,A3=A∩B,则Ai∩Aj=Ф,且 |A∪B|=|A1∪A2∪A3|= |A1|+|A2|+|A3| =|A|-|A3|+|B|-|A3|+|A3| =|A|+|B|-|A∩B|. 定理2:设A,B是集合U的子集,则 |CUA∩CUB|=|U|-|A|-|B|+|A∩B|. 证明:其实|CUA∩CUB|=|CU(A∪B)| 注:摩根定律(1)CUA∩CUB=CU(A∪B); (2) CUA∪CUB=CU(A∩B)。



高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(2)容斥原理的基本形式

例1、 对24名科技人员进行掌握外语情况的调查,其统 计资料如下:会英、日、德、法语的人数分别为13、5、10和 9。其中同时会英语、日语的人数为2;同时会英语和德语、 同时会英语和法语、同时会德语和法语两种语言的人数均为4; 会日语的人既不会法语也不会德语。试求只会一种语言的人 数各为多少?又同时会英、德、法语的人数为多少?

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(2)容斥原理的基本形式

例1、解:设A、B、C、D分别为会英、日、德、法语的 人的集合,由已知条件可知: |A|=13,|B|=5,|C|=10,|D|=9 |A∩B|=2,|A∩C|=|A∩D|=|C∩D|=4,|B∩C|=|B∩D|=0 |A∩B∩C|=|A∩B∩D|=|B∩C∩D|=0 |A∩B∩C∩D|=0 |A∪B∪C∪D|=24 利用容斥原理,并代入已知条件得 24=13+5+10+9-2-4-4-4-0-0+0+0+0+|A∩C∩D|-0 解得,|A∩C∩D|=1,即同时会英、德、法语的只有1人。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(2)容斥原理的基本形式

例1、解: 设只会英、日、德、法语的人数分别为x1,x2,x3,x4,则 x1=|A|-|(B∪C∪D)∩A|=|A|-|(B∩A)∪(C∩A)∪(D∩A)| 对B∩A、C∩A、D∩A应用容斥原理,得 |(B∩A)∪(C∩A)∪(D∩A)|=2+4+4-0-0-1+0=9 故,x1=13-9=4。 类似地可求出:x2=3,x3=3,x4=2。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(2)容斥原理的基本形式

例2、求1,2,3,…,100中不能被2,3,5整除的数的 个数. 解:记U={1,2,3,…,100},A={x|x∈U且x是2的倍数}, B={x| x|x∈U且x是3的倍数},C ={x|x∈U且x是5的倍数},由 容斥原理, |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩ C|-|C∩ A|+|A∩ B∩ C| =[100/2]+[100/3]+[100/5]-[100/6]-[100/15][100/10]+[100/30]=74 所以,不能被2,3,5整除的数有100-74=26个。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理
n

(3)容斥原理的一般形式
? ? Ai ? ? Ai ? A j ?
i ?1 i? j n

定理3: 设A1,A2,…,An是任意有限集合,有

? ?A
i ?1

i

1? i ? j ? k ? n

?

Ai ? A j ? Ak

? ? ? ( ?1)

n ?1

n

?A
i ?1

i

.



定理4:设U为全集,A1,A2,…,An是任意有限集合,有

??A
i ?1

n

i

?U ?

??A
i ?1

n

i



注:定理4叫做逐步淘汰原理,又叫筛法公式。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(3)容斥原理的一般形式

例3、(匈牙利数学竞赛试题)由数字1、2和3组成n位数, 要求n位数中1、2和3的每一个至少出现一次,求所有这种n位 数的个数. 解:设所有由数字1、2和3组成的n位数集合为S,则 |S|=______. 3n 记S中不含 i 的 n 位数集合为 Ai ( i=1,2,3 ), 则 1 |Ai|=______.|Ai∩Aj|=_____,|A1∩A2∩A3|=_____. 0 2n 3n-3×2n+3 而且所求为|CSA1∩ CSA2∩ CSA3|=……=___________________.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理 (3)容斥原理的一般形式 例4、计算不超过120的合数和素数的个数。 思路分析:显然112=121>120,所以不超过120的合数必是 2,3,5,7的倍数. 解:记S1 = {a|1≤a≤120,2|a}, S2 = {b|1≤b≤120,3|b}, S3 = {c|1≤c≤120,5|c}, S4 = {d|1≤d≤120,7|d}, 60 24 则 |S1|=____,|S2|=_____,|S3|=____,|S4|=____. ……… 40 17 93 |S1∪S2∪S3∪S4|=_____.但其中2,3,5,7不是合数,故不超 89 过120的合数有_____个,而且1不是素数,所以不超过120的 32 素数有_____个。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(3)容斥原理的一般形式

例5、将与105互质的所有正整数从小到大排列,求这个 数列的第1000项. 思路分析:先研究较简单情况:在(0,105]中有多少个 数与105互质;而105=3×5×7…… 解:设S={1,2,3,…,105},A1={a|a∈S,且3|a}, A2= {a|a∈S且5|a}, A3={a|a∈S,且7|a}.则|A1|=___,|A2|=___,|A3|=___, 35 21 15 48 |CSA1∩CSA2∩CSA3|=_____. 设与105互质的正整数从小到大的顺序排列为a1,a2,a3, …, 则a1=1,a2=2,a3=4, …a48=104,a49=105+1,a50=105+2, … 2186 因为1000=48×20+40,所以a1000=105×20+a40=_______.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析 (3)容斥原理的一般形式 例6、如果记小于正整数n且与n互质的数的个数为φ(n), 则在数论上叫函数φ(n)为欧拉函数.试求φ(n). 解:设pi(i=1,2, …,m)是正整数n的全部质因数, 记S={1,2,…,n},设Ai={a|a∈S,pi|a},i=1,2, …,m 则φ(n)=|∩CSAi|,注意到|Ai|=[n/pi],|Ai∩Aj|=[n/pipj], …, |A1∩A2∩…∩Am|=[n/p1p2…pm],而pi为n的质因数,所以上式 中的 [ ] 都可去掉.由筛法公式得:
? ( n ) ? S ? ? C S Ai
i ?1 m

2、容斥原理

?n??
i ?1

m

1 pi

?

1? i ? j ? m

?

? 1 ? ? ? ? ( ? 1) ? n ? ? ?1 ? ? pi p j p1 p 2 ? pm pi ? i ?1 ?

1

m

1

m

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(3)容斥原理的一般形式

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

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理

(3)容斥原理的一般形式

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

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

2、容斥原理
例9、已知集合A、B、C满足: (1)|A|+|B|+|C|=|A∪B∪C|,(2)|A|=|B|=100. 求|A∩B∩C|的最小值. 解:根据条件知2100+2100+2|C|=2|A∪B∪C|,可得|C|=101, |A∪B∪C|=102。 (?) 根据容斥原理: |A∩B∩C|=|A∪B∪C|+|A|+|B|+|C|-|A ∪ B|-|A ∪ C|-|B ∪ C| 可知:|A∩B∩C|≥97 另外取A={1,2,3, …,100},B={3,4,5, …,102},C={1,2,4,5,6, …,100,102,102}时,|A∩B∩C|=97。 所以, |A∩B∩C|的最小值为97。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理
例1、(鸡兔同笼问题)鸡兔同笼不知数,三十六头笼中 露,看足却有一百整,不知多少鸡和兔?

例2、(智力游戏)一张圆桌,两人轮流往上方大小相等 的硬币,只许平放,不许重叠,谁在桌上放下最后一枚硬币, 谁就是最后的胜利者,你选择先下还是后下,为什么?

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理 集合理论的重要性的一个侧面是它的方法论意义.我们 知道,有些数学问题所涉及的各个元素的地位是不平衡的, 其中的某个极端元素往往具有优于其它元素的特殊性质,能 为解题提供方便,而利用这种极端性的依据之一就是下面所 要介绍的有关集合的一条简单性质.
最小数原理1:设M是正整数集的一个有非空子集,则M 中必有最小数. 最小数原理2:设M是实数集的一个有限的非空子集,则 M中必有最小数. 推论:设M是实数集的一个有限的非空子集,则M中必有 最大数.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理 例3、设S为整数的非空集,满足:①如果x,y∈S,那么 x-y ∈S ;②如果x∈S ,那么kx ∈S,k ∈Z. 求证:在S中存在 一个整数d,使得S由d的所有倍数组成. 证明:若S={0},则命题显然成立.
今设S不空,易证S中元素有正有负。设S’为S中 所有整数 组成的集合,从而S中有最小数,记为d,由②, nd∈S(n∈Z) . 另一方面,对任意h∈S,有h=kd+r(0≤r<d). 由 ①知r=hnd∈S.再由d是属于S的最小正整数,故只可能r=0. 所以S={nd|n∈Z},命题成立.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理 例4、若干人聚会,其中某些人彼此认识.已知:若某 两人在聚会者中有相同数目的熟人,则他俩便没有共同的熟 人,证明:若聚会者中有人至少有 20 个熟人,则必然也有 人恰好有 20 个熟人. 证明:考虑聚会中熟人最多的某个人(如这样的人不止 一个,则任取其中一个),记为A,设A共认识n个人,这些 人为B1, B2,…,Bn,显然n≥20. 由于B1, B2,…,Bn 中任两人 Bi 与Bj 都认识A, 由已知可知Bi 与Bj 的熟人数目不等.又B1, B2,…,Bn 的熟人数目均不超过n,且至少有1个熟人,于是 他们的熟人数目恰好为1,2,…,n. 由于n≥20 ,故数20在上 述数列中出现,于是 B1, B2,…,Bn中有人恰好有20个熟人.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理 例5、在平面上任给2n个点,其中任意三点不共线,并 把其中n个点染成红色,n个点染成蓝色.求证:可以一红一 蓝地把它们连成n条线段,使这些线段互不相交. 证明:因为总共只有2n个点,将红点与蓝点一一配对的 方法只有有限种(实际上为n!种).对于每一种配对方法, 都会得到这n条线段的长度和,这种和数只有有限个(其实不 超过n!个),由原理2知,其中必有一个是最小的,下面来证 明,这时候这n条线段是互不相交的. 用反证法.假定此时有两条线段 R1B1和 R2B2相交,其中 R1, R2是红点, B1 , B2是蓝点,设它们的交点为P(会发生什 么现象?以下略)。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理 例6、一次10名选手参加的循环赛中无平局,胜者得1 分, 负者得O分.证明:各选手得分的平方和不超过285 . 证明:由于得分的情况仅有有限多种,其中必有一种 的平方和取最大值.这时各选手的得分p1,p2,…,p10必互 不相同,因为若pi=pj则改变选手i与j之间的胜负,即用 pi-1,Pj+1来代替pi, pj时,由于 (pi-1)2+(pj+1)2-(pi2+pj2)=2>0, 而平方和中其它项不变,故平方和严格增大.这与平 方和已取得最大值矛盾.于是,在pi=i-1(i=1,2, …,10)时,各 选手平方和最大,这时的值为285 , 所以各选手得分的平方 和不超过 285 .

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

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

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理
例7证明:以无序对{ai,bi}表示参加第i场的比赛选手,并 记S={{ai,bi}|i=1,2,…,14}.设M为S的一个非空子集,且M 中所 含选手对中出现的所有选手互不相同.显然这样的子集存在 有限多个.设这种子集中元素个数最多的一个为M0,记 |M0|=r.显然,只需证明r≥6 . 假设r≤5 .由于M0是S的选手互异的集合中元素最多的集 合,故M0中未出现过的20-2r名选手之间互相没有比赛,否则 与M0的定义矛盾.这意味着这20-2r名选手所参加的比赛一定 是同M0中2r名选手进行的.由于已知每名选手至少参加一场 比赛,故除了 M0 中的r场比赛之外,至少还要进行 20 -2r 场 比赛,即总的比赛场数至少为 r+(20-2r)=20-r≥15 . 这与比赛总 场次为 14 矛盾.这就证明了 r≥6 .

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理
例8、(第24届莫斯科数学奥林匹克)在平面上有100个 点,其中任何两点的距离都不超过1,并且任何3点为顶点都 构成钝角三角形。证明能够做出一个半径为1/2的圆,使得所 有这些点都在这个圆内或圆周上. 证明:设在100个给定点中,彼此间距离最远的两点为A、 B,以线段AB为直径做圆S,则因对任何给定点C,△ABC为 钝角三角形,故点C在圆S内部,即所有给定点都在圆S内或 圆周上.若AB=1,则圆S即为所求;若AB<1,则圆S的以1/2为 半径的同心圆即为所求.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理
例9、(第25届莫斯科数学奥林匹克)在平面上给定25个 点,其中任何3点都有两点间的距离小于1,求证:其中必可 选出13个点,使得它们都位于一个半径为1/2的圆内. 证明:设在给定的25个点中,两点间距离最大的是A、B, 对任何异于A、B的给定点C,由已知,点C必与AB两点之一 的距离小于1,对于其余23个点利用抽屉原理知,AB两点中 必有一点(不妨记为A),与它距离小于1的点至少12个,于 是以A为圆心,1为半径的圆中至少有13个给定点.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

3、极端原理
例10、证明方程 x3+2y3-4z3=0 没有正整数解x,y,z. 证明:假设方程有正整数解,设x=x1,y=y1,z=z1 是方程的 所有正整数解中x最小的一组解.则 x13+2y13-4z13=0 , 所以 x1 是偶数,设 x1=2x2,则 (2x2)3+2y13-4z13=0, 即 4x23+2y134z13=0. 所以 y1是偶数,设 y1=2y2,则 4x23 + 8y23-2z13=0, 即 2x23+ 4y23-z13=0, 所以 z1 是偶数,设 z1=2z2,代人得 x23 + 2y23-4z23 = 0 . 所以 x=x2, y=y2, z=z2 也是原方程的一组正整数 解,且 x2=x1/2 <x1,矛盾. 故原方程没有正整数解.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

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-分类,其中每一个子集叫做研究对象的的一个类.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

4、集合的划分与覆盖
例1、集合{1,2,…,3n}可以划分成n个互不相交的三 元集合{x,y,z},其中x+y=3z,求满足条件的最小正整数n. 解、设三元组为{xi,yi,zi},其中xi+yi=3zi,i=1,2, …,n. 则 (x1+y1+z1)+(x2+y2+z2)+…+(xn+yn+zn)=4(z1+z2+…+zn) =3n(3n+1)/2 当2|n时,须8|n,得n的最小值为8; 当2不能整除n时,须8|(3n+1),得n的最小值为5.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

4、集合的划分与覆盖
例2、是集合{1,2,…,2004}的子集,S中的任意两个 数的差不等于4或7,问S中最多含有多少个元素?

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

4、集合的划分与覆盖 例12 设A={1,2,3,4,5,6},B={7,8,9,……,n}, 在A中取三个数,B中取两个数组成五个元素的集合,求的最 小值。

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

4、集合的划分与覆盖
例13.设,是的一个子集,且中任意三个不同元素都有,求 的最大值.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

4、集合的划分与覆盖
例14.一次会议有1990位数学家参加,每人至少有1327位合 作者,求证:可以找到4位数学家,他们中每两人都合作过.

高中数学竞赛同步讲义——2、组合数学基础 一、基础题型例析

4、集合的划分与覆盖 例15.设是整数集,其中.对于的非空子集,定义为的一切元素 的乘积.设表示的算术平均数.这里遍历的一切非空子集. 若=13,且有一正整数使得,试确定及的值.


推荐相关:

组合数学基础-答案及讲稿

第二讲组合数学基础 72页 1财富值 组合数学基础 26页 免费 组合数学基础9 14...“等和划分” . 解二:元素交换法,显然 ∑ ai = ∑ bi = 39 ,恒设12 ...


组合数学基础-问题与练习

26页 免费 第二讲组合数学基础 72页 1财富值喜欢此文档的还喜欢 ...组合数学基础组合数学基础-问题与练习 基础(陶平生) 陶平生)基本内容与方法:组合...


第二讲复习总结-体育比赛中的数学问题

组合数学复习总结 32页 1下载券喜欢此文档的还喜欢...第二讲 体育比赛中的数学问题 【前言】 体育比赛中...每一轮都要在上一轮的基础上除以 2,决出冠军最后...


广告设计基础复习资料(1)

第一讲 设计的基本涵义 这一讲主要从四个方面来...二、骨骼的分类 规律性骨骼:以严谨的数学逻辑为基础...4.对比:在构成中以相反性质的要素组合起来形成对比,...


[第17讲]排列组合和概率(中)

自主招生中的排列组合问题往往 是在高考难度的问题的基础上再考虑复杂一步,不会...(2012)数学 第二讲 教师版 3 【例题精讲】 【例1】(2010 五校联考样题)...


第八章第二讲:抽屉原理.课后练习

第八章第二讲:抽屉原理 教学目标抽屉原理是一种特殊的思维方法,不但可以根据它...抽屉原理是组合数学中一个重要而又基本的数学原理,利用它可 以解决很多有趣的...


图论第二讲

图​论​第​二​讲 暂无评价|0人阅读|0次下载|举报文档复习:图论基本...锁具装箱的第一问完全是一个数学问题,可以用 计算机程序、排列组合法、 计算机...


3年级4年级5年级年级奥数模块划分11

秋季第一讲四则运算二(乘除法巧算) 秋季第九讲 等差数列(基本概念与公式) 秋季...(数字推理) 学而思组合问题 组合数学 春季第八讲 智巧趣题(二) 暑假第七讲 ...


第二讲课后题

YY语音小升初衔接数学第二... 4页 免费 多米诺学校...金印组合 压单盘口语言 26页 免费 炒股 股票 选股...认为,劳动和资本是两个最基本的生产要素,在静态经济...


书人奥数第二讲

书人奥数第二讲_学科竞赛_小学教育_教育专区。海豚教育个性化简案学生姓名: ...题源于基本定律和性质而高于基本定律和性质, 这就要求学生具有较高的 数学素养...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com