组合极值问题_第1页
组合极值问题_第2页
组合极值问题_第3页
组合极值问题_第4页
组合极值问题_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、56个四元组。由于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为偶数,连线段A

14、1A2,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)A1恰引出2条线段A1A2、A1A3,这时,一定要连出线段A2

15、A3(因为对于两点A1、A2,只能是A3与A1、A2都相连) 考虑点A1、Ai(i4),由Ai必与A2、A3中的某一点有线段相连,又由(1)可知,Ai至少引出2条线段,所以,从A4、A5,An这n-3个点至少引出条线段,则这n个点引出的线段的条数不少于因此,m的最小值为注:解此题先构造例子,猜出m的最小值,然后再证明,这种“先猜后证”的思想也是解决组合极值问题的常见方法。高中数学联赛模拟试题一一试一选择题(本题满分分,每小题分)1若则称函数是无穷小(其中)。特别地,如果函数都是无穷小,且满足,则称函数是等价无穷小。根据以上定义,下面的( )是等价无穷小。(A) (B)(C) (D)2.已知则3

16、、设MN=,则 ( ) 4、在四面体ABCD中,面ABC及BCD都是边长为2的等边三角形,且ADa,M、N分别为棱AB、CD的中点,则在四面体表面上M与N的最短距离为 ( ) 5、已知三个三角形、 、的周长分别为,且,较小的两个三角形可以互不重叠地放入大三角形的内部,则的最大值是 ( ) 6、已知自然数n不是5的倍数,则5除时有 ( ) 不能确定,都有可能发生二、填空题(本题满分分,每小题分)7、设其中是不小于3的自然数,则形如的全体分数之和为_8、在ABC中,已知三内角A、B、C成等差数列,若其对边分别为,并且等于AC边上的高h,则=_9.已知定义在实数集上的函数满足,则10、从集合中任取两

17、个不相邻的数(这两个数可以相同)相乘,所有这样的积再求和等于_11.在直角坐标平面中一椭圆的两个焦点为且椭圆与纵轴相切,则椭圆短轴长为_12.设,且,则的大小关系为_三、解答题(本题满分分,每小题分)13已知M是抛物线上的动弦AB上的点,O为坐标原点,OAOB,OMAB,求点M的轨迹方程.若F(x)的反函数为F-1(x),证明方程F-1(x)=0有唯一解;并求出该唯一解15定义在(-1,1)上的函数f(x)满足:()对任意x,y(-1,1)都有f(x)+f(y)=f();()当x(-1,0)时,有f(x)0.求证: 加试一(本题满分分)如图,等腰中,为边上一点,边的中点为,连接,为线段上的两点

18、,且若的面积为的面积的倍,求 二(本题满分分)求证:只要二次函数满足条件: (1) a>0(2) |f(x)|当x(3)就必有当。三(本题满分分)将正整数表示为一些正整数的和,其中 ,记 是如此表示的方法种数(如 , ,故 )求证对任意 。高中数学联赛模拟试题一参考答案一试一选择题(本题满分分,每小题分)1若则称函数是无穷小(其中)。特别地,如果函数都是无穷小,且满足,则称函数是等价无穷小。根据以上定义,下面的( B )是等价无穷小。(A) (B)(C) (D)解:根据定义,本题目正确答案为B2.已知则解:由已知条件得考虑到函数是实数集上的奇函数,且为单调增函数,所以得到,即选C3、设M

19、N=,则 ( B ) 解:由集合M化简得:,图象为一、四象限各一支,又由tg(arctgx+arcctgy)=0得:得:可知故 选B4、在四面体ABCD中,面ABC及BCD都是边长为2的等边三角形,且ADa,M、N分别为棱AB、CD的中点,则在四面体表面上M与N的最短距离为 ( A )ABCDMNMMMMNAMBCDN 解:在四面体表面上,M到N的路线有四种: 经过棱AC,经过棱AD,经过棱BC,经过棱BD,取四种情况之最小者. 情形,沿ABCD展开如图,=MN连接MC,得:,从而 ,AD=,则AC,MCN=90+30=120,120=3a+a+2a=4a+MN=同理,对于、的情况同法可以求得

20、=MN2a情形的情况与情形相同. 选A5、已知三个三角形、 、的周长分别为,且,较小的两个三角形可以互不重叠地放入大三角形的内部,则的最大值是 ( D ) 解:设的周长是p,面积为S,的周长是p,面积为,的周长是,面积是,由已知条件得:,则(=k)于是,由基本不等式: 即:,以等腰直角三角形为例(如图):知等号能成立. 选D6、已知自然数n不是5的倍数,则5除时有 ( A ) 不能确定,都有可能发生解:因为n不是5的倍数,故n,或n(mod5) 1或4(mod5)所以0或0(mod5) 选A二、填空题(本题满分分,每小题分)7、设其中是不小于3的自然数,则形如的全体分数之和为 )解:把形如的数

21、如下分组:,其中第k组含有k个分数,第k个组的k个元素的和为:所以SBACDh8、在ABC中,已知三内角A、B、C成等差数列,若其对边分别为,并且等于AC边上的高h,则= .解:h=c-a=所以因为A、B、C成等差数列,所以B,AC所以解得:9.已知定义在实数集上的函数满足,则10、从集合中任取两个不相邻的数(这两个数可以相同)相乘,所有这样的积再求和等于_解:任取两个数相乘再求和得S=1320其中不符合条件的和为=285+45=330所求之和11.在直角坐标平面中一椭圆的两个焦点为且椭圆与纵轴相切,则椭圆短轴长为_解:求出关于纵轴的对称点。则12.设,且,则的大小关系为_解:设,易证而因=

22、故于是由于上式的两个不等号中的等号不能同时取到,故三、解答题(本题满分分,每小题分)3已知M是抛物线上的动弦AB上的点,O为坐标原点,OAOB,OMAB,求点M的轨迹方程.解:设AB与x轴交于C(点,A、B的坐标分别是,则即 ()又直线AB的方程是,将C坐标代入得:化简上式,并利用()得:x=2p,由圆的定义知点M的轨迹方程是若F(x)的反函数为F-1(x),证明方程F-1(x)=0有唯一解;并求出该唯一解设-lx1x2l,则x1-x20,2-x10,2-x20,(*)式第一项0又(l+x1)(l-x2)0,(l-x1)(l+x2)0,(l+x1)(1-x2)-(1-x1)(1+x2)= x1-x20(*)式第二项的真数大于零且小于1于是F(x1)-F(x2)0,F(x)在(-1,1)上是增函数&#

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论