《数学奥林匹克专题讲座》第15讲 离散.doc

第15讲 离散最值问题在国内外数学竞赛中，常出现一些在自然数范围内变化的量的最值问题，我们称之为离散最值问题。解决这类非常规问题，尚无统一的方法，对不同的题目要用不同的策略和方法，就具体的题目而言，大致可从以下几个方面着手：1.着眼于极端情形；2.分析推理确定最值；3.枚举比较确定最值；4.估计并构造。例1 一把钥匙只能开一把锁，现在有4把钥匙4把锁，但不知哪把钥匙开哪把锁，最少试多少次，就一定能使全部的钥匙和锁相匹配？解：开第1把锁，若不凑巧，试3把钥匙还没有成功，则第4把不用再试了，它一定能打开这把锁。同理，开第2把锁最多试2次，开第3把锁最多试1次，最后剩下的1把钥匙一定能打开剩下的第4把锁，而用不着再试。这样最多要试的次数为321=6（次）。说明：在“最凑巧”的情况下，只需试3次就可使全部的钥匙和锁相匹配。本题中要求满足任何情况，所以应从“最不凑巧”的情况考虑问题。例2 一个布袋中有红、黄、绿三种颜色的小球各10个，这些小球的大小均相同，红色小球上标有数字“4”，黄色小球上标有数字“5”，绿色小球上标有数字“6”。小明从袋中摸出8个球，它们的数字和是39，其中最多可能有多少个球是红色的？解：假设摸出的8个球全是红球，则数字之和为（48=）32，与实际的和39相差7，这是因为将摸出的黄球、绿球都当成是红球的缘故。用一个绿球换一个红球，数字和可增加（64=）2，用一个黄球换一个红球，数字和可增加（5-4=）1。为了使红球尽可能地多，应该多用绿球换红球，现在72=31，因此可用3个绿球换红球，再用一个黄球换红球，这样8个球的数字之和正好等于39。所以要使8个球的数字之和为39，其中最多可能有（8-3-1=）4个是红球。例3 红星小学的礼堂里共有座位24排，每排有30个座位，全校650个同学坐到礼堂里开会，至少有多少排座位上坐的学生人数同样多？解：从极端情形考虑，假设24排座位上坐的人数都不一样多，那么最多能坐假设只有2排座位上坐的学生人数同样多，那么，最多能坐假设只有3排座位上坐的学生人数同样多，那么，最多能坐而题中说全校共有学生650人，因此必定还有（650636=）14人要坐在这24排中的某些排座位上，所以其中至少有4排座位上坐的学生人数同样多。说明：（1）若问最多有多少排座位上坐的学生人数同样多，你会解吗？这个问题留给读者研究。（2）从极端情形入手，着眼于极端情形，是求解最值问题的有效手段。如例1中从最不凑巧的情形看，用n把钥匙开1把锁要开n次才能打开，例2从摸出的8个球全是红球这种极端情形入手，再进行逐步调整。解：本题实质上是确定n的最小值，利用被11整除的数的特征知：一个数能被11整除，当且仅当该数的偶位数字的和与奇位数字的和之差能被11整除。该数的偶位数字之和为18n2，奇位数字之和为10n5。两者之差为18n2-（10n5）=8n-3。要使（8n-3）为11的倍数，不难看出最小的n=10，故所求最小数为说明：本题采用分析、推理的方法来确定最值，这也是解离散最值问题的一种常用方法。EFG的最大值与最小值相差多少？解：由右式知，A=1，DG=3或13，由于A，D，G为不同数字，故DG3，因此 D+ G13；C+F=8或18，但 CF，故只有 CF=8，数，为使数字不重复，只有取E=7（B=2），F=5（C=3），G=9（D=4），E=2（B=7），F=3（C=5），G4（D=9），即当1234759-1759234=1234（234525）-（1234525）234（1234234）525=525000。例6 某公共汽车从起点开往终点站，中途共有13个停车站。如果这辆公共汽车从起点站开出，除终点站外，每一站上车的乘客中，正好各有一位乘客从这一站到以后的每一站，那么为了使每位乘客都有座位，这辆公共汽车至少应有多少个座位？解法1：只需求车上最多有多少人。依题意列表如下：由上表可见，车上最多有56人，这就是说至少应有56个座位。说明：本题问句出现了“至少”二字是就座位而言的，座位最少有多少，取决于什么时候车上人数最多，要保证乘客中每人都有座位，应准备的座位至少应当等于乘客最多时的人数。所以，我们不能只看表面现象，误认为有了“至少”就是求最小数，而应该把题意分析清楚后再作判断。解法2：因为车从某一站开出时，以前各站都有同样多的人数到以后各站（每站1人），这一人数也和本站上车的人数一样多，因此车开出时人数=（以前的站数+1）以后站数=站号（15-站号）。因此只要比较下列数的大小：114， 213， 312， 411， 510，69， 78， 87， 96， 105，114， 123， 132， 141。由这些数，得知78和87是最大值，也就是车上乘客最多时的人数是56人，所以它应有56个座位。说明：此题的两种解法都是采用的枚举法，枚举法是求解离散最值问题的基本方法。这种方法的大意是：将问题所涉及的对象一一列出，逐一比较从中找出最值；或者将与问题相关的各种情况逐一考察，最后归纳出需要的结论。例7 在10，9，8，7，6，5，4，3，2，1这10个数的每相邻两个数之间都添上一个加号或一个减号，组成一个算式。要求：（1）算式的结果等于37；（2）这个算式中的所有减数（前面添了减号的数）的乘积尽可能地大。那么，这些减数的最大乘积是多少？解：把10个数都添上加号，它们的和是55，如果把其中一个数的前面的加号换成减号，使这个数成为减数，那么和数将要减少这个数的2倍。因为55-3718，所以我们变成减数的这些数之和是182=9。对于大于2的数来说，两数之和总是比两数乘积小，为了使这些减数的乘积尽可能大，减数越多越好（不包括1）。9最多可拆成三数之和234=9，因此这些减数的最大乘积是23424，添上加、减号的算式是10 9 8 7 6 5- 4- 3- 2 137。例8 设a1，a2，a3，a4，a5，a6是1到9中任意6个不同的正整数，并且a1a2a3a4a5a6。试用这6个数分别组成2个三位数，使它们的乘积最大。分析与解：由于a1，a6具体大小不清楚，因此先取特殊数1，2，3，4，5，6这6个不同的数考虑。要使2个三位数的乘积最大，必须使这2个数的百位数最大，应分别是6，5；而十位数次大，应分别为4，3，个位数最小，应分别为2，1。因为当2个数之和一定时，这2个数之差越小，它们的乘积越大，所以这2个数是631和542。例9 8个互不相同的自然数的总和是56，如果去掉最大的数及最小的数，那么剩下的数的总和是44。问：剩下的数中，最小的数是多少？解：因为最大数与最小数的和是5644=12，所以最大数不会超过11。去掉最大和最小数后剩下的6个互不相同的自然数在210之间，且总和为44，这6个数只能是4，6，7，8，9，10。例10 采石场采出了200块花岗石料，其中有120块各重7吨，其余的每块各重9吨，每节火车车皮至多载重40吨，为了运出这批石料，至少需要多少节车皮？解：每节车皮所装石料不能超出5块，故车皮数不能少于2005=40（节），而40节车皮可按如下办法分装石料：每节装运3块7吨的和两块9吨的石料，故知40节可以满足要求。例11 用若干个形如图1的图形盖住一个尺寸为612的矩形（允许图形伸出矩形之外）。问：至少需要多少个形如图1的图形？并说明理由。解：将图1去掉1个小方格，可得图2，用2个图2可以盖住36的矩形，推知用8个图2可以盖住612的矩形，从而用8个图1也能盖住612的矩形。612的矩形有72个方格，而7个图1共有710=70（个）方格，7个图1盖不住612的矩形，所以至少需要8个。例12 把 1，2，3，12填在左下图的12个圆圈里，然后将任意两个相邻的数相加，得到一些和，要使这些和都不超过整数n，n至少是多少？为什么？并请你设计一种填法，满足你的结论。解：因为1+2312=78， 7821213，所以n13。又考虑到与12相邻的数最小是1和2，所以n至少是14。右上图是一种满足要求的填法。说明：“估计+构造”是解离散最值问题的一种常用方法，要求某个离散最值，先估计该量的上界或下界，然后构造出一个实例说明此上界或下界能够达到，这样便求出了这个量的最大值或最小值。练习15 1.一排有50个座位，其中有些座位已经有人，若新来一个人，他无论坐在何处，都有一个人与他相邻，则原来至少有多少人就座？最大值是多少？3.有一个正整数的平方，它的最后三位数字相同但不为零，试求满足上述条件的最小正整数。4.命题委员会为510年级准备数学奥林匹克试题，每个年级各7道题，而且都恰有4道题跟任何其它年级不同。试问，其中最多可以有多少道不同的试题（指各个年级加在一起）？5.如果10个互不相同的两位奇数之和等于898，那么这10个奇数中最小的一个是多少？6.某城市设立1999个车站，并打算设立若干条公共汽车线路。要求：（1）从任何一站上车，至多换一次车就可以到达城市的任一站；（2）每一个车站，至多是两条线路的公共站。问：这个城市最多可以开辟多少条公共汽车线路？7.23个不同的自然数的和是4845。问：这23个数的最大公约数可能达到的最大的值是多少？写出你的结论，并说明理由。8.两个偶数的倒数之和与两个奇数的倒数之和相等，这样的偶数对和奇数对要求是不同的偶数和奇数。问：满足这个条件的偶数对的两个偶数之和的最小值是多少？练习151.17人。解：只要两个人之间空的座位不多于2个，便可满足题设条件。503=162，所以原来至少有16+1=17（人）就座。之值最大，可知a-b=1，从而a+b之值要尽可能大，据此a=100，b=99，所3.1444。解：平方数末位只能为0，1，4，5，6，9。因为111，444，555，666，999均非平方数，而1000，1111也不是平方数，但1444=382，故满足题设条件的最小正整数是1444。4.33道。解：显然，当每道题至多为两个年级所公用时，题目的数量达到最多，此时不同的试题共有46+（36）2=33（道）。例如，每个年级的第47题均与其他年级不同，而第13题，5，6年级相同，7，8年级相同，9，10年级相同，此时恰有33道不同的试题。5.79。解：9个不同的最大的两位奇数99，97，95，93，91，89，87，85，83的和是819，898-819=79，所以10个奇数中最小的是79。6.63条。解：设这个城市设立了n条公共汽车线路。由（1）（2）可知，任何两条线路必有公共的车站，所以每条线路至少有（n-1）个车站。n条线路至少有n（n-1）个车站。由于每一个车站都有可能是两条线路的公共车站个车站，于是有满足上述不等式的最大整数是n=63。也就是说这个城市最多可以开辟63条公共汽车线路。7.17。解：设这23个彼此不同的自然数为a1，a2，a22，a23，并且它们的最大公约数是d，则a1=db1，a2=db2，a22=db22，a23=db23。依题意，有4845=a1+a2+a22+a23=d（b1+b2+b22+b23）。因为b1，b2，b22，b23也是彼此不等的自然数，所以b1+b2+b231+2+23=276。因为4845=d（b1+b2+b22+b23）276d，所以又