數(shù)學(xué)奧林匹克專題講座 第15講 離散最值問(wèn)題

1、數(shù)學(xué)奧林匹克專題講座 第15講 離散最值問(wèn)題在國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中，常出現(xiàn)一些在自然數(shù)范圍內(nèi)變化的量的最值問(wèn)題，我們稱之為離散最值問(wèn)題。解決這類非常規(guī)問(wèn)題，尚無(wú)統(tǒng)一的方法，對(duì)不同的題目要用不同的策略和方法，就具體的題目而言，大致可從以下幾個(gè)方面著手：1.著眼于極端情形；2.分析推理確定最值；3.枚舉比較確定最值；4.估計(jì)并構(gòu)造。例1 一把鑰匙只能開(kāi)一把鎖，現(xiàn)在有4把鑰匙4把鎖，但不知哪把鑰匙開(kāi)哪把鎖，最少試多少次，就一定能使全部的鑰匙和鎖相匹配？解：開(kāi)第1把鎖，若不湊巧，試3把鑰匙還沒(méi)有成功，則第4把不用再試了，它一定能打開(kāi)這把鎖。同理，開(kāi)第2把鎖最多試2次，開(kāi)第3把鎖最多試1次，最后剩下的1把鑰

2、匙一定能打開(kāi)剩下的第4把鎖，而用不著再試。這樣最多要試的次數(shù)為321=6（次）。說(shuō)明：在“最湊巧”的情況下，只需試3次就可使全部的鑰匙和鎖相匹配。本題中要求滿足任何情況，所以應(yīng)從“最不湊巧”的情況考慮問(wèn)題。例2 一個(gè)布袋中有紅、黃、綠三種顏色的小球各10個(gè)，這些小球的大小均相同，紅色小球上標(biāo)有數(shù)字“4”，黃色小球上標(biāo)有數(shù)字“5”，綠色小球上標(biāo)有數(shù)字“6”。小明從袋中摸出8個(gè)球，它們的數(shù)字和是39，其中最多可能有多少個(gè)球是紅色的？解：假設(shè)摸出的8個(gè)球全是紅球，則數(shù)字之和為（4×8=）32，與實(shí)際的和39相差7，這是因?yàn)閷⒚龅狞S球、綠球都當(dāng)成是紅球的緣故。用一個(gè)綠球換一個(gè)紅球，數(shù)字和可

3、增加（64=）2，用一個(gè)黃球換一個(gè)紅球，數(shù)字和可增加（5-4=）1。為了使紅球盡可能地多，應(yīng)該多用綠球換紅球，現(xiàn)在7÷2=31，因此可用3個(gè)綠球換紅球，再用一個(gè)黃球換紅球，這樣8個(gè)球的數(shù)字之和正好等于39。所以要使8個(gè)球的數(shù)字之和為39，其中最多可能有（8-3-1=）4個(gè)是紅球。例3 紅星小學(xué)的禮堂里共有座位24排，每排有30個(gè)座位，全校650個(gè)同學(xué)坐到禮堂里開(kāi)會(huì)，至少有多少排座位上坐的學(xué)生人數(shù)同樣多？解：從極端情形考慮，假設(shè)24排座位上坐的人數(shù)都不一樣多，那么最多能坐假設(shè)只有2排座位上坐的學(xué)生人數(shù)同樣多，那么，最多能坐假設(shè)只有3排座位上坐的學(xué)生人數(shù)同樣多，那么，最多能坐而題中說(shuō)全校

4、共有學(xué)生650人，因此必定還有（650636=）14人要坐在這24排中的某些排座位上，所以其中至少有4排座位上坐的學(xué)生人數(shù)同樣多。說(shuō)明：（1）若問(wèn)最多有多少排座位上坐的學(xué)生人數(shù)同樣多，你會(huì)解嗎？這個(gè)問(wèn)題留給讀者研究。（2）從極端情形入手，著眼于極端情形，是求解最值問(wèn)題的有效手段。如例1中從最不湊巧的情形看，用n把鑰匙開(kāi)1把鎖要開(kāi)n次才能打開(kāi)，例2從摸出的8個(gè)球全是紅球這種極端情形入手，再進(jìn)行逐步調(diào)整。解：本題實(shí)質(zhì)上是確定n的最小值，利用被11整除的數(shù)的特征知：一個(gè)數(shù)能被11整除，當(dāng)且僅當(dāng)該數(shù)的偶位數(shù)字的和與奇位數(shù)字的和之差能被11整除。該數(shù)的偶位數(shù)字之和為18n2，奇位數(shù)字之和為10n5。兩者

