9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

高中数学竞赛



第十八章 组合 一、方法与例题 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),


更多相关文章:
2012年浙江省高中数学竞赛试题及答案(word版本)
2012年浙江省高中数学竞赛试题及答案(word版本)_学科竞赛_高中教育_教育专区。2012 年浙江省高中数学竞赛试题 总分 200 分一、选择题(50 分) 1、已知 i 是虚数...
2004年全国高中数学联赛试题及解答
1978年全国高中数学联赛... 1979年全国高中数学竞赛... 1981年全国高中数学联赛... 1982年全国高中数学联赛... 1983年全国高中数学联赛... 1984年全国高中数学联...
高一数学竞赛试题5
高一数学竞赛试题5_学科竞赛_高中教育_教育专区。高中数学竞赛试题及答案高一数学竞赛试题(1) (注意:共有二卷,时间 100 分钟, 满分 150) 第一卷(本卷 100 分...
2014年全国高中数学联赛试题
2014年全国高中数学联赛试题_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2014年全国高中数学联赛试题_学科竞赛_高中教育_教育专区。2014 年全国...
高一数学竞赛
高一数学竞赛题_高一数学_数学_高中教育_教育专区。.高一数学竞赛试题班级 一、选择题 1、集合 A+{x|x=2K,k∈z},B={x|x=2k+1 k∈z} C{x|x=4k+1...
2011年浙江省高中数学竞赛试题及参考答案
3 2011 年浙江省高中数学竞赛参考解答与评分标准 年浙江省高中数学竞赛参考解答与评分标准 1.解答:因为 θ∈ [ 5π 3π , ] ,所以 1 ? sin 2θ ? 1 +...
高中数学竞赛 第24讲 三角不等式教案
高中数学竞赛 第24讲 三角不等式教案 隐藏>> 第24 讲 三角不等式 含有未知数的三角函数的不等式叫做三角不等式.三角不等式首先是不等式,因此, 处理不等式的常用...
2000年全国高中数学联赛试题及解答
2000年全国高中数学联赛试题及解答。高中数学竞赛试题,可以研究研究以求得对数学的更深入了解。2000 年全国高中数学联赛 冯惠愚 2000 年全国高中数学联合竞赛试卷 (10...
1997年全国高中数学联赛试题及解答
1997 年全国高中数学联赛 冯惠愚 1997 年全国高中数学联合竞赛试卷第一试 (10 月 5 日上午 8:00?10:00) 一、选择题(每小题 6 分,共 36 分) 1.已知...
2016年全国高中数学联赛江苏赛区初赛试卷
2016年全国高中数学联赛江苏赛区初赛试卷_学科竞赛_高中教育_教育专区。2016年全国高中数学联赛江苏赛区初赛试卷 2016 年全国高中数学联赛江苏赛区初赛试卷考生注意:1....
更多相关标签:
数学竞赛    高中数学竞赛辅导书    高中数学竞赛试题    全国高中数学联赛    高中物理竞赛    高中数学联赛    高中数学    王后雄    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图