资源描述:
《数学竞赛讲座48192543》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数学竞赛讲座1抽屉原则抽屉原则的常见形式一,把n+k(k≥1)个物体以任意方式全部放入n个抽屉中,一定存在一个抽屉中至少有两个物体。二,把mn+k(k≥1)个物体以任意方式全部放入n个抽屉中,一定存在一个抽屉中至少有m+1个物体。三,把m1+m2+…+mn+k(k≥1)个物体以任意方式全部放入n个抽屉中,那么后在一个抽屉里至少放入了m1+1个物体,或在第二个抽屉里至少放入了m2+1个物体,……,或在第n个抽屉里至少放入了mn+1个物体四,把m个物体以任意方式全部放入n个抽屉中,有两种情况:①当n
2、m时(n
3、m表示n整除m),一定存在一个抽屉中至少放入了个物体;②当n不能整除m时
4、,一定存在一个抽屉中至少放入了[]+1个物体([x]表示不超过x的最大整数)五,把无穷多个元素分成有限类,则至少有一类包含无穷多个元素。注:背下来上面的几种形式没有必要,但应当清楚这些形式虽然不同,却都表示的一个意思。理解它们的含义最重要。在各种竞赛题中,往往抽屉原则考得不少,但一般不会很明显的让人看出来,构造抽屉才是抽屉原则中最难的东西。一般来说,题目中一旦出现了“总有”“至少有”“总存在”之类的词,就暗示着我们:要构造抽屉了。2容斥原理容斥原理常常使用,其实说简单点,就是从多的往下减,减过头了在加回来,又加多了再减,减多了再加……,最终得到正确结果。对于计数中容易出现重复的
5、题目,我们常常采用容斥原理,去掉重复的情况。容斥原理基本形式:其中
6、A
7、表示集合A中元素的个数。3递推方法许多竞赛题目正面计算十分困难,于是我们避开正面计算,先考虑n-1时的情况,在计算n时的情况比n-1时的情况增添了多少,然后写出一个递推式,这样就可以利用数列的知识进行解决,但一般要求根据递推式求通项的能力要比较强,是和擅长数列的同学使用。没什么具体解释,多多练习吧4映射计数个人认为映射计数绝对是计数方法中最经典的一种,常常能将复杂至极的问题简单化,变成人人都会做的普通题目。但是想熟练掌握往往是不容易的,要求有大量的习题积累,才能形成建立映射的能力。明确概念:对于y=f(x)
8、单射:不同的x对应不同的y,即
9、x
10、≤
11、y
12、满射:每个y至少有一个x映射,即
13、x
14、≥
15、y
16、双射:即是单射又是满射,即
17、x
18、=
19、y
20、倍数映射:
21、x
22、=m
23、y
24、注:双射即通常说的一一映射,有的人将双射理解为m=2的倍数映射或其他映射,这是不对的。不要从感觉上去理解。双射应当是“单射”“满射”的综合。利用映射解题,一般是建立双射,将要证明的问题转化为其他的问题,但是计算总数不变。而我们不仅要会建立双射,也应会建立单射和满射,因为显然建立单射和满射是证明不等关系的极好方法,不可以忽略。利用倍数映射解决的题目,我目前还没遇到多少,但还是要时刻记着有这样一种方法。一,建立双射集合{1,2,
25、……,2004}有多少个元素和为奇数的子集?将正整数n写成若干个1与若干个2之和,和项的顺序不同认为是不同的写法,所有写法的种数记为A(n);将正整数n写成若干个大于1的正整数之和,和项顺序不同认为是不同的写法,所有写法的种数记为B(n),求证:A(n)=B(n+2)注:此题即为很好的映射计数例子。因为即便不用映射我们可以把A(n)求出来,再把B(n+2)求出来,然后比较后会发现两者相等,但这显然是超大工作量,如果使用了映射计数,我们只需用一些技巧,在A(n)和B(n+2)中建立双射,此题即得到证明。二,建立单射或满射注:映射计数可能会有一定难度,如果觉得掌握不了也不要灰心,只
26、要多练,时间一长自然就会了。不等式与最值1平均不等式等号成立当且仅当注意:运用平均不等式需注意各项均为正数!题外话:有很多同学十分“痛恨”这两个符号,总是看不懂,其实这两个符号是绝对好用的,并且以后会常常遇到,在大学课本中更是家常便饭,多看几次自然也就习惯了。例求证:分析:为了凑出a+b+c+d,以便充分利用条件,将4a+1,4b+1,4c+1,4d+1视作整体,利用平均不等式。2柯西不等式及其变形设(i=1,2,…,n),则其中等号成立,当且仅当为定值注:这个式子在竞赛中极为常用,只需简记为“积和方小于方和积”。等号成立条件比较特殊,要牢记。此外应注意在这个式子里不要求各项均
27、是正数,因此应用范围较广。常用变形一:(i=1,2,…,n),则注:要求bi为正数常用变形二:若(i=1,2,…,n),则注:要求ai,bi均为正数。当然,这两个式子虽常用,但是记不记并不太重要,只要将柯西不等式原始的式子记得很熟,这两个式子其实是一眼就能看出来的,这就要求我们对柯西不等式要做到活学活用。例:若的最小值。并指出等号成立的条件。分析:由于a,b,c,d各项系数不同,而且既有1次项,又有2次项,显然要用柯西不等式。而且使用柯西不等式不受-7c这项的影响。使用时,注意写明等号成立条