资源描述：
《高二数学竞赛班讲义第三讲组合极值》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、高二数学竞赛班二试第三讲组合极值问题班级姓名一.知识要点：组合极值问题是各类数学竞赛的热点，它与代数，几何，数论等相比风格迥异。解组合极值问题往往需要某种技巧，因此，需耍解题者具有丰富的解题经验与良好的题感。二、经典例题1构造法我们常常通过构造抽屉，映射，表格等解决组合极值问题，有时还需要构造例子说明取到极值。1.1构造抽屉例1・(2000年中国数学奥林匹克)某次考试有5道选择题，每题都有4个不同答案供选择，每人每题恰好选1个答案。在2000份答案中发现存在一个n,使得任何n份答卷中都存在4份，其中每2份
2、的答案都至多3题相同，求n的最小可能值。例1：解：将每道题的4种答案分别记为1,2,3,4,每份试卷上的答案记为(g,h,i,j,k),其中g,h,i,j,ke{1,2,3,4}。令{(1,hfifjfk(2,hfijfk(3,hfifjfk)f(4,hfifjf^)},hfjfke{1,2,3,4}得256个四元组。由于2000=2567+208,故由抽屉原理知，有8份试卷上的答案属于同一个四元组。取出这8份试卷后，余下的1992份试卷中仍有8份试卷属于同一个四元组，再取岀这8份试卷，余下的1984
3、份试卷中又有8份属于同一个四元组。又取出这8份试卷，三次共取出24份试卷。在这24份试卷中，任何4份中总有2份的答案属于同一个四元组，当然不满足题目的要求，所以n25o下面证明n可以取到25。令s={(g,/2,z,J，^)Ig+/+7+Z:=0(mod^g,/?,z,J,Z:G{1,2,3,4}}，贝9
4、S
5、二256,且S中任何2种答案都至多有3题相同。从S中去掉6个元素，当余下的250种答案中的每种答案都恰有8人选用时，总有4份不相同。由于它们都在S中，当然满足题目要求，这表明，n二25满足题目要求。
6、综上可知，所求的n的最小可能值为25。1.2构造映射例2.将正整数n表示为一些正整数卩卫2,…,饰的和，即心绚+勺+…+勺,，其中a,1,/("+1)<*[/(〃)+f(n+2)].例2・分析：由于本题证明的是一个非严格不等式，则需要构造一个单射或满射来证之。证明：此题实质上是要证/G+l)_/S)7、便可得一个n+1的拆法，故“2+1)-/何表示的是舁+1的拆法中卩工1的拆法数。同理f(n+2)-/(n+1)是n+2的拆法中q工1的拆法数。考虑到n+l>2,把一个®工1的〃+1的拆法中的a〃加上1,就可变为一个坷幻的n+2的拆法，这样就构造了从⑦工1的斤+1的拆法到坷工1的斤+2拆法的一个对应，显然这个对应是一个单射，所以有+1)-f(n)8、有顶点均在S中的正方形组成的集合，对于S中的一个点对(两点组成)，当此点对恰是k个正方形的顶点时，则称这个点对具有k重性，所有具有k重性的点对的个数记为ak.试比较a。与勺+2冬的大小。例3•解首先证明：一个点对至多属于3个正方形，由于以点对间所连线段为一边的正方形最多有两个，而以该线段为对角线的正方形最多只有1个，故以一个点对为两个顶点的正方形不超过3个，从而对任一点对，其重性只可能为0,1,2,3,另一方面，点对总数为C；，从而CIq+6Z]+6^+03=C；(1)将任意一点对及以该点对为两顶点的正方
9、形作为一个“顶点一正方形组”，简称VS组，规定：当且仅当点对及正方形都相同时，VS组相同，设T=S,一方面，对于每一个正方形包括6个点对，故有6S个VS组；另一方面，从点对的角度考虑vs组，对于k重性的任一点对必屈于k个正方形，从而VS组的总数为1・4]+2・色+3偽，综合可得4+2a2+3色=6S(2)最后计算T中正方形的个数S。记T中两边为水平与竖直方向的正方形组成的集合为A,那么，T屮任一个正方形a,都对应着A屮的一个正方形b,使得a的顶点全在b的边界上，而对于A中一个边长为i的正方形，在T中恰
10、好有i个正方形，使得它们的顶点全在这个正方形的边界上，又A中边长为i的正方形有(n-i)2个，故s二亍心-沪二2邙，即C：?=6S(3)综合(1),(2),(3),可知d()+%+^2+。3=°1+2勺+3务。()=a2+2。3・注本题中，计算点对及VS组个数时，运用了算两次，计算
11、T
12、时，则运用了映射法计数。例4.在一节车厢中，任何m(m3)个旅客都有唯一的公共朋友(当甲是乙的朋友时，乙也是甲的朋友，任何人不作为他自己的朋友