5、之差為18n2-（10n5）=8n-3。要使（8n-3）為11的倍數(shù)，不難看出最小的n=10，故所求最小數(shù)為說(shuō)明：本題采用分析、推理的方法來(lái)確定最值，這也是解離散最值問(wèn)題的一種常用方法。×EFG的最大值與最小值相差多少？解：由右式知，A=1，DG=3或13，由于A，D，G為不同數(shù)字，故DG3，因此 D+ G13；C+F=8或18，但 CF，故只有 CF=8，數(shù)，為使數(shù)字不重復(fù)，只有取E=7（B=2），F(xiàn)=5（C=3），G=9（D=4），E=2（B=7），F(xiàn)=3（C=5），G4（D=9），即當(dāng)1234×759-1759×234=1234×（234525）-

6、（1234525）×234（1234234）×525=525000。例6 某公共汽車從起點(diǎn)開(kāi)往終點(diǎn)站，中途共有13個(gè)停車站。如果這輛公共汽車從起點(diǎn)站開(kāi)出，除終點(diǎn)站外，每一站上車的乘客中，正好各有一位乘客從這一站到以后的每一站，那么為了使每位乘客都有座位，這輛公共汽車至少應(yīng)有多少個(gè)座位？解法1：只需求車上最多有多少人。依題意列表如下：由上表可見(jiàn)，車上最多有56人，這就是說(shuō)至少應(yīng)有56個(gè)座位。說(shuō)明：本題問(wèn)句出現(xiàn)了“至少”二字是就座位而言的，座位最少有多少，取決于什么時(shí)候車上人數(shù)最多，要保證乘客中每人都有座位，應(yīng)準(zhǔn)備的座位至少應(yīng)當(dāng)?shù)扔诔丝妥疃鄷r(shí)的人數(shù)。所以，我們不能只看表面現(xiàn)象，

7、誤認(rèn)為有了“至少”就是求最小數(shù)，而應(yīng)該把題意分析清楚后再作判斷。解法2：因?yàn)檐噺哪骋徽鹃_(kāi)出時(shí)，以前各站都有同樣多的人數(shù)到以后各站（每站1人），這一人數(shù)也和本站上車的人數(shù)一樣多，因此車開(kāi)出時(shí)人數(shù)=（以前的站數(shù)+1）×以后站數(shù)=站號(hào)×（15-站號(hào)）。因此只要比較下列數(shù)的大?。?×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。由這些數(shù)，得知

8、7×8和8×7是最大值，也就是車上乘客最多時(shí)的人數(shù)是56人，所以它應(yīng)有56個(gè)座位。說(shuō)明：此題的兩種解法都是采用的枚舉法，枚舉法是求解離散最值問(wèn)題的基本方法。這種方法的大意是：將問(wèn)題所涉及的對(duì)象一一列出，逐一比較從中找出最值；或者將與問(wèn)題相關(guān)的各種情況逐一考察，最后歸納出需要的結(jié)論。例7 在10，9，8，7，6，5，4，3，2，1這10個(gè)數(shù)的每相鄰兩個(gè)數(shù)之間都添上一個(gè)加號(hào)或一個(gè)減號(hào)，組成一個(gè)算式。要求：（1）算式的結(jié)果等于37；（2）這個(gè)算式中的所有減數(shù)（前面添了減號(hào)的數(shù)）的乘積盡可能地大。那么，這些減數(shù)的最大乘積是多少？解：把10個(gè)數(shù)都添上加號(hào)，它們的和是55，如果把其中一

