高中数学竞赛教材讲义 第十八章 组合讲义.pdf
《高中数学竞赛教材讲义 第十八章 组合讲义.pdf》由会员分享,可在线阅读,更多相关《高中数学竞赛教材讲义 第十八章 组合讲义.pdf(3页珍藏版)》请在三一文库上搜索。
1、第十八章 组合 一、方法与例题 1抽屉原理。 例 1 设整数 n4,a1,a2,an是区间(0,2n)内 n 个不同的整数, 证明 : 存在集合a1,a2,an 的一个子集,它的所有元素之和能被 2n 整除。 证明 (1) 若na1,a2,an,则n个不同的数属于n-1个集合1,2n-1, 2,2n-2,n- 1,n+1。 由抽屉原理知其中必存在两个数 ai,aj(ij)属于同一集合, 从而 ai+aj=2n 被 2n 整除 ; (2) 若 na1,a2,an, 不妨设 an=n, 从 a1,a2,an-1(n-13)中任意取 3 个数 ai, aj, ak(ai,0)不被 n 整除, 考虑
2、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 在 nn 的方格表的每个小方格内写有一个非负整数,并且在某一行和某一列的交叉点 处如果
3、写有 0, 那么该行与该列所填的所有数之和不小于 n。 证明 : 表中所有数之和不小于 2 2 1 n 。 证明 计算各行的和、各列的和,这 2n 个和中必有最小的,不妨设第 m 行的和最小,记和 为 k,则该行中至少有 n-k 个 0,这 n-k 个 0 所在的各列的和都不小于 n-k,从而这 n-k 列的数 的总和不小于(n-k)2,其余各列的数的总和不小于 k2,从而表中所有数的总和不小于(n-k)2+k2 . 2 1 2 )( 2 2 n kkn 3.不变量原理。 俗话说,变化的是现象,不变的是本质,某一事情反复地进行,寻找不变量是一种策略。 例 3 设正整数 n 是奇数,在黑板上写下
4、数 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,即
5、 S0,即 S0(mod4)。经有限次变号可将每个 ai都变成 1,而始 终有 S0(mod4),从而有 n0(mod4),所以 4|n。 4构造法。 例 5 是否存在一个无穷正整数数列 a1,a2a3,使得对任意整数 A,数列中仅 1 nn Aa 有有限个素数。 证明 存在。 取 an=(n!)3即可。 当 A=0 时, an中没有素数 ; 当|A|2 时, 若 n|A|, 则 an+A 均为|A|的倍数且大于|A|, 不可能为素数 ; 当 A=1 时, an1=(n!1)(n!)2n!+1, 当3 时均为合数。从而当 A 为整数时,(n!)3+A中只有有限个素数。 例 6 一个多面体共有偶
6、数条棱,试证 : 可以在它的每条棱上标上一个箭头,使得对每个顶点, 指向它的箭头数目是偶数。 证明 首先任意给每条棱一个箭头,如果此时对每个顶点,指向它的箭头数均为偶数,则 命题成立。若有某个顶点 A,指向它的箭头数为奇数,则必存在另一个顶点 B,指向它的箭头 数也为奇数(因为棱总数为偶数) ,对于顶点 A 与 B,总有一条由棱组成的“路径”连结它们, 对该路径上的每条棱,改变它们箭头的方向,于是对于该路径上除 A,B 外的每个顶点,指向 它的箭头数的奇偶性不变,而对顶点 A,B,指向它的箭头数变成了偶数。如果这时仍有顶点, 指向它的箭头数为奇数,那么重复上述做法,又可以减少两个这样的顶点,由
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高中数学竞赛教材讲义 第十八章 组合讲义 高中数学 竞赛 教材 讲义 第十八 组合
链接地址:https://www.31doc.com/p-4129985.html