《数学奥林匹克专题座》离散.docVIP

第15讲 离散最值问题 　　在国内外数学竞赛中，常出现一些在自然数范围内变化的量的最值问题，我们称之为离散最值问题。解决这类非常规问题，尚无统一的方法，对不同的题目要用不同的策略和方法，就具体的题目而言，大致可从以下几个方面着手： 　　1.着眼于极端情形； 　　2.分析推理——确定最值； 　　3.枚举比较——确定最值； 　　4.估计并构造。 　　例1 一把钥匙只能开一把锁，现在有4把钥匙4把锁，但不知哪把钥匙开哪把锁，最少试多少次，就一定能使全部的钥匙和锁相匹配？ 　　解：开第1把锁，若不凑巧，试3把钥匙还没有成功，则第4把不用再试了，它一定能打开这把锁。同理，开第2把锁最多试2次，开第3把锁最多试1次，最后剩下的1把钥匙一定能打开剩下的第4把锁，而用不着再试。这样最多要试的次数为 　　3＋2＋1=6（次）。 　　说明：在“最凑巧”的情况下，只需试3次就可使全部的钥匙和锁相匹配。本题中要求满足任何情况，所以应从“最不凑巧”的情况考虑问题。 　　例2 一个布袋中有红、黄、绿三种颜色的小球各10个，这些小球的大小均相同，红色小球上标有数字“4”，黄色小球上标有数字“5”，绿色小球上标有数字“6”。小明从袋中摸出8个球，它们的数字和是39，其中最多可能有多少个球是红色的？ 　　解：假设摸出的8个球全是红球，则数字之和为（4×8=）32，与实际的和39相差7，这是因为将摸出的黄球、绿球都当成是红球的缘故。 　　用一个绿球换一个红球，数字和可增加（6－4=）2，用一个黄球换一个红球，数字和可增加（5-4=）1。为了使红球尽可能地多，应该多用绿球换红球，现在7÷2=3……1，因此可用3个绿球换红球，再用一个黄球换红球，这样8个球的数字之和正好等于39。所以要使8个球的数字之和为39，其中最多可能有（8-3-1=）4个是红球。 　　例3 红星小学的礼堂里共有座位24排，每排有30个座位，全校650个同学坐到礼堂里开会，至少有多少排座位上坐的学生人数同样多？ 　　解：从极端情形考虑，假设24排座位上坐的人数都不一样多，那么最多能坐 　　假设只有2排座位上坐的学生人数同样多，那么，最多能坐 　　假设只有3排座位上坐的学生人数同样多，那么，最多能坐 　　而题中说全校共有学生650人，因此必定还有（650－636=）14人要坐在这24排中的某些排座位上，所以其中至少有4排座位上坐的学生人数同样多。 　　说明：（1）若问最多有多少排座位上坐的学生人数同样多，你会解吗？这个问题留给读者研究。 　　（2）从极端情形入手，着眼于极端情形，是求解最值问题的有效手段。如例1中从最不凑巧的情形看，用n把钥匙开1把锁要开n次才能打开，例2从摸出的8个球全是红球这种极端情形入手，再进行逐步调整。 　　 　　解：本题实质上是确定n的最小值，利用被11整除的数的特征知：一个数能被11整除，当且仅当该数的偶位数字的和与奇位数字的和之差能被11整除。该数的偶位数字之和为18n＋2，奇位数字之和为10n＋5。两者之差为 　　18n＋2-（10n＋5）=8n-3。 　　要使（8n-3）为11的倍数，不难看出最小的n=10，故所求最小数为 　　 　　说明：本题采用分析、推理的方法来确定最值，这也是解离散最值问题的一种常用方法。 　　 ×EFG的最大值与最小值相差多少？ 　　 　　解：由右式知，A=1，D＋G=3或13，由于A，D，G为不同数字，故D＋G≠3，因此 D+ G＝13；C+F=8或18，但 C≠F，故只有 C＋F=8， 数，为使数字不重复，只有取E=7（B=2），F=5（C=3），G=9（D=4）， E=2（B=7），F=3（C=5），G＝4（D=9），即当 　　1234×759-1759×234 　　=1234×（234＋525）-（1234＋525）×234 　　＝（1234—234）×525=525000。 　　例6 某公共汽车从起点开往终点站，中途共有13个停车站。如果这辆公共汽车从起点站开出，除终点站外，每一站上车的乘客中，正好各有一位乘客从这一站到以后的每一站，那么为了使每位乘客都有座位，这辆公共汽车至少应有多少个座位？ 　　解法1：只需求车上最多有多少人。依题意列表如下： 　　 　　由上表可见，车上最多有56人，这就是说至少应有56个座位。 　　说明：本题问句出现了“至少”二字是就座位而言的，座位最少有多少，取决于什么时候车上人数最多，要保证乘客中每人都有座位，应准备的座位至少应当等于乘客最多时的人数。所以，我们不能只看表面现象，误认为有了“至少”就是求最小数，而应该把题意分析清楚后再作判断。 　　解法2：因为车从某一站开出时，以前各站都有同样多的人数到以后各站（每站1人），这一人数也和本站上车的人数一样多，因此 　　车开出时人数=（以前的