9、個(gè)數(shù)的前面的加號(hào)換成減號(hào)，使這個(gè)數(shù)成為減數(shù)，那么和數(shù)將要減少這個(gè)數(shù)的2倍。因?yàn)?5-3718，所以我們變成減數(shù)的這些數(shù)之和是18÷2=9。對(duì)于大于2的數(shù)來(lái)說(shuō)，兩數(shù)之和總是比兩數(shù)乘積小，為了使這些減數(shù)的乘積盡可能大，減數(shù)越多越好（不包括1）。9最多可拆成三數(shù)之和234=9，因此這些減數(shù)的最大乘積是2×3×424，添上加、減號(hào)的算式是10 9 8 7 6 5- 4- 3- 2 137。例8 設(shè)a1，a2，a3，a4，a5，a6是1到9中任意6個(gè)不同的正整數(shù)，并且a1a2a3a4a5a6。試用這6個(gè)數(shù)分別組成2個(gè)三位數(shù)，使它們的乘積最大。分析與解：由于a1，a6具體大小

10、不清楚，因此先取特殊數(shù)1，2，3，4，5，6這6個(gè)不同的數(shù)考慮。要使2個(gè)三位數(shù)的乘積最大，必須使這2個(gè)數(shù)的百位數(shù)最大，應(yīng)分別是6，5；而十位數(shù)次大，應(yīng)分別為4，3，個(gè)位數(shù)最小，應(yīng)分別為2，1。因?yàn)楫?dāng)2個(gè)數(shù)之和一定時(shí)，這2個(gè)數(shù)之差越小，它們的乘積越大，所以這2個(gè)數(shù)是631和542。例9 8個(gè)互不相同的自然數(shù)的總和是56，如果去掉最大的數(shù)及最小的數(shù)，那么剩下的數(shù)的總和是44。問(wèn)：剩下的數(shù)中，最小的數(shù)是多少？解：因?yàn)樽畲髷?shù)與最小數(shù)的和是5644=12，所以最大數(shù)不會(huì)超過(guò)11。去掉最大和最小數(shù)后剩下的6個(gè)互不相同的自然數(shù)在210之間，且總和為44，這6個(gè)數(shù)只能是4，6，7，8，9，10。例10 采石場(chǎng)

11、采出了200塊花崗石料，其中有120塊各重7噸，其余的每塊各重9噸，每節(jié)火車車皮至多載重40噸，為了運(yùn)出這批石料，至少需要多少節(jié)車皮？解：每節(jié)車皮所裝石料不能超出5塊，故車皮數(shù)不能少于200÷5=40（節(jié)），而40節(jié)車皮可按如下辦法分裝石料：每節(jié)裝運(yùn)3塊7噸的和兩塊9噸的石料，故知40節(jié)可以滿足要求。例11 用若干個(gè)形如圖1的圖形蓋住一個(gè)尺寸為6×12的矩形（允許圖形伸出矩形之外）。問(wèn)：至少需要多少個(gè)形如圖1的圖形？并說(shuō)明理由。解：將圖1去掉1個(gè)小方格，可得圖2，用2個(gè)圖2可以蓋住3×6的矩形，推知用8個(gè)圖2可以蓋住6×12的矩形，從而用8個(gè)圖1也能蓋住

12、6×12的矩形。6×12的矩形有72個(gè)方格，而7個(gè)圖1共有7×10=70（個(gè)）方格，7個(gè)圖1蓋不住6×12的矩形，所以至少需要8個(gè)。例12 把 1，2，3，12填在左下圖的12個(gè)圓圈里，然后將任意兩個(gè)相鄰的數(shù)相加，得到一些和，要使這些和都不超過(guò)整數(shù)n，n至少是多少？為什么？并請(qǐng)你設(shè)計(jì)一種填法，滿足你的結(jié)論。解：因?yàn)?+2312=78， 78×2÷1213，所以n13。又考慮到與12相鄰的數(shù)最小是1和2，所以n至少是14。右上圖是一種滿足要求的填法。說(shuō)明：“估計(jì)+構(gòu)造”是解離散最值問(wèn)題的一種常用方法，要求某個(gè)離散最值，先估計(jì)該量的上界或

