nbhkdz.com冰点文库

数学奥林匹克专题讲座 第15讲 离散最值问题

时间:2011-05-29

数学奥林匹克专题讲座 第 15 讲 离散最值问题
在国内外数学竞赛中,常出现一些在自然数范围内变化的量的最值问题,我们称 之为离散最值问题。解决这类非常规问题,尚无统一的方法,对不同的题目要用不同 的策略和方法,就具体的题目而言,大致可从以下几个方面着手: 1.着眼于极端情形; 2.分析推理——确定最值; 3.枚举比较——确定最值; 4.估计并构造。 现在有 4 把钥匙 4 把锁, 但不知哪把钥匙开哪把锁, 例 1 一把钥匙只能开一把锁, 最少试多少次,就一定能使全部的钥匙和锁相匹配? 解:开第 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 排座位上坐的人数都不一样多,那么最多能坐

1

假设只有 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,故所求最小数为

说明:本题采用分析、推理的方法来确定最值,这也是解离散最值问题的一种常 用方法。

2

×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 个座位。

3

说明:本题问句出现了“至少”二字是就座位而言的,座位最少有多少,取决于 什么时候车上人数最多,要保证乘客中每人都有座位,应准备的座位至少应当等于乘 客最多时的人数。所以,我们不能只看表面现象,误认为有了“至少”就是求最小数, 而应该把题意分析清楚后再作判断。 解法 2:因为车从某一站开出时,以前各站都有同样多的人数到以后各站(每站 1 人),这一人数也和本站上车的人数一样多,因此 车开出时人数=(以前的站数+1)×以后站数 =站号×(15-站号)。 因此只要比较下列数的大小: 1×14, 2×13, 3×12, 4×11, 5×10, 6×9, 7×8, 8×7, 9×6, 10×5, 11×4, 12×3, 13×2, 14×1。 由这些数,得知 7×8 和 8×7 是最大值,也就是车上乘客最多时的人数是 56 人, 所以它应有 56 个座位。 说明:此题的两种解法都是采用的枚举法,枚举法是求解离散最值问题的基本方 法。这种方法的大意是:将问题所涉及的对象一一列出,逐一比较从中找出最值;或 者将与问题相关的各种情况逐一考察,最后归纳出需要的结论。 例 7 在 10,9,8,7,6,5,4,3,2,1 这 10 个数的每相邻两个数之间都添上 一个加号或一个减号,组成一个算式。要求:(1)算式的结果等于 37;(2)这个算 式中的所有减数(前面添了减号的数)的乘积尽可能地大。那么,这些减数的最大乘 积是多少? 解:把 10 个数都添上加号,它们的和是 55,如果把其中一个数的前面的加号换 成减号,使这个数成为减数,那么和数将要减少这个数的 2 倍。 因为 55-37=18,所以我们变成减数的这些数之和是 18÷2=9。对于大于 2 的数 来说,两数之和总是比两数乘积小,为了使这些减数的乘积尽可能大,减数越多越好 (不包括 1)。9 最多可拆成三数之和 2+3+4=9,因此这些减数的最大乘积是 2×3 ×4=24,添上加、减号的算式是 10 + 9+ 8+ 7 + 6+ 5- 4- 3- 2 +1=37。 例 8 设 a1,a2,a3,a4,a5,a6 是 1 到 9 中任意 6 个不同的正整数,并且 a1<a2 <a3<a4<a5<a6。试用这 6 个数分别组成 2 个三位数,使它们的乘积最大。

4

分析与解:由于 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。问:剩下的数中,最小的数是多少? 解:因为最大数与最小数的和是 56-44=12,所以最大数不会超过 11。去掉最大 和最小数后剩下的 6 个互不相同的自然数在 2~10 之间,且总和为 44,这 6 个数只能 是 4,6,7,8,9,10。 例 10 采石场采出了 200 块花岗石料,其中有 120 块各重 7 吨,其余的每块各重 9 吨,每节火车车皮至多载重 40 吨,为了运出这批石料,至少需要多少节车皮? 解:每节车皮所装石料不能超出 5 块,故车皮数不能少于 200÷5=40(节),而 40 节车皮可按如下办法分装石料:每节装运 3 块 7 吨的和两块 9 吨的石料,故知 40 节可以满足要求。

例 11 用若干个形如图 1 的图形盖住一个尺寸为 6×12 的矩形(允许图形伸出矩 形之外)。问:至少需要多少个形如图 1 的图形?并说明理由。

