《高二数学竞赛班讲义第三讲组合极值》由会员分享，可在线阅读，更多相关《高二数学竞赛班讲义第三讲组合极值（8页珍藏版）》请在金锄头文库上搜索。
1、1高二数学竞赛班二试高二数学竞赛班二试 第三讲第三讲 组合极值问题组合极值问题班级班级 姓名姓名 一、知识要点：一、知识要点： 组合极值问题是各类数学竞赛的热点，它与代数，几何，数论等相比风格 迥异。解组合极值问题往往需要某种技巧，因此，需要解题者具有丰富的解题 经验与良好的题感。二、经典例题二、经典例题 1 构造法构造法 我们常常通过构造抽屉，映射，表格等解决组合极值问题，有时还需要构 造例子说明取到极值。 1.1 构造抽屉 例例 1(2000 年中国数学奥林匹克)某次考试有 5 道选择题，每题都有 4 个不同 答案供选择，每人每题恰好选 1 个答案。在 2000 份答案中发现存在一个 n
2、， 使得任何 n 份答卷中都存在 4 份，其中每 2 份的答案都至多 3 题相同，求 n 的最小可能值。 例例 1：解：将每道题的 4 种答案分别记为 1 ，2 ，3 ，4 ，每份试卷上的答案记为,其中。令k , j , i , h ,g4321,k , j , i , h ,g,共得 256 个四元组。k , j , i , h ,k , j , i , h ,k , j , i , h ,k , j , i , h ,43214321,k , j , i , h由于 2000=2567+208，故由抽屉原理知，有 8 份试卷上的答案属于同一 个四元组。取出这 8 份试卷后，余下的 1992
3、 份试卷中仍有 8 份试卷属于同一个 四元组，再取出这 8 份试卷，余下的 1984 份试卷中又有 8 份属于同一个四元组。 又取出这 8 份试卷，三次共取出 24 份试卷。在这 24 份试卷中，任何 4 份中总 有 2 份的答案属于同一个四元组，当然不满足题目的要求，所以 n 25 。 下面证明 n 可以取到 25。令，则 |S| =256 ，432140,k , j , i , h ,g,modkjihg|k , j , i , h ,gS且 S 中任何 2 种答案都至多有 3 题相同。从 S 中去掉 6 个元素，当余下的 250 种答案中的每种答案都恰有 8 人选用时，总有 4 份不相同
4、。由于它们都在 S 中， 当然满足题目要求，这表明，n = 25 满足题目要求。综上可知，所求的 n 的最 小可能值为 25。1.2 构造映射例例 2将正整数 n 表示为一些正整数的和，即paaa,21，其中，记是如此表示的方法种数paaan21paaa21)(nf2（如 4=4，4=1+3，4=2+2，4=1+1+2，4=1+1+1+1，故） ，证明：对任5)4(f意.)2()(21) 1(, 1nfnfnfn例例 2分析：由于本题证明的是一个非严格不等式，则需要构造一个单射或满射来证之。证明：此题实质上是要证).1()2()() 1(nfnfnfnf因将每个 n 的拆法前加一个“1” ，便
5、可得一个 n+1 的拆法，故表示的是的拆法中的拆法数。)() 1(nfnf1n11a同理是 n+2 的拆法中的拆法数。) 1()2(nfnf11a考虑到，把一个的的拆法中的加上 1，就可变为一个21n11a1npa的 n+2 的拆法，这样就构造了从的的拆法到的拆法11a11a1n11a2n的一个对应，显然这个对应是一个单射，所以有).1()2()() 1(nfnfnfnf评注：应用映射法可以证明一些与计数有关的不等式。例例 3设 n 是一个正整数，设 T 是所有( , )|1,1, ,Sx yxnyn x yZ顶点均在 S 中的正方形组成的集合，对于 S 中的一个点对（两点组成） ，当此点对恰
6、是 k 个正方形的顶点时，则称这个点对具有 k 重性，所有具有 k 重性的点对的个数记为试比较的大小。.ka3202aaa与例例 3解 首先证明：一个点对至多属于 3 个正方形，由于以点对间所连线段为一边的正方形最多有两个，而以该线段为对角线的正方形最多只有 1 个，故以一个点对为两个顶点的正方形不超过 3 个，从而对任一点对，其重性只可能为 0，1，2，3，另一方面，点对总数为，从而2 2nC(1) 2 32102nCaaaa将任意一点对及以该点对为两顶点的正方形作为一个“顶点一正方形组” ，简称 VS 组，规定：当且仅当点对及正方形都相同时，VS 组相同，设，ST |一方面，对于每一个正方
7、形包括 6 个点对，故有 6S 个 VS 组；另一方面，从点3对的角度考虑 VS 组，对于 k 重性的任一点对必属于 k 个正方形，从而 VS 组的总数为，综合可得321321aaa（2）Saaa632321最后计算 T 中正方形的个数 S。记 T 中两边为水平与竖直方向的正方形组成的集合为 A，那么，T 中任一个正方形 a，都对应着 A 中的一个正方形 b，使得 a 的顶点全在 b 的边界上，而对于 A 中一个边长为 i 的正方形，在 T 中恰好有 i 个正方形，使得它们的顶点全在这个正方形的边界上，又 A 中边长为 i 的正方形有个，2)(in 故,61)(2112 2nniCiniS即
8、（3）SCn62 2综合（1） ， （2） ， （3） ，可知,323213210aaaaaaa.2320aaa注 本题中，计算点对及 VS 组个数时，运用了算两次，计算|T|时，则运用了映射法计数。 例例 4在一节车厢中，任何 m ( m 3 )个旅客都有唯一的公共朋友(当甲是乙的 朋友时，乙也是甲的朋友，任何人不作为他自己的朋友)。问在这节车厢中，朋 友最多的人有多少个朋友？ 例例 4解：设朋友最多的人 A 有 k 个朋友，记为 B1 , B2 , , Bk , 并记。显然， 。kB,B,BS21mk 若 k m ,设是 S 的任一个元子集，则 121miiiB,B,B1m这 m 个人有
9、1 个公共朋友，记为 Ci ,因为 Ci是 A 的朋友，所 121miiiB,B,B,A以 Ci S 。定义映射：，则 是从 S 的所有 m 1 元子集的集合到 SSCB,B,Bfiiiim 121：的一个单射。事实上，若存在 S 的两个不同的 m 1 元子集和 121miiiB,B,B均有相同的像 Ci ,又因为中 121mjjjB,B,B 121miiiB,B,B 121mjjjB,B,B至少有 m 个元素，故这 m 个人有 2 个公共朋友 A 和 Ci ，与已知矛盾。4由于 是单射，故 ,因为 m 3 , m 1 2 ,所以kCm k1( k 1 ) ( k 2 ) ( k 3 ) (
10、k m + 2 ) ( m 1 ) ( m 2 ) 2 = ( m 1) 故 11221 ! 1 !1 !m kk kkkmk mCkmm矛盾，可见所求 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 的一元子集。例例 5解：设，构造表格 1：n ,S321123n A1100 A2010 A3 Ak P1P2P3Pn如果，那么，在所在行， 所在列处的方格中
11、标上 1，其余的方格jAijAi中标上 0。考虑表 1 的列构成的序列 ，下面证明：S 的子集nP,P,P21具有题中性质的充分必要条件是两两不同。kA,A,A21nP,P,P21充分性：由两两不同，则对任意有，所以在某nP,P,P21, ba ,Sb ,abaPP 一行(设为第行)上，第列与第列的方格中一个为 1，而另一个为 0。这表jab 明为单元素集，故具有题中性质。 b ,aAjkA,A,A21必要性：由于对任意存在，使为单元素集，, ba ,Sb ,ak ,j21 b ,aAj则与在第行处的两个方格中的数一个为 1，而另一个为 0，故。aPbPjbaPP 所以两两不同。根据表 1 知
12、：nP,P,P2122,logknkn2log11kn52 染色法染色法 例例 6设 n 是一个固定的正偶数，考虑一块的正方形板，它被分成 n2个单nn 位正方形格，板上 2 个不同的正方形格如果有一条公共边，就称它们为相邻的。 将板上 N 个单位正方形格作上标记，使得板上的任意正方形格(作上标记的或者 没有作上标记的)都与至少一个作上标记的正方形格相邻，试确定 N 的最小值。 例例 6解：设 n = 2k，首先将正方形板黑白相间地染成像国际象棋棋盘那样。设为所求的 N 的最小值，为必须作上标记的白格子的最小数目，使得 nf nfa任一黑格子都有一个作上标记的白格子与之相邻。同样的，定义为必须
13、作 nfb上标记的黑格子的最小数目，使得任一白格子都有一个作上标记的黑格子与之相邻。由于 n 是偶数， “棋盘”是对称的，故有， nfnfba，为方便起见，将“棋盘”按照最长的黑格子对角线水平放 nfnfnfba置，则各行黑格子的个数分别为。在含有个黑格子的那行24242,k,24 i 下面，将奇数位置的白格子作上标记。当该行在对角线上方时，共有个白格i 2 子作上了标记；当该行在对角线下方时，共有个白格子作上了标记。从而，12 i 作上了标记的白格子共有个，所以这时每个黑格子都与 1 个作上标记的 211342kkk白格子相邻，故得。考虑这个作上标记的白格子，它们 21kknfa 21kk中
14、的任意两个没有相邻的公共黑格子，所以，至少还需要将个黑格子作 21kk上标记，以保证这些白格子中的每一个都有一个作上标记的黑格子与之相邻，从而，故。因此，。 21kknfb 21kknfnfba 1kknf3 调整法调整法例例 7给定平面上的点集，且 P 中任三点均不共线。将 P 中199421P,P,PP所有的点任意分成 83 组，使得每组至少有三个点，且每点恰好属于一组，然后， 将在同一组的任两个点用一条线段相连，不在同一组的两个点不连线段，这样 得到一个图案 G。不同的分组方式得到不同的图案。将图案 G 中所含的以 P 中 的点为顶点的三角形的个数记为 m(G)。(1) 求 m(G)的最小值 ；0m(2) 设是使的一个图案，若将中的线段(指以 P 的点为端点的线G 0mGmG段)用 4 种颜色染色，每条线段恰好染 1 种颜色。证明：存在一种染色方案，使染色后不含以 P 的点为顶点的三边颜色相同的三角形。G6例例 7解：(1)设 m(G)= ，G 由分组得到，其中为第 组的点0m8321X,X,XiXi构成的集合，。令，则有83321,i8321,i ,xXii，且。下面证明：当19948321xxx333 08321xxxCCCm
