当前位置:首页 >> 学科竞赛 >> 高中数学竞赛组合复习讲义

高中数学竞赛组合复习讲义


高中数学 http://www.shuxuefudao.com

高中数学竞赛 第十八章 组合 一、方法与例题 1.抽屉原理。 例 1 设整数 n≥4,a1,a2,…,an 是区间(0,2n)内 n 个不同的整数, 证明: 存在集合{a1,a2,…,an} 的一个子集,它的所有元素之和能被 2n 整除。 [ 证 明 ] ( 1 ) 若 n ? {a1,a2,

… ,an}, 则 n 个 不 同 的 数 属 于 n-1 个 集 合 {1,2n-1} , {2,2n-2},…,{n-1,n+1}。由抽屉原理知其中必存在两个数 ai,aj(i≠j)属于同一集合,从而 ai+aj=2n 被 2n 整除; (2) n∈{a1,a2,…,an}, 若 不妨设 an=n, a1,a2,…,an-1(n-1≥3)中任意取 3 个数 ai, aj, ak(ai,<aj< 从 ak),则 aj-ai 与 ak-ai 中至少有一个不被 n 整除,否则 ak-ai=(ak-aj)+(aj-ai)≥2n,这与 ak∈(0,2n) 矛盾,故 a1,a2,…,an-1 中必有两个数之差不被 n 整除;不妨设 a1 与 a2 之差(a2-a1>0)不被 n 整除,考虑 n 个数 a1,a2,a1+a2,a1+a2+a3,…,a1+a2+…+an-1。 ⅰ)若这 n 个数中有一个被 n 整除, 设此数等于 kn, k 为偶数,则结论成立; k 为奇数, 若 若 则加上 an=n 知结论成立。 ⅱ) 若这 n 个数中没有一个被 n 整除, 则它们除以 n 的余数只能取 1,2,…,n-1 这 n-1 个值, 由抽屉原理知其中必有两个数除以 n 的余数相同,它们之差被 n 整除,而 a2-a1 不被 n 整除, 故这个差必为 ai, aj, ak-1 中若干个数之和,同ⅰ)可知结论成立。 2.极端原理。 例 2 在 n×n 的方格表的每个小方格内写有一个非负整数,并且在某一行和某一列的交叉 点处如果写有 0,那么该行与该列所填的所有数之和不小于 n。证明:表中所有数之和不小 于

1 2 n 。 2

[证明] 计算各行的和、各列的和,这 2n 个和中必有最小的,不妨设第 m 行的和最小,记 和为 k,则该行中至少有 n-k 个 0,这 n-k 个 0 所在的各列的和都不小于 n-k,从而这 n-k 列 的数的总和不小于(n-k)2,其余各列的数的总和不小于 k2,从而表中所有数的总和不小于 (n-k)2+k2≥

(n ? k + k ) 2 1 2 = n . 2 2

3.不变量原理。 俗话说,变化的是现象,不变的是本质,某一事情反复地进行,寻找不变量是一种策略。 例 3 设正整数 n 是奇数,在黑板上写下数 1,2,…,2n,然后取其中任意两个数 a,b,擦 去这两个数,并写上|a-b|。证明:最后留下的是一个奇数。 [证明] 设 S 是黑板上所有数的和,开始时和数是 S=1+2+…+2n=n(2n+1),这是一个奇数, 因为|a-b|与 a+b 有相同的奇偶性,故整个变化过程中 S 的奇偶性不变,故最后结果为奇数。 例 4 数 a1, a2,…,an 中每一个是 1 或-1, 并且有 S=a1a2a3a4+ a2a3a4a5+…+ana1a2a3=0. 证明: 4|n. [证明] 如果把 a1, a2,…,an 中任意一个 ai 换成-ai,因为有 4 个循环相邻的项都改变符号,S 模 4 并不改变,开始时 S=0,即 S≡0,即 S≡0(mod4)。经有限次变号可将每个 ai 都变成 1, 而始终有 S≡0(mod4),从而有 n≡0(mod4),所以 4|n。 4.构造法。 例5 是否存在一个无穷正整数数列 a1,<a2<a3<…,使得对任意整数 A,数列 {a n + A}n =1 中


仅有有限个素数。 3 [证明] 存在。取 an=(n!) 即可。当 A=0 时,{an}中没有素数;当|A|≥2 时,若 n≥|A|,
京翰教育 http://www.zgjhjy.com/

高中数学 http://www.shuxuefudao.com