解:将图 1 去掉 1 个小方格,可得图 2,用 2 个图 2 可以盖住 3×6 的矩形,推知 用 8 个图 2 可以盖住 6×12 的矩形,从而用 8 个图 1 也能盖住 6×12 的矩形。6×12 的矩形有 72 个方格,而 7 个图 1 共有 7×10=70(个)方格,7 个图 1 盖不住 6×12 的矩形,所以至少需要 8 个。 例 12 把 1,2,3,…,12 填在左下图的 12 个圆圈里,然后将任意两个相邻的 数相加,得到一些和,要使这些和都不超过整数 n,n 至少是多少?为什么?并请你 设计一种填法,满足你的结论。

5

解:因为 1+2+3+…+12=78, 78×2÷12=13,所以 n≥13。又考虑到与 12 相 邻的数最小是 1 和 2,所以 n 至少是 14。右上图是一种满足要求的填法。 说明:“估计+构造”是解离散最值问题的一种常用方法,要求某个离散最值, 先估计该量的上界或下界,然后构造出一个实例说明此上界或下界能够达到,这样便 求出了这个量的最大值或最小值。
练习 15

1.一排有 50 个座位,其中有些座位已经有人,若新来一个人,他无论坐在何处, 都有一个人与他相邻,则原来至少有多少人就座?

最大值是多少? 3.有一个正整数的平方,它的最后三位数字相同但不为零,试求满足上述条件的 最小正整数。 4.命题委员会为 5~10 年级准备数学奥林匹克试题,每个年级各 7 道题,而且都 恰有 4 道题跟任何其它年级不同。试问,其中最多可以有多少道不同的试题(指各个 年级加在一起)? 5.如果 10 个互不相同的两位奇数之和等于 898,那么这 10 个奇数中最小的一个 是多少? 6.某城市设立 1999 个车站,并打算设立若干条公共汽车线路。要求: (1)从任何一站上车,至多换一次车就可以到达城市的任一站; (2)每一个车站,至多是两条线路的公共站。 问:这个城市最多可以开辟多少条公共汽车线路?

6

7.23 个不同的自然数的和是 4845。问:这 23 个数的最大公约数可能达到的最大 的值是多少?写出你的结论,并说明理由。 8.两个偶数的倒数之和与两个奇数的倒数之和相等,这样的偶数对和奇数对要求 是不同的偶数和奇数。问:满足这个条件的偶数对的两个偶数之和的最小值是多少? 练习 15 1.17 人。 解:只要两个人之间空的座位不多于 2 个,便可满足题设条件。50÷3=16……2, 所以原来至少有 16+1=17(人)就座。

之值最大,可

从而 a+b 之值要尽可能大, 据此 a=100, b=99, 所 知 a-b=1, 3.1444。 解:平方数末位只能为 0,1,4,5,6,9。因为 111,444,555,666,999 均非 平方数,而 1000,1111 也不是平方数,但 1444=382,故满足题设条件的最小正整数 是 1444。 4.33 道。 解:显然,当每道题至多为两个年级所公用时,题目的数量达到最多,此时不同 的试题共有 4×6+(3×6)÷2=33(道)。 例如,每个年级的第 4~7 题均与其他年级不同,而第 1~3 题,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)个车站。 由于每一个车站都有可能是两条线路的公共车站

7

个车 站,于是有

满足上述不等式的最大整数是 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+…+b23≥1+2+…+23=276。 因为 4845=d(b1+b2+…+b22+b23)≥276×d,所以

又因为 4845=19×17×15,因此 d 的最大值可能是 17。 当 a1=17,a2=17×2,a3=17×3,…,a21=17×21,a22=17×22,a23=17×32 时, 得 a1+a2+…+a22+a23 =17×(1+2+…+22)+17×32 =17×253+17×32=17×285=4845。 而(a1,a2,…,a22,a23)=17。所以 d 的最大值等于 17。
8

8.16。 解:我们先证明这样的两个偶数之和必为 4 的倍数。因为两个奇数的倒数之和为

另一方面,两个偶数的倒数之和为

“偶+偶”是 8 的倍数。

不合条件; 当两偶数和为 16 时,有

9


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

数学奥林匹克专题讲座第15讲 离散最值问题 - 第 15 讲 离散最值问题 在国内外数学竞赛中, 常出现一些在自然数范围内变化的量的最值问 题,我们称之为...

2011年北京市数学竞赛辅导第15讲离散最值问题.doc

第15 讲 离散最值问题 在国内外数学竞赛中, 常出现一些在自然数范围内变化的...4.命题委员会为 5~10 年级准备数学奥林匹克试题,每个年级各 7 道题,而且都...

第十四讲 离散最值问题.doc

