离散量的最值问题.doc

离散量的最值问题所谓离散量最值问题，即指自变量是整数，集合、子集、点、线，图等离散量，要求它们在满足某些约束条时，求目标函数的最大值或最小值问题。离散最值问题涉及的面非常广泛，也是近年来国内外数学竞赛中经常出现的热点问题。由于整数等自变量的离散性，通常关于求连续变量的最值问题的方法不再适用。所以解决这类非常规的离散最值问题，对于参赛的同学的聪明才智具有更大的挑战性。下面介绍解离散最值问题的几种主要方法。一、不等式法不等式法解离散最值问题包括两个方面：论证估值与构造实例。论证估值即是根据问题中的离散变量具有的性质建立不等式，然后通过对不等式的放缩来论证或者估计离散变量的最佳的上界或下界；构造实例即是找到一个实例以说明离散变量在约束条件下，目标函数可以达到这个最佳的上界或下界，于是这个上界或下界即是所求的最大值或是小值。例1 设，求的最大值 （2000年全国高中数学联赛试题）。解 ，有由均值不等式有，故 注意到上面价值不等式中等号成立的充要条件是，即，而。综上，的最大值为。例2 已知个正整数。且满足。若有，求的最大值。 解 首先估计的上界。注意到，否则，若，则有。 于是有，矛盾！若，而，则有矛盾！ 故。下面构造一个的实例。令，则有。综上，所求的最大值为。例3 某市有所中学，第所中学派出名学生到体育馆观看球赛。全部学生总数为，看台上每一横排有199个座位。要求同一学校的学生必须坐在同一横排。向体育馆最少要安排多少个横排才能保证全部学生都能坐下，（1990年全国高中数学联赛试题）。分析 首先利用条件初步估计最小横排数的上界13，即“随便坐，13排足够”；其次利用极端性原理考虑空位最小的原则，精确估计最小横排数的最佳上界12，即“巧安排，12排够用”；最后构造反例说明：11排一定坐不下，所以所求最小横排数为12。解 已知每个故每一横排至少可坐161人，否则不足161人将至少留下39个空位，从而尚可安排一具学校的学生坐下。于是只要有13排，至少可坐人，当然能坐下全部1990人，这说明，随便坐，13排正够。下面我们说明巧安排，12排就够用了。为了使横排数最少，应使各排的空位数尽可能少，所以应该依据空位最小的原则来进行安排。因为所学校的学生数是有限个数，故它们的不超过199的有限和只有有限个。记为其中最接近（1990）199的有限和则可将这个学校的学生安排在第1排就座。无疑，这样安排最充分有效地利用了第一排的座位。然后再在余下的中选取最接近199的限和，并将其中这些学校的学生安排在第2排。依此类推，一直到第10排，记第排的空位数为，显然有因为12排共有个座位，坐满1990个人，尚余个空位，而。故下面分两种情况讨论。（1）若。则余下听未入座的每个学校的学生数。如果余下的学校数，注意到，将他们全部安排在第11排即可即此的仅需安排11排便可使全部1990人入座。如果余下的学校数，则完全可以任取5个学校的学生坐在第11排，而且在少坐人，从而,这与的最小值矛盾。即这种情况是不会出现的。（2）若，则前10排空位总数。于是前10排所坐学生总数不小于，从而未入座的学生数不大于。由于每一横排至少坐161人，故再安排2排就可以使入座的学生坐下。即此仅需安排12排即可使全部1990人入座。最后，我们构造反例说明仅安排11排是不行的。设，其中有79个学校每校25人，有1个学校15人，共计人。因为除第1排可以坐人之外，其余10排每排至多坐人，所以11排至多坐人。这说明11排是不够全部学生入座的。综上，所求最小横排数为12。例4 平面上有个点，其中任意三点不共线，每两点间用线段相连，用红蓝两种颜色将每条线段染色。若对任何染色法，一定存在12个同色三角形，求的最小值。解 为估计的下号，我们引入异色角的概念。若一个角的两边不同角，则称这个角为异色三角形恰有两个异色角。个点可构成个三角形，由条件可知其中至少有12个同色三角形，于是至多有个异角三角形，从而至多有个异色角。这说明对于任何染色法，异色角总数若不超过，则必存在同色三角形。另一方面，设个点为 ，从任一点出发，可引条线段，设其中有条红线，条蓝线。于是以为顶点的异色角数为条，从而异色角总数为。由均值不等式故由上面分析可知，若的取值满足不等式，则必存在12个同色三角形。解此不等式得。下面举反例说明时，不存在12个同色三角形。当时，过每点的7条线均染三红四蓝，则异色角总数为个，于是异色三角形总数为个，从而同色三角形只有个。综上，所求的最小值为9。例5 8位歌手参加艺术节，准备为他们安排次演出，每次由其中4位登台表演，要求8位歌手中任意两位同时演出的次数都一样多。请设计一种方案，使得演出的次数最少（1996年中国冬令营试题）。分析 首先通过对于对歌手总共同时演出的次数进行两个方面的估算（也称“算两次”）得到的下界；然后构造一个实例，即设计一种演出方案，使可以达到这个下界，于是这个下界即是的最小值。解 设任意两位歌手都同时演出次。一方面，共有对歌手，每对歌手同时演出次，他们总共同时演出次。另一方面，每次演出有4人登台，从而每次演出有对歌手同时演出，由于共演次，所以他们总共同时演出。次。综合两方面有，即。由此知，故，于是。下面设计一个演出方案，说明是可行的。用1，2，8代表8位歌手，用表不一次演出:(1,2,3,4),(5,6,7,8),(1,4,5,8),(2,3,6,7)(1,2,5,6),(3,4,7,8),(1,3,5,7),(2,4,6,8)(1,2,7,8),(3,4,5,6),(2,3,5,8),(1,4,6,7)(1,3,6,8),(2,4,5,7).在上面14个括号内，由于每对数字恰出现在3个括号内，即任意两位歌手同台演出恰为3次，所以的最小值为14。例6 试求出具有如下性质的最小的正整数： 可以表示为2002个各位数字之和相等的正整数之和，又可以表示为2003个各位数字之和相等的正整数之和。 （2002年第28届俄罗斯数学奥林匹克试题）解 假设对正整数有所求的表达式由于的各位数字之和相同，所以它们被9除的余数相同，记该余数为。同理，被9除的余数相同，记为。于是，且，从而-=。注意到，且，故。若，则，由于均被9整除，故此为；若，则，于是与中至少有一个不小于5。故此为或。下面考虑的两种符合要求的分析：一方面，综上，的最小值为10010。二、调整法许多离散最值问题可以看作是涉及到有限多个元素的系统。系统的状态是有限多，因而值的状态。例7已知，且，求。因为这说明将最小数减少1，而将最大数增加1，和不变，但平方和增大。为此，我们每次调整都将减少1，将减少的1加到上，直到为止，这样调整的结果便得69个正整数的和为112不变，而平方和在调整前增大了。再将解冻，对调整，幻然是每次将减少1，将加上，直到为止。如此对一步一步地调整下去，直到将调整到。此时，因为，并且每调整一次，平方和就增大一次，所以的最大值为例8 155只鸟停在一圆周上，记为，如果,称与是相互可见的，求互相可见的鸟对的最小数（假定一个位置上可以同时有个鸟）。分析 欲求互相可见的鸟对的最小值。首先用调整法证明鸟在圆周的落脚点至多只有35处时，即一对鸟只有在同一处才互相可见时才是最佳状态；其次再用调整法证明任何两处的鸟数至多差1时才是最佳状态；最后计算最佳状态时的可见对的最小值。解 设鸟停在圆周的处，鸟停在圆周的处， 与可见。设为从可以看到而从处看不到的鸟的只数，为从处可以看到而从处看不到的鸟的只数，且设。如果将处的所有鸟调整到处，则对每只鸟都减少了个可见对而增加了个可见对，所以互相可见的对数减少时。经过如上调整，重复若干次调整，直到每两只鸟只有在同一位置时才互相可见，这时有鸟的位置最多有35处，于是问题化为在条件之下，求的最小值。其中每个 为非负整数，当时，约定。下面再对每处鸟的只数进行调整，不妨设，。若，则令，这样调整后的值不变，而由于所以要减少。继续调整，直到，然后再选择中的最大数与最小数如此调整，注意到，所以经过有限次调整，可以使所有为4或5。此时，可见对取最小值。最后，计算可见对时最小值。设有处停4只鸟，有处停5只鸟，于是有解得，所有可见对的最小值为。即圆周上取35个位置（相邻两点的劣弧大于），其中20个位置各停4只鸟，15个位置各停5只鸟，可见对可以达到最小值270对。 三、差分法 求离散变量函数的最值问题时常用到差分法，即通过考察正数的一阶差分的符号，以确定的单调区间，从而求其最值。例9 试求函数的最大值。解 当时，故下面只考虑取非负整数的情况。先计算一阶差分易知，当时，有，于是，从而，即而当时，有，于是，从而，即综上可知，的最大值为例10 试求函数的最大值。解 当时，因为所以一阶差分，即当时，因为所以有即，且.综上可知，的最大值为.练 习 题1设，是的子集且满足条件：当时，。试求中元素个数的最大值.2. 10人到书店买书，已知（1）每人都买了3种书；（2）任何两人所买的书中，都至少有一种相同。问购买人数最多的一种书最少有几个人购买？3个互不相同的正偶数和个互不相同的正奇数的总和为1987，试求的最大值。412个朋友每周聚餐一次，每周分成三组，每组4人，不同组坐不同的桌子，若要求这些朋友中任意两个人至少有一次同坐一张桌子，问至少需要多少周？5已知若当时，的值都能被9整除，求的最小值。6已知若干个正整数之和为1976，求其积的最大值。7设，求的最大值。 8设，求的最大值。练 习 题 答 案1 令，因为，必有，所以与这两个数中至少有一个不属于。从而应有又因为，恒有。另一方面。所以可构造 则满足条件，且综上，的最大值为1870。2设购买人数最多的一种书有个人购买。设是10人之一，已知买了3种书，且其余9人中每人所买的书中都至少有一种与相同，由抽屉原则知9人中至少有3人，加上共4人买了同一种书，故。 若，则的3种书均为4人购买。同理，其它9人的每种书也均有4人购买。所以10人所买书的总数应是4的倍数，即4|30，矛盾，所以。 下面构造例子说明可行。设为互不相同的书，10人买书情况如下：上述购书情况符合要求，故购买人数最多的一种书最少有5人购买。3设是互不相同的正偶数，是互不相同的正奇数，使得此时，于是有因而有由柯西不等式有注意到的整数，所以另一方面，当时。，且所以的最大值为221。4因为12人共有对，而每张桌有对，第一周有对同桌。第一周后的每一周，同桌4人来自第一周的3桌，故其中至少有两人第一周已经同桌，即每桌产生的新的同桌对至少有6-1=5对，共计15对。于是4周至多有同桌对所以不行。即可行。设12个人分别记为设计如下：周 次 1号桌 2号桌 3号桌 1 1 2 3 4 5 6 9 10 7 8 11 12 2 1 2 5 6 3 4 7 8 9 10 11 12 3 1 2 7 8 3 4 9 10 5 6 11 12 4 1 2 9 10 3 4 11 12 5 6 7 8 5 1 2 11 12