则 an+A 均为|A|的倍数且大于|A|,不可能为素数;当 A=±1 时,an±1=(n!±1)?[(n!) ± 3 n!+1],当≥3 时均为合数。从而当 A 为整数时,{(n!) +A}中只有有限个素数。 例 6 一个多面体共有偶数条棱,试证:可以在它的每条棱上标上一个箭头,使得对每个顶 点,指向它的箭头数目是偶数。 [证明] 首先任意给每条棱一个箭头,如果此时对每个顶点,指向它的箭头数均为偶数,则 命题成立。若有某个顶点 A,指向它的箭头数为奇数,则必存在另一个顶点 B,指向它的箭 头数也为奇数(因为棱总数为偶数) ,对于顶点 A 与 B,总有一条由棱组成的“路径”连结 它们,对该路径上的每条棱,改变它们箭头的方向,于是对于该路径上除 A,B 外的每个顶 点,指向它的箭头数的奇偶性不变,而对顶点 A,B,指向它的箭头数变成了偶数。如果这 时仍有顶点,指向它的箭头数为奇数,那么重复上述做法,又可以减少两个这样的顶点,由 于多面体顶点数有限,经过有限次调整,总能使和是对每个顶点,指向它的箭头数为偶数。 命题成立。 5.染色法。 例 7 能否在 5×5 方格表内找到一条线路,它由某格中心出发,经过每个方格恰好一次, 再回到出发点,并且途中不经过任何方格的顶点? [解] 不可能。将方格表黑白相间染色,不妨设黑格为 13 个,白格为 12 个,如果能实现, 因黑白格交替出现,黑白格数目应相等,得出矛盾,故不可能。 6.凸包的使用。 给定平面点集 A,能盖住 A 的最小的凸图形,称为 A 的凸包。 例 8 试证:任何不自交的五边形都位于它的某条边的同一侧。 [证明] 五边形的凸五包是凸五边形、 凸四边形或者是三角形, 凸包的顶点中至少有 3 点是 原五边形的顶点。五边形共有 5 个顶点,故 3 个顶点中必有两点是相邻顶点。连结这两点的 边即为所求。 7.赋值方法。 例 9 由 2×2 的方格纸去掉一个方格余下的图形称为拐形, 用这种拐形去覆盖 5×7 的方格 板,每个拐形恰覆盖 3 个方格,可以重叠但不能超出方格板的边界,问:能否使方格板上每 个方格被覆盖的层数都相同?说明理由。 [解] 将 5×7 方格板的每一个小方格内填写数-2 和 1。 如图 18-1 所示, 每个拐形覆盖的三 个数之和为非负。因而无论用多少个拐形覆盖多少次,盖住的所有数字之和都是非负的。另 一方面,方格板上数字的总和为 12×(-2)+23×1=-1,当被覆盖 K 层时,盖住的数字之和等 于-K,这表明不存在满足题中要求的覆盖。 -2 1 -2 1 -2 1 1 1 1 1 -2 1 -2 1 -2 1 1 1 1 1 -2 1 -2 1 -2 1 1 1 1 1 -2 1 -2 1 -2

2

8.图论方法。 例 10 生产由六种颜色的纱线织成的双色布,在所生产的双色布中,每种颜色的纱线至少 与其他三种颜色的纱线搭配过。证明:可以挑出三种不同的双色布,它们包含所有的颜色。 [证明] 用点 A1,A2,A3,A4,A5,A6 表示六种颜色,若两种颜色的线搭配过,则在相应 的两点之间连一条边。由已知,每个顶点至少连出三条边。命题等价于由这些边和点构成的 图中有三条边两两不相邻(即无公共顶点) 。因为每个顶点的次数≥3,所以可以找到两条边 不相邻,设为 A1A2,A3A4。
京翰教育 http://www.zgjhjy.com/

高中数学 http://www.shuxuefudao.com

(1)若 A5 与 A6 连有一条边,则 A1A2,A3A4,A5A6 对应的三种双色布满足要求。 (2)若 A5 与 A6 之间没有边相连,不妨设 A5 和 A1 相连,A2 与 A3 相连,若 A4 和 A6 相连, 则 A1A2,A3A4,A5A6 对应的双色布满足要求;若 A4 与 A6 不相连,则 A6 与 A1 相连,A2 与 A3 相连,A1A5,A2A6,A3A4 对应的双色布满足要求。 综上,命题得证。 二、习题精选 1.药房里有若干种药,其中一部分药是烈性的。药剂师用这些药配成 68 副药方,每副药方 中恰有 5 种药,其中至少有一种是烈性的,并且使得任选 3 种药恰有一副药方包含它们。试 问:全部药方中是否一定有一副药方至少含有 4 种烈性药?(证明或否定) 2.21 个女孩和 21 个男孩参加一次数学竞赛, (1)每一个参赛者最多解出 6 道题; (2)对 每一个女孩和每一个男孩至少有一道题被这一对孩子都解出。 求证: 有一道题至少有 3 个女 孩和至少有 3 个男孩都解出。 3.求证:存在无穷多个正整数 n,使得可将 3n 个数 1, 2,…, 3n 排成数表 a1, a2…an b1, b2…bn c1, c2…cn 满足: (1)a1+b1+c1= a2+b2+c2=…= an+bn+cn=,且为 6 的倍数。 (2)a1+a2+…+an= b1+b2+…+bn= c1+c2+…+cn=,且为 6 的倍数。 4.给定正整数 n,已知克数都是正整数的 k 块砝码和一台天平可以称出质量为 1,2,…,n 克的所有物品,求 k 的最小值 f(n)。 5.空间中有 1989 个点,其中任何 3 点都不共线,把它们分成点数各不相同的 30 组,在任 何 3 个不同的组中各取一点为顶点作三角形。试问:为使这种三角形的总数最大,各组的点 数应分别为多少? 6.在平面给定点 A0 和 n 个向量 a1,a2,…,an,且使 a1+a2+…+an =0。这组向量的每一个 排 列 a i , ai , L , a i
1 2