第十四讲 离散最值问题_学科竞赛_小学教育_教育专区。第 1 页共 7 页 第...离散数学讲义-第14讲(7... 84页 1下载券 数学奥林匹克专题讲座 第......

《数学奥林匹克专题讲座》第16讲 枚举问题.doc

数学奥林匹克专题讲座》第16讲 枚举问题 - 枚举、 第 16 讲 枚举、归纳

离散量的最值问题.doc

(2002 年第 28 届俄罗斯数学奥林匹克试题) 解 假设对正整数 n 有所求的...第15讲 离散最值问题 10页 2下载券 第八讲 离散最值与逻辑... 2页 2...

《数学奥林匹克专题讲座》第10讲 应用问题选讲.doc

数学奥林匹克专题讲座》第10讲 应用问题选讲 - 第 10 讲 应用问题选讲

数学奥林匹克专题讲座 第10讲 应用问题选讲new.doc

数学奥林匹克专题讲座第 10 讲 应用问题选讲我们...故当 x=y=12 时,x+y 有最小值,从而长方形...显然,x 要满足不等式 3≤x≤15,于是当 x=3 时...

数学奥林匹克题解E组合数学 E2计数和离散最值031-040)汇总.doc

数学奥林匹克题解E组合数学 E2计数和离散最值031-040)汇总_职高对口_职业教育...(3)=15.将等边三角形每边 数记为 f(n),求 f(n)表达式. n 等分,过各...

《数学奥林匹克专题讲座》第14讲 估计与估算.doc

数学奥林匹克专题讲座》第14讲 估计与估算_学科竞赛_小学教育_教育专区。第 ...说明:解答这类问题要特别注意:不能简单地根据最小值是 6 的 1 倍,最大值...

数学奥林匹克题解E组合数学 E2计数和离散最值071-080)汇总.doc

数学奥林匹克题解E组合数学 E2计数和离散最值071-080)汇总_职高对口_职业教育...【题说】 第十六届(1990 年)全俄数学奥林匹克九年级题 5. 【解】 称积分...

数学奥林匹克专题讲座 第01讲 数论的方法技巧(上).pdf

数学奥林匹克专题讲座 第1讲 数论的方法技巧(上) ...(ak+1)。 5.整数集的离散性:n与n+1之间不再...可能的情况有下面15种: ①1,6,10 ②1,7,9 ③...

《数学奥林匹克专题讲座》第01讲 数论汇总.doc

数学奥林匹克专题讲座》第01讲 数论汇总 - 第 1 讲 数论的方法技巧(上) 数论是研究整数性质的一个数学分支,它历史悠久,而且有着强大的生命力。数 论问题...

数学奥林匹克专题讲座 第12讲 染色和赋值.doc

数学奥林匹克专题讲座 第12讲 染色和赋值_初三数学_数学_初中教育_教育专区。数学奥林匹克专题讲座 第 12 讲 染色和赋值染色方法和赋值方法是解答数学竞赛问题的两...

最值问题解题思路奥数.doc

最值问题解题思路奥数_五年级数学_数学_小学教育_教育专区。介绍了小学奥数中最值问题的解题思路 马到成功奥数专题:离散最值引言:在国内外数学竞赛中,常出现一些在...

《数学奥林匹克专题讲座》第12讲 染色和赋值.doc

数学奥林匹克专题讲座》第12讲 染色和赋值_学科竞赛_小学教育_教育专区。第 12 讲 染色和赋值 染色方法和赋值方法是解答数学竞赛问题的两种常用的方法。 就其...

数学奥林匹克专题讲座 第13讲 抽屉原理.doc

数学奥林匹克专题讲座 第 13 讲 抽屉原理把 5 个...由于余数只能取 0,1,2,…,499 这 499 个值,...(100-86+1)+1,即 46=3×15+1,也就是说,把...

第八讲 离散最值与逻辑推理问题1.doc

第八讲 离散最值与逻辑推理问题1 - 第八讲 离散最值与逻辑推理问题 在数学竞赛中, 常会出现在自然数范围内变化的量的最值问题, 称之为离散最值问题。 解决...

数学奥林匹克专题讲座 第02讲 数论的方法技巧(下).pdf

数学奥林匹克专题讲座》第2讲 数论的方法技巧(下...因此,n的最大值为434。练习2 1.将两个自然数的...又因为 15=1+2+3+4+5≤a1+a2+a3+a4+a5 ≤...

《数学奥林匹克专题讲座》七.doc

(2009-01-31 12:37:41) 标签:杂谈 分类:他山之石 转《数学奥林匹克专题讲座》七 第 12 讲 染色和赋值 染色方法和赋值方法是解答数学竞赛问题的两种常用的...

《数学奥林匹克专题讲座》第05讲 有趣的数字.doc

数学奥林匹克专题讲座》第05讲 有趣的数字 - 第 5 讲 有趣的数字 数字问题一直是中小学数学竞赛中的热门问题, 解这类问题一般要用 到整数的性质及解整数...