13、下界，然后構(gòu)造出一個(gè)實(shí)例說(shuō)明此上界或下界能夠達(dá)到，這樣便求出了這個(gè)量的最大值或最小值。練習(xí)15 1.一排有50個(gè)座位，其中有些座位已經(jīng)有人，若新來(lái)一個(gè)人，他無(wú)論坐在何處，都有一個(gè)人與他相鄰，則原來(lái)至少有多少人就座？最大值是多少？3.有一個(gè)正整數(shù)的平方，它的最后三位數(shù)字相同但不為零，試求滿足上述條件的最小正整數(shù)。4.命題委員會(huì)為510年級(jí)準(zhǔn)備數(shù)學(xué)奧林匹克試題，每個(gè)年級(jí)各7道題，而且都恰有4道題跟任何其它年級(jí)不同。試問(wèn)，其中最多可以有多少道不同的試題（指各個(gè)年級(jí)加在一起）？5.如果10個(gè)互不相同的兩位奇數(shù)之和等于898，那么這10個(gè)奇數(shù)中最小的一個(gè)是多少？6.某城市設(shè)立1999個(gè)車站，并打算設(shè)立若

14、干條公共汽車線路。要求：（1）從任何一站上車，至多換一次車就可以到達(dá)城市的任一站；（2）每一個(gè)車站，至多是兩條線路的公共站。問(wèn)：這個(gè)城市最多可以開(kāi)辟多少條公共汽車線路？7.23個(gè)不同的自然數(shù)的和是4845。問(wèn)：這23個(gè)數(shù)的最大公約數(shù)可能達(dá)到的最大的值是多少？寫(xiě)出你的結(jié)論，并說(shuō)明理由。8.兩個(gè)偶數(shù)的倒數(shù)之和與兩個(gè)奇數(shù)的倒數(shù)之和相等，這樣的偶數(shù)對(duì)和奇數(shù)對(duì)要求是不同的偶數(shù)和奇數(shù)。問(wèn)：滿足這個(gè)條件的偶數(shù)對(duì)的兩個(gè)偶數(shù)之和的最小值是多少？練習(xí)151.17人。解：只要兩個(gè)人之間空的座位不多于2個(gè)，便可滿足題設(shè)條件。50÷3=162，所以原來(lái)至少有16+1=17（人）就座。之值最大，可知a-b=1，

15、從而a+b之值要盡可能大，據(jù)此a=100，b=99，所3.1444。解：平方數(shù)末位只能為0，1，4，5，6，9。因?yàn)?11，444，555，666，999均非平方數(shù)，而1000，1111也不是平方數(shù)，但1444=382，故滿足題設(shè)條件的最小正整數(shù)是1444。4.33道。解：顯然，當(dāng)每道題至多為兩個(gè)年級(jí)所公用時(shí)，題目的數(shù)量達(dá)到最多，此時(shí)不同的試題共有4×6+（3×6）÷2=33（道）。例如，每個(gè)年級(jí)的第47題均與其他年級(jí)不同，而第13題，5，6年級(jí)相同，7，8年級(jí)相同，9，10年級(jí)相同，此時(shí)恰有33道不同的試題。5.79。解：9個(gè)不同的最大的兩位奇數(shù)99，97，95

16、，93，91，89，87，85，83的和是819，898-819=79，所以10個(gè)奇數(shù)中最小的是79。6.63條。解：設(shè)這個(gè)城市設(shè)立了n條公共汽車線路。由（1）（2）可知，任何兩條線路必有公共的車站，所以每條線路至少有（n-1）個(gè)車站。n條線路至少有n（n-1）個(gè)車站。由于每一個(gè)車站都有可能是兩條線路的公共車站個(gè)車站，于是有滿足上述不等式的最大整數(shù)是n=63。也就是說(shuō)這個(gè)城市最多可以開(kāi)辟63條公共汽車線路。7.17。解：設(shè)這23個(gè)彼此不同的自然數(shù)為a1，a2，a22，a23，并且它們的最大公約數(shù)是d，則a1=db1，a2=db2，a22=db22，a23=db23。依題意，有4845=a1+a2+a22+a23=d（b1+b2+b22+b23）。因?yàn)閎1，b2，b22，b23也是彼此不等的自然數(shù)，所以b1+b2+b231+2+23=276。因?yàn)?845=d（b1+b2+b22+b23）276×d，所以又因?yàn)?845=19×17×15，因此d的最大值可能是17。當(dāng)a1=17，a2=17