资源描述：
《《组合极值问题》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、精彩文档，无偿分享！组合极值问题组合极值问题是各类数学竞赛的热点，它与代数，几何，数论等相比风格迥异。解组合极值问题往往需要某种技巧，因此，需要解题者具有丰富的解题经验与良好的题感。1构造法我们常常通过构造抽屉，映射，表格等解决组合极值问题，有时还需要构造例子说明取到极值。1.1构造抽屉例1：(2000年中国数学奥林匹克)某次考试有5道选择题，每题都有4个不同答案供选择，每人每题恰好选1个答案。在2000份答案中发现存在一个n，使得任何n份答卷中都存在4份，其中每2份的答案都至多3题相同，求n的最
2、小可能值。解：将每道题的4种答案分别记为1，2，3，4，每份试卷上的答案记为,其中。令,,共得256个四元组。由于2000=256´7+208，故由抽屉原理知，有8份试卷上的答案属于同一个四元组。取出这8份试卷后，余下的1992份试卷中仍有8份试卷属于同一个四元组，再取出这8份试卷，余下的1984份试卷中又有8份属于同一个四元组。又取出这8份试卷，三次共取出24份试卷。在这24份试卷中，任何4份中总有2份的答案属于同一个四元组，当然不满足题目的要求，所以n³25。下面证明n可以取到25。令，则
3、S
4、
5、=256，且S中任何2种答案都至多有3题相同。从S中去掉6个元素，当余下的250种答案中的每种答案都恰有8人选用时，总有4份不相同。由于它们都在S中，当然满足题目要求，这表明，n=25满足题目要求。综上可知，所求的n的最小可能值为25。1.2构造映射例2将正整数n表示为一些正整数的和，即，其中，记是如此表示的方法种数（如4=4，4=1+3，4=2+2，4=1+1+2，4=1+1+1+1，故），证明：对任意.分析：由于本题证明的是一个非严格不等式，则需要构造一个单射或满射来证之。证明：此题实质上是
6、要证精彩文档，无偿分享！因将每个n的拆法前加一个“1”，便可得一个n+1的拆法，故表示的是的拆法中的拆法数。同理是n+2的拆法中的拆法数。考虑到，把一个的的拆法中的加上1，就可变为一个的n+2的拆法，这样就构造了从的的拆法到的拆法的一个对应，显然这个对应是一个单射，所以有评注：应用映射法可以证明一些与计数有关的不等式。例3设n是一个正整数，，设T是所有顶点均在S中的正方形组成的集合，对于S中的一个点对（两点组成），当此点对恰是k个正方形的顶点时，则称这个点对具有k重性，所有具有k重性的点对的个数记
7、为试比较的大小。解首先证明：一个点对至多属于3个正方形，由于以点对间所连线段为一边的正方形最多有两个，而以该线段为对角线的正方形最多只有1个，故以一个点对为两个顶点的正方形不超过3个，从而对任一点对，其重性只可能为0，1，2，3，另一方面，点对总数为，从而(1)将任意一点对及以该点对为两顶点的正方形作为一个“顶点一正方形组”，简称VS组，规定：当且仅当点对及正方形都相同时，VS组相同，设，一方面，对于每一个正方形包括6个点对，故有6S个VS组；另一方面，从点对的角度考虑VS组，对于k重性的任一点对
8、必属于k个正方形，从而VS组的总数为，综合可得（2）最后计算T中正方形的个数S。精彩文档，无偿分享！记T中两边为水平与竖直方向的正方形组成的集合为A，那么，T中任一个正方形a，都对应着A中的一个正方形b，使得a的顶点全在b的边界上，而对于A中一个边长为i的正方形，在T中恰好有i个正方形，使得它们的顶点全在这个正方形的边界上，又A中边长为i的正方形有个，故即（3）综合（1），（2），（3），可知注本题中，计算点对及VS组个数时，运用了算两次，计算
9、T
10、时，则运用了映射法计数。例4：在一节车厢中，任何
11、m(m³3)个旅客都有唯一的公共朋友(当甲是乙的朋友时，乙也是甲的朋友，任何人不作为他自己的朋友)。问在这节车厢中，朋友最多的人有多少个朋友？解：设朋友最多的人A有k个朋友，记为B1,B2,¼,Bk,并记。显然，。若k>m,设是S的任一个m元子集，则这m个人有1个公共朋友，记为Ci,因为Ci是A的朋友，所以CiÎS。定义映射：，则¦是从S的所有m-1元子集的集合到S的一个单射。事实上，若存在S的两个不同的m-1元子集和均有相同的像Ci,又因为È中至少有m个元素，故这m个人有2个公共朋友A和Ci，与
12、已知矛盾。由于¦是单射，故,因为m³3,m-1³2,所以(k-1)(k-2)(k-3)(k-m+2)>(m-1)(m-2)¼2=(m-1)!故矛盾，可见所求k=m.1.3构造图表例5：设nÎN+,n³2,S是一个n元集合，求最小的正整数k，使得存在S的子集A1,A2,¼，Ak具有如下性质：对S中的任意两个不同元素a,b，存在jÎ{1,2,¼,k},使AjÇ{a,b}为S的一元子集。精彩文档，无偿分享！解：设，构造表格1：123nA1100A2010A3AkP1P2P3Pn如果，那么