都 定 义 一 个 点 集 : A1 , A2 , … , An=A0 , 使 得

n

ai = A0 A1 , ai = A1 A2 ,L, ai = An ?1 An
1 2 n

求证:存在一个排列,使由它定义的所有点 A1,A2,…,An-1 都在以 A0 为角顶的某个 600 角的内部和边上。 7.设 m, n, k∈N,有 4 个酒杯,容量分别为 m,n,k 和 m+n+k 升,允许进行如下操作:将一个 杯中的酒倒入另一杯中或者将另一杯倒满为止。 开始时, 大杯中装满酒而另 3 个杯子却空着, 问:为使对任何 S∈N,S<m+n+k,都可经过若干次操作,使得某个杯子中恰有 S 升酒的关于 m,n,k 的充分必要条件是什么? 8.设有 30 个人坐在一张圆桌的周围,其中的每个人都或者是白痴,或者是聪明人。对在座 的每个人都提问: “你右边的邻座是聪明人还是白痴?”聪明人总是给出正确的答案,而白 痴既可能回答正确,也可能回答不正确。已知白痴的个数不超过 F,求总可以指出一位聪明 人的最大的 F。 9.某班共有 30 名学生,每名学生在班内都有同样多的朋友,期末时任何两人的成绩都可分 出优劣,没有相同的。问:比自己的多半朋友的成绩都要好的学生最多能有多少人?

京翰教育 http://www.zgjhjy.com/


更多相关文档:

高中数学竞赛组合复习讲义

高中数学竞赛组合复习讲义_学科竞赛_高中教育_教育专区。高中数学 http://www.shuxuefudao.com 高中数学竞赛 第十八章 组合 一、方法与例题 1.抽屉原理。 例 1 ...

高中数学竞赛讲义十二

高中数学竞赛讲义(十二)──立体几何 一、基础知识 公理 1 记作:a a. 一条直线。上如果有两个不同的点在平面。内.则这条直线在这个平面内, 公理 2 两个...

高中数学竞赛讲义(十三)──排列组合与概率

高中数学竞赛讲义(十三) ──排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法,在第 1 类办法中有 m1 种不同的方法,在第 2 类办 法中有 ...

高中数学竞赛专题练习——排列组合

高中数学竞赛专题讲座之 排列组合 二项式定理和概率 一. 排列组合二项式定理 1 ...口腔执业医师实践技能复习资料 中医护理学基础重点 执业医师实践技能考试模拟试题10289...

高中数学竞赛培训讲义(word版43页)

高中数学竞赛培训讲义(word版43页)_学科竞赛_高中教育_教育专区。2011 高中数学...(组)或不等式(组)的解、 表示充要条件, 描述排列组合,用集合的性质进行组合...

高中数学竞赛讲义(免费)

高中数学竞赛讲义(免费)_高三数学_数学_高中教育_教育专区。高中数学竞赛资料 一...组合计数,组合几何。抽屉原理。容 斥原理。极端原理。图论问题。集合的划分。...

竞赛复习科目:数学 高中数学竞赛总复习(一)

百度文库 专业资料 竞赛复习科目:数学 高中数学竞赛总复习(一)_专业资料 暂无评价|0人阅读|0次下载|举报文档竞赛复习科目:数学 高中数学竞赛总复习(一)_专业资料...

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

柳铁一中组合高中数学竞赛同步讲义_学科竞赛_高中教育_教育专区。高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品! 高中数学竞赛同步讲义——组合数学基...

全国高中数学联赛组合数学真题集(一)

全国高中数学联赛组合数学真题集(一)_学科竞赛_高中教育_教育专区。高 2013 级高一下学期数学竞赛培训资料——铁一出品,必属精品! 全国高中数学联赛组合数学真题集...

高中数学竞赛讲义(13)排列组合与概率

高中数学竞赛讲义(13)排列组合与概率_学科竞赛_高中教育_教育专区。高中数学竞赛讲义(十三) ──排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com