离散量的最值问题

《离散量的最值问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散量的最值问题所谓离散量最值问题，即指自变量是整数，集合、子集、点、线，图等离散量，要求它们在满足某些约束条时，求目标函数的最大值或最小值问题。离散最值问题涉及的面非常广泛，也是近年来国内外数学竞赛中经常出现的热点问题。由于整数等自变量的离散性，通常关于求连续变量的最值问题的方法不再适用。所以解决这类非常规的离散最值问题，对于参赛的同学的聪明才智具有更大的挑战性。下面介绍解离散最值问题的几种主要方法。一、不等式法不等式法解离散最值问题包括两个方面：论证估值与构造实例。论证估值即是根据问题中的离散变量具有的性质建立不等式，然后通过对不等式的

2、放缩来论证或者估计离散变量的最佳的上界或下界；构造实例即是找到一个实例以说明离散变量在约束条件下，目标函数可以达到这个最佳的上界或下界，于是这个上界或下界即是所求的最大值或是小值。例1设，，求的最大值（2000年全国高中数学联赛试题）。解，有由均值不等式有，故注意到上面价值不等式中等号成立的充要条件是，即，而。综上，的最大值为。例2已知个正整数。且满足。若有，求的最大值。11解首先估计的上界。注意到，否则，，若，则有。于是有，矛盾！若，而，则有矛盾！故。下面构造一个的实例。令，，，则有。综上，所求的最大值为。例3某市有所中学，第所中学派出名

3、学生到体育馆观看球赛。全部学生总数为，看台上每一横排有199个座位。要求同一学校的学生必须坐在同一横排。向体育馆最少要安排多少个横排才能保证全部学生都能坐下，（1990年全国高中数学联赛试题）。分析首先利用条件初步估计最小横排数的上界13，即“随便坐，13排足够”；其次利用极端性原理考虑空位最小的原则，精确估计最小横排数的最佳上界12，即“巧安排，，12排够用”；最后构造反例说明：11排一定坐不下，所以所求最小横排数为12。解已知每个故每一横排至少可坐161人，否则不足161人将至少留下39个空位，从而尚可安排一具学校的学生坐下。于是只要有

4、13排，至少可坐人，当然能坐下全部1990人，这说明，随便坐，13排正够。下面我们说明巧安排，12排就够用了。为了使横排数最少，应使各排的空位数尽可能少，所以应该依据空位最小的原则来进行安排。因为所学校的学生数是有限个数，故它们的不超过199的有限和只有有限个。记为其中最接近（≤1990）199的有限和则可将这个学校的学生安排在第1排就座。无疑，这样安排最充分有效地利用了第一排的座位。然后再在余下的中选取最接近199的限和，并将其中这些学校的学生安排在第2排。依此类推，一直到第10排，记第排的空位数为，显然有11因为12排共有个座位，坐满1

5、990个人，尚余个空位，而。故下面分两种情况讨论。（1）若。则余下听未入座的每个学校的学生数。如果余下的学校数，注意到，将他们全部安排在第11排即可即此的仅需安排11排便可使全部1990人入座。如果余下的学校数，则完全可以任取5个学校的学生坐在第11排，而且在少坐人，从而,这与的最小值矛盾。即这种情况是不会出现的。（2）若，则前10排空位总数。于是前10排所坐学生总数不小于，从而未入座的学生数不大于。由于每一横排至少坐161人，故再安排2排就可以使入座的学生坐下。即此仅需安排12排即可使全部1990人入座。最后，我们构造反例说明仅安排11排

6、是不行的。设，其中有79个学校每校25人，有1个学校15人，共计人。因为除第1排可以坐人之外，其余10排每排至多坐人，所以11排至多坐人。这说明11排是不够全部学生入座的。综上，所求最小横排数为12。例4平面上有个点，其中任意三点不共线，每两点间用线段相连，用红蓝两种颜色将每条线段染色。若对任何染色法，一定存在12个同色三角形，求的最小值。解为估计的下号，我们引入异色角的概念。若一个角的两边不同角，则称这个角为异色三角形恰有两个异色角。个点可构成个三角形，由条件可知其中至少有12个同色三角形，于是至多有个异角三角形，从而至多有个异色角。这说

7、明对于任何染色法，异色角总数若不超过，则必存在同色三角形。另一方面，设个点为，从任一点出发，可引条线段，设其中有条红线，条蓝线。于是以为顶点的异色角数为条，从而异色角总数为。由均值不等式故11由上面分析可知，若的取值满足不等式，则必存在12个同色三角形。解此不等式得。下面举反例说明时，不存在12个同色三角形。当时，过每点的7条线均染三红四蓝，则异色角总数为个，于是异色三角形总数为个，从而同色三角形只有个。综上，所求的最小值为9。例58位歌手参加艺术节，准备为他们安排次演出，每次由其中4位登台表演，要求8位歌手中任意两位同时演出的次数都一样多

8、。请设计一种方案，使得演出的次数最少（1996年中国冬令营试题）。分析首先通过对于对歌手总共同时演出的次数进行两个方面的估算（也称“算两次”）得到的下界；然后构造一个实例，即设计