组合极值问题

1、组合极值问题组合极值问题是各类数学竞赛的热点，它与代数，几何，数论等相比风格迥异。解组合极值问题往往需要某种技巧，因此，需要解题者具有丰富的解题经验与良好的题感。1 构造法我们常常通过构造抽屉，映射，表格等解决组合极值问题，有时还需要构造例子说明取到极值。1.1构造抽屉例1：(2000年中国数学奥林匹克)某次考试有5道选择题，每题都有4个不同答案供选择，每人每题恰好选1个答案。在2000份答案中发现存在一个 n ，使得任何 n 份答卷中都存在4份，其中每2份的答案都至多3题相同，求 n 的最小可能值。解：将每道题的4种答案分别记为1 ，2 ，3 ，4 ，每份试卷上的答案记为,其中。令,共得25

2、6个四元组。由于2000=256´7+208，故由抽屉原理知，有8份试卷上的答案属于同一个四元组。取出这8份试卷后，余下的1992份试卷中仍有8份试卷属于同一个四元组，再取出这8份试卷，余下的1984份试卷中又有8份属于同一个四元组。又取出这8份试卷，三次共取出24份试卷。在这24份试卷中，任何4份中总有2份的答案属于同一个四元组，当然不满足题目的要求，所以 n ³ 25 。下面证明 n 可以取到25。令，则 |S| =256 ，且S中任何2种答案都至多有3题相同。从 S 中去掉6个元素，当余下的250种答案中的每种答案都恰有8人选用时，总有4份不相同。由于它们都在S中，当

3、然满足题目要求，这表明，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，故），证明：对任意.分析：由于本题证明的是一个非严格不等式，则需要构造一个单射或满射来证之。证明：此题实质上是要证因将每个n的拆法前加一个“1”，便可得一个n+1的拆法，故表示的是的拆法中的拆法数。同理是n+2的拆法中的拆法数。考虑到，把一个的的拆法中的加上1，就可变为一个的n+2的拆法，这样就构造了从的的拆法到的拆法的一个对应，显然这个对应是一个单射，

4、所以有评注：应用映射法可以证明一些与计数有关的不等式。例3 设n是一个正整数，设T是所有顶点均在S中的正方形组成的集合，对于S中的一个点对（两点组成），当此点对恰是k个正方形的顶点时，则称这个点对具有k重性，所有具有k重性的点对的个数记为试比较的大小。解 首先证明：一个点对至多属于3个正方形，由于以点对间所连线段为一边的正方形最多有两个，而以该线段为对角线的正方形最多只有1个，故以一个点对为两个顶点的正方形不超过3个，从而对任一点对，其重性只可能为0，1，2，3，另一方面，点对总数为，从而 (1) 将任意一点对及以该点对为两顶点的正方形作为一个“顶点一正方形组”，简称VS组，规定：当且仅当点对

5、及正方形都相同时，VS组相同，设，一方面，对于每一个正方形包括6个点对，故有6S个VS组；另一方面，从点对的角度考虑VS组，对于k重性的任一点对必属于k个正方形，从而VS组的总数为，综合可得 （2）最后计算T中正方形的个数S。记T中两边为水平与竖直方向的正方形组成的集合为A，那么，T中任一个正方形a，都对应着A中的一个正方形b，使得a的顶点全在b的边界上，而对于A中一个边长为i的正方形，在T中恰好有i个正方形，使得它们的顶点全在这个正方形的边界上，又A中边长为i的正方形有个，故即 （3）综合（1），（2），（3），可知注 本题中，计算点对及VS组个数时，运用了算两次，计算|T|时，则运用了映射

6、法计数。例4：在一节车厢中，任何 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 ,又因为

7、È中至少有 m 个元素，故这 m 个人有2个公共朋友A和Ci ，与已知矛盾。由于¦ 是单射，故 ,因为 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中的任意

8、两个不同元素 a , b ，存在 j Î 1 ,2 , ¼ , k , 使 Aj Ç a , b 为S的一元子集。解：设，构造表格1：123nA1100A2010A3AkP1P2P3Pn如果，那么，在所在行，所在列处的方格中标上1，其余的方格中标上0。考虑表1的列构成的序列 ，下面证明：S 的子集具有题中性质的充分必要条件是两两不同。充分性：由两两不同，则对任意有，所以在某一行(设为第行)上，第列与第列的方格中一个为1，而另一个为0。这表明为单元素集，故具有题中性质。必要性：由于对任意存在，使为单元素集，则与在第行处的两个方格中的数一个为1，而另一个为0，故。所以

9、两两不同。根据表1知：2 染色法例6：设n 是一个固定的正偶数，考虑一块的正方形板，它被分成n2个单位正方形格，板上2个不同的正方形格如果有一条公共边，就称它们为相邻的。将板上N个单位正方形格作上标记，使得板上的任意正方形格(作上标记的或者没有作上标记的)都与至少一个作上标记的正方形格相邻，试确定N的最小值。解：设n = 2k，首先将正方形板黑白相间地染成像国际象棋棋盘那样。设为所求的N的最小值，为必须作上标记的白格子的最小数目，使得任一黑格子都有一个作上标记的白格子与之相邻。同样的，定义为必须作上标记的黑格子的最小数目，使得任一白格子都有一个作上标记的黑格子与之相邻。由于n是偶数，“棋盘”是

10、对称的，故有，为方便起见，将“棋盘”按照最长的黑格子对角线水平放置，则各行黑格子的个数分别为。在含有个黑格子的那行下面，将奇数位置的白格子作上标记。当该行在对角线上方时，共有个白格子作上了标记；当该行在对角线下方时，共有个白格子作上了标记。从而，作上了标记的白格子共有个，所以这时每个黑格子都与1个作上标记的白格子相邻，故得。考虑这个作上标记的白格子，它们中的任意两个没有相邻的公共黑格子，所以，至少还需要将个黑格子作上标记，以保证这些白格子中的每一个都有一个作上标记的黑格子与之相邻，从而，故。因此，。3 调整法例7：给定平面上的点集，且P中任三点均不共线。将P中所有的点任意分成83组，使得每组至

11、少有三个点，且每点恰好属于一组，然后，将在同一组的任两个点用一条线段相连，不在同一组的两个点不连线段，这样得到一个图案G。不同的分组方式得到不同的图案。将图案G中所含的以P中的点为顶点的三角形的个数记为m(G)。(1) 求m(G)的最小值 ；(2) 设是使的一个图案，若将中的线段(指以P的点为端点的线段)用4种颜色染色，每条线段恰好染1种颜色。证明：存在一种染色方案，使染色后不含以P的点为顶点的三边颜色相同的三角形。 解：(1)设m(G)= ，G由分组得到，其中为第组的点构成的集合，。令，则有，且。下面证明：当时，有。事实上，若存在使得，不妨设，作P的点的分组(为第i组的点构成的集合，)，使得

12、 这样的分组存在(只需从原来的中取一点到中，其余组的不动)，于是对于由分组得到的图案G，有故=因为，所以，故与m0的最小性矛盾又1994=83×24+2=81×24+2×25故（2）设图案由分组得到，这里Xi表示第i组的点构成的集合（i=1,2,，83）。由（1），不妨设下面给出G*的一种染色方法，使得G*用4种不同颜色染后不含三边颜色相同的三角形。将集合Xi及所连线段构成的图形称为G*的第i块，记为对于，令使得将每个子集中任两个点所连线段用图1所示的方法去染，将不同子集与之间所连线段用图2所示的方法去染，图中a、b、c、d分别代表4种不同颜色，这样，染后的显然不

13、含三边颜色相同的三角形y1ccaaaaabbbbb图1 y5y2dddddccy4y3c图2 对于，可用染的方法去染，至于的染法，可先加1点并将该点与原来的24点各连一条线段，然后，按的染法染好，再把加的1点及与该点所连的线段去掉，这样，染后的也不含三边颜色相同的三角开。4 归纳猜想 例8 给定平面上无三点共线的n个点，以这n个点为端点连出了m条线段，已知对这n个点中的任意两点A、B，都有一点C，使得C与A、B都有线段相连，求m的最小值 解：记这n个点为A1，A2，An，先看一个例子 如果n为奇数，连线段A1A2，A1A3，A1An；A2A3，A4A5，An-1An. 如果n为偶数，连线段A1A2，A1A3，A1An；A2A3，A4A5，An-2An-1, A2An. 显然，依上述方法连出的线段满足条件，所以，所求m的最小值小于或等于。（注：为上面连出的线段的条数，这里表示不超过x的最大整数。）下面证明：这n个点至少需要连出条线段，才能达到题中要求。 事实上，如果A1，A2，An中任意一点都引出至少3条线段，则； 如果其中有一点（不妨设为A1）引出的线段条数不大于2，那么，有如下两种情形： （1）A1只引出1条线段，不妨设为A1A2，则与A1，A2都有线段相连的点不存在，矛盾同样地，若A1不引出线段也可得矛盾。 （2