離散量的最值問(wèn)題

離散量的最值問(wèn)題所謂離散量最值問(wèn)題，即指自變量是整數(shù)，集合、子集、點(diǎn)、線，圖等離散量，要求它們?cè)跐M(mǎn)足某些約束條時(shí)，求目標(biāo)函數(shù)的最大值或最小值問(wèn)題。離散最值問(wèn)題涉及的面非常廣泛，也是近年來(lái)國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中經(jīng)常出現(xiàn)的熱點(diǎn)問(wèn)題。由于整數(shù)等自變量的離散性，通常關(guān)于求連續(xù)變量的最值問(wèn)題的方法不再適用。所以解決這類(lèi)非常規(guī)的離散最值問(wèn)題，對(duì)于參賽的同學(xué)的聰明才智具有更大的挑戰(zhàn)性。下面介紹解離散最值問(wèn)題的幾種主要方法。一、不等式法不等式法解離散最值問(wèn)題包括兩個(gè)方面：論證估值與構(gòu)造實(shí)例。論證估值即是根據(jù)問(wèn)題中的離散變量具有的性質(zhì)建立不等式，然后通過(guò)對(duì)不等式的放縮來(lái)論證或者估計(jì)離散變量的最佳的上界或下界；構(gòu)造實(shí)例即是找到一個(gè)實(shí)例以說(shuō)明離散變量在約束條件下，目標(biāo)函數(shù)可以達(dá)到這個(gè)最佳的上界或下界，于是這個(gè)上界或下界即是所求的最大值或是小值。123nN，求皿(TWn-的最大值12000年全國(guó)高中數(shù)學(xué)聯(lián)賽試題）。解nN123nN，求皿(TWn-的最大值12000年全國(guó)高中數(shù)學(xué)聯(lián)賽試題）。解nNf(n)，有Sn (n32)Sn1nn(n1)21n322(n1)n2)n234n6434164由均值不等式有6434n2,'n646434n2,'n64 34n50故細(xì)Fn15064注意到上面價(jià)值不等式中等號(hào)成立的充要條件是n ，即64注意到上面價(jià)值不等式中等號(hào)成立的充要條件是n ，即nn8，而f(8)150°綜上，f（n）的最大值為秒。50例2已知例2已知n個(gè)（n2）正整數(shù)X],X一,。且滿(mǎn)足x1xn。若有n求xn的最大值。n解首先估計(jì)X的上界。注意到Xn1 2,否則,，若X11 n11，則有X] x2Xn1 1。于是n1矛盾！XX1解首先估計(jì)X的上界。注意到Xn1 2,否則,，若X11 n11，則有X] x2Xn1 1。于是n1矛盾！XX1-4 2-XX12x nxnXX12X(n

n1)xxnnxx1x2n2，則有xx2x3nxx1x3nx2nxx112(n1)12(n 1)n22(n2n1)2n2矛盾！故xn。nT面構(gòu)造一個(gè)Xnn的實(shí)例。X2n1n，則有xx122n。綜上，所求X的最大值為n。n39,1in）。全部學(xué)生例3某市有n所中學(xué)，第i所中學(xué)派出39,1in）。全部學(xué)生n總數(shù)為c1990，看臺(tái)上每一橫排有199個(gè)座位。要求同一學(xué)校的學(xué)生必須坐在同一橫排。向體育館ii1最少要安排多少個(gè)橫排才能保證全部學(xué)生都能坐下，（1990年全國(guó)高中數(shù)學(xué)聯(lián)賽試題）。分析首先利用條件初步估計(jì)最小橫排數(shù)的上界13，即“隨便坐，13排足夠”；其次利用極端性原理考慮空位最小的原則，精確估計(jì)最小橫排數(shù)的最佳上界12，即“巧安排，，12排夠用”；最后構(gòu)造反例說(shuō)明：11排一定坐不下，所以所求最小橫排數(shù)為12。解已知每個(gè)C39,故每一橫排至少可坐161人，否則不足161人將至少留下39個(gè)空位，從而尚可i安排一具學(xué)校的學(xué)生坐下。于是只要有13排，至少可坐161132093人，當(dāng)然能坐下全部1990人，這說(shuō)明，隨便坐，13排正夠。下面我們說(shuō)明巧安排，12排就夠用了。為了使橫排數(shù)最少，應(yīng)使各排的空位數(shù)盡可能少，所以應(yīng)該依據(jù)空位最小的原則來(lái)進(jìn)行安排。因?yàn)榭谒鶎W(xué)校的學(xué)生數(shù)叩c2,c是有限個(gè)數(shù)，故它們的不超過(guò)199的有限和只有有限個(gè)。記12nC1c 乞?yàn)槠渲凶罱咏ǎ?990）199的有限和則可將這k個(gè)學(xué)校的學(xué)生安排在第1排就座。無(wú)i1i2 ik疑，這樣安排最充分有效地利用了第一排的座位。然后再在余下的c中選取最接近199的限和，并將其中這些學(xué)校的學(xué)生安排在第2排。依此類(lèi)推，一1直到第10排，記第i排的空位數(shù)為X.1i10），顯然有

因?yàn)?2排共有1991239812xxx因?yàn)?2排共有1991239812xxx12102388個(gè)座位，坐滿(mǎn)1990個(gè)人，尚余23881990398個(gè)空位，而33。故下面分兩種情況討論％。若xi033。則余下聽(tīng)未入座的每個(gè)學(xué)校的學(xué)生數(shù)Cj34。如果余下的學(xué)校數(shù)4,注意到394156199，將他們?nèi)堪才旁诘?1排即可即此的僅需安排11排便可使全部1990人入座。如果余下的學(xué)校數(shù)5,則完全可以任取5個(gè)學(xué)校的學(xué)生坐在第11排,而且在少坐345170人,從而x11 29x10,這與％的最小值矛盾。即這種情況是不會(huì)出現(xiàn)的。若x10 32，則前10排空位總數(shù)10x10x10x10x10320。于是前10排所坐學(xué)生總數(shù)不小于199103201670，從而未入座的學(xué)生數(shù)不大于19901670320。由于每一橫排至少坐161人，故再安排2排就可以使入座的學(xué)生坐下。即此僅需安排12排即可使全部1990人入座。最后，我們構(gòu)造反例說(shuō)明僅安排11排是不行的。設(shè)n80,其中有79個(gè)學(xué)校每校25人，有1個(gè)學(xué)校15人，共計(jì)257915 1990人。因?yàn)槌?排可以坐25715190人之外，其余10排每排至多坐257175人，所以11排至多坐190175101940人。這說(shuō)明11排是不夠全部學(xué)生入座的。綜上，所求最小橫排數(shù)為12。例4平面上有n個(gè)點(diǎn)，其中任意三點(diǎn)不共線，每?jī)牲c(diǎn)間用線段相連，用紅藍(lán)兩種顏色將每條線段染色。若對(duì)任何染色法，一定存在12個(gè)同色三角形，求n的最小值。解為估計(jì)n的下號(hào)，我們引入異色角的概念。若一個(gè)角的兩邊不同角，則稱(chēng)這個(gè)角為異色三角形恰有兩個(gè)異色角。n個(gè)點(diǎn)可構(gòu)成C3個(gè)三角形，由條件可知其中至少有12個(gè)同色三角形，于是至多有C3 12個(gè)異角nn三角形，從而至多有2(c3 12)個(gè)異色角。這說(shuō)明對(duì)于任何染色法，異色角總數(shù)若不超過(guò)2(c3 12)，nn則必存在同色三角形。另一方面，設(shè)n個(gè)點(diǎn)為A.(i12n)，從任一點(diǎn)A.出發(fā)，可引n1條線段，設(shè)其中有r條紅線，i in1n1r條藍(lán)線。于是以A.為頂點(diǎn)的異色角數(shù)為r(ni i i1r)條，從而異色角總數(shù)nri(n1r)。由i i ii1均值不等式r(n1r(n1r)

ii(罟)1)1)r(n1r)iii1由上面分析可知，若n的取值滿(mǎn)足不等式n(」)2 2@ 12)2n則必存在12個(gè)同色三角形。解此不等式得n9。T面舉反例說(shuō)明n8時(shí)，不存在12個(gè)同色三角形。當(dāng)n8時(shí)，過(guò)每點(diǎn)的7條線均染三紅四藍(lán)，則48個(gè)，從而同色三角形只有異色角總數(shù)為8 (34) 96個(gè)，于是異色三角形總數(shù)為￡96c3485648848個(gè)，從而同色三角形只有8綜上，所求n的最小值為9。例58位歌手參加藝術(shù)節(jié)，準(zhǔn)備為他們安排m次演出，每次由其中4位登臺(tái)表演，要求8位歌手中

任意兩位同時(shí)演出的次數(shù)都一樣多。請(qǐng)?jiān)O(shè)計(jì)一種方案，使得演出的次數(shù)山最少(1996年中國(guó)冬令營(yíng)試題)。分析首先通過(guò)對(duì)于c2對(duì)歌手總共同時(shí)演出的次數(shù)進(jìn)行兩個(gè)方面的估算(也稱(chēng)“算兩次”得到m的8下界；然后構(gòu)造一個(gè)實(shí)例，即設(shè)計(jì)一種演出方案，使m可以達(dá)到這個(gè)下界，于是這個(gè)下界即是m的最小值。解設(shè)任意兩位歌手都同時(shí)演出r次。一方面，共有c2對(duì)歌手，每對(duì)歌手同時(shí)演出r次，他們總共同8時(shí)演出rc2次。8另一方面，每次演出有4人登臺(tái)，從而每次演出有c2對(duì)歌手同時(shí)演出，由于共演山次，所以他們總4共同時(shí)演出。mc2次。4綜合兩方面有rc2 mc2，即14r3m。由此知3|r，故r3，于是m14。84下面設(shè)計(jì)一個(gè)演出方案，說(shuō)明m 14(r3)是可行的。用1，2,…，8代表8位歌手，用(a,b,c,d)表不一次演出:(1,2,3,4),(5,6,7,8),(1,4,5,8),(2,3,6,7)(1,2,5,6),(3,4,7,8),(1,3,5,7),(2,4,6,8),(3,4,5,6),(2,3,5,8),(1,4,6,7),(2,4,5,7).在上面14個(gè)括號(hào)內(nèi)，由于每對(duì)數(shù)字恰出現(xiàn)在3個(gè)括號(hào)內(nèi)，即任意兩位歌手同臺(tái)演出恰為3次，所以m的最小值為14。例6試求出具有如下性質(zhì)的最小的正整數(shù)n:n可以表示為2002個(gè)各位數(shù)字之和相等的正整數(shù)之

和，又可以表示為2003個(gè)各位數(shù)字之和相等的正整數(shù)之和。(2002年第28屆俄羅斯數(shù)學(xué)奧林匹克試題)naaabbb2002 1 2 2003解假設(shè)對(duì)正整數(shù)nnaaabbb2002 1 2 2003由于aa,a 的各位數(shù)字之和相同，所以它們被9除的余數(shù)相同，記該余數(shù)為r(0r8)。122002同理，bb ,b 被9除的余數(shù)相同，記為s(0s8)o1 2 2003于是，9|n2002r且9|n2003s，從而9|(n2002r)-(n2003s)=2003(rs)4005r。注意到9|4005，且(9,2003) 1，故9|(rs)。若rs0,則rs0,由于b,b,,b均被9整除，故此為n92003；1 2 2003若rs0，則rs9，于是r與s中至少有一個(gè)不小于5。故此為n52003或n52002。下面考慮5200210010的兩種符合要求的分析：一方面，1001055 5(2002個(gè)5)另一方面,10010420022002144 42002(2002個(gè)4與1個(gè)2002)綜上，口的最小值為10010。二、調(diào)整法許多離散最值問(wèn)題可以看作是涉及到有限多個(gè)元素的系統(tǒng)。系統(tǒng)的狀態(tài)是有限多，因而值的狀態(tài)。X692。因?yàn)門(mén)OC\o"1-5"\h\z例7已知廿2 X69 N，且X1 X2 X69 112，求X12 X2X692。因?yàn)?x1)2(x 1)2x2x222(xx)x2x21 69 1 69 69 1 1 69這說(shuō)明將最小數(shù)^減少1，而將最大數(shù)X增加1，和不變，但平方和增大。為此，我們每次調(diào)整都將’減1 69 1少1，將減少的1加到X上，直到X1為止，這樣調(diào)整的結(jié)果便得69個(gè)正整數(shù)的和為112不變，而平69 1方和在調(diào)整前增大了。再將x2解凍，對(duì)x2調(diào)整，幻然是每次將x2減少1，將x加上，直到X” 1為止。2 2 69 2如此對(duì)x,x,,x—步一步地調(diào)整下去，直到將(x,x,,x,x)調(diào)整到1,1,,1,44)。4 66 1 2 68 69此時(shí)，因?yàn)?1 144 6844112，并且每調(diào)整—次，平方和就增大—次，所以x2x2x2的最大值為1 2 6912 12 12 442 681936 2004例8 155只鳥(niǎo)停在一圓周C上，記為P1i155)，如果pp10,稱(chēng)P與p.是相互可見(jiàn)的,i ij ij求互相可見(jiàn)的鳥(niǎo)對(duì)的最小數(shù)(假定一個(gè)位置上可以同時(shí)有n個(gè)鳥(niǎo))。分析欲求互相可見(jiàn)的鳥(niǎo)對(duì)的最小值。首先用調(diào)整法證明鳥(niǎo)在圓周C的落腳點(diǎn)至多只有35處時(shí)，即

一對(duì)鳥(niǎo)只有在同一處才互相可見(jiàn)時(shí)才是最佳狀態(tài)；其次再用調(diào)整法證明任何兩處的鳥(niǎo)數(shù)至多差1時(shí)才是最佳狀態(tài)；最后計(jì)算最佳狀態(tài)時(shí)的可見(jiàn)對(duì)的最小值。解設(shè)鳥(niǎo)p.停在圓周C的A處，鳥(niǎo)p.停在圓周C的B處，(AB)P.與P.可見(jiàn)。設(shè)k為從B可ijij以看到而從A處看不到的鳥(niǎo)的只數(shù)，l為從A處可以看到而從B處看不到的鳥(niǎo)的只數(shù)，且設(shè)k1。如果將B處的所有鳥(niǎo)調(diào)整到A處，則對(duì)B每只鳥(niǎo)都減少了k個(gè)可見(jiàn)對(duì)而增加了1個(gè)可見(jiàn)對(duì)，所以互相可見(jiàn)的對(duì)數(shù)減少kl時(shí)。經(jīng)過(guò)如上調(diào)整，重復(fù)若干次調(diào)整，直到每?jī)芍圾B(niǎo)只有在同一位置時(shí)才互相可見(jiàn),這時(shí)有鳥(niǎo)的位置最多有35處，于是問(wèn)題化為在條件xxx1551235之下，求c2x35的最小值。其中每個(gè)x. 1i35)為非負(fù)整數(shù)，當(dāng)x.i下面再對(duì)每處鳥(niǎo)的只數(shù)進(jìn)行調(diào)整，不妨設(shè)X]min1.352時(shí)，約定c2XimaXXi，X20c2x35的最小值。其中每個(gè)x. 1i35)為非負(fù)整數(shù)，當(dāng)x.i下面再對(duì)每處鳥(niǎo)的只數(shù)進(jìn)行調(diào)整，不妨設(shè)X]min1.352時(shí)，約定c2XimaXXi，X20。xi。1i35若x22，則令x2'35X11，這樣調(diào)整后i1x的值不變，i而由于c2

x12c2c1x'x'12x(x1)2x(x1)(x1)x—22112(x1)(x0,2)x211所35以Ci1要減少。繼續(xù)調(diào)整，直到x21，然后再選擇Xi(1ii35)中的最大數(shù)與最小數(shù)如此調(diào)整，注意到4最后，155 5,所以經(jīng)過(guò)有限次調(diào)整，計(jì)算可見(jiàn)對(duì)時(shí)最小值。設(shè)有m處停4只鳥(niǎo)，有n處停5只鳥(niǎo)，于是有可以使所有X.為4或5。此時(shí)，可見(jiàn)對(duì)取最小值。imn35,4m5n155.解得m20，n15，所有可見(jiàn)對(duì)的最小值為20c215c2270。45即圓周上取35個(gè)位置(相鄰兩點(diǎn)的劣弧大于10)，其中20個(gè)位置各停4只鳥(niǎo)，15個(gè)位置各停5只鳥(niǎo)可見(jiàn)對(duì)可以達(dá)到最小值270對(duì)。三、差分法求離散變量函數(shù)f(n)(nZ)的最值問(wèn)題時(shí)常用到差分法，即通過(guò)考察正數(shù)的一階差分f(n)f(n1)f(n)的符號(hào)，以確定f(n)的單調(diào)區(qū)間，從而求其最值。

例9試求函數(shù)f(n)1n例9試求函數(shù)f(n)1n32n2(nZ)0時(shí)，0時(shí)，f(n)2綜上可知，2綜上可知，f(n)的最大值為f6)19f(n)f(n1)f(n)1(n1)1n(n23n31)、易知，當(dāng)032(n1)232n2(332nn2)(32n2n23n310，于是f(n)0，從而f(n1)f(n)，即f(5)f(4)f(1)f(0) 0.而當(dāng)n5時(shí)，有n23n310，于是f(0)0，從而f(n)f(n1)，即0,故下面只考慮n取非負(fù)整數(shù)的情況。先計(jì)解當(dāng)n算一階差分f(5)f(6)f(7)n4時(shí)，有例10試求函數(shù)f(n)1966nf(n)1966n(nN)n!的最大值。解當(dāng)1n18時(shí)，因?yàn)?9(n1)!19n119n!19nn!，66n1(n1)!66n166n66nn!n!所以一階差分f(n)f(n1)f(n)0,即f(19)f(18)f(1)當(dāng)n19時(shí)，因?yàn)?n1)!19(n1)!19n119n!19nn!，66n1(n1)!66n166n66nn!n!所以一階差分f(n)f(n1)f(n)0,即f(19)f(18)f(1)當(dāng)n19時(shí)，因?yàn)?n1)!f(n)19n166n1(n1)(19n66n)66n(66n1)19n(n119)0,19n640,n65所以有f(n)f(n1)f(n)0,0,n64即f(65)f(64)f(19),且f(65)f(66)f(67)綜上可知，f(n)綜上可知，f(n)的最大值為f(65)1965 666565!__練習(xí)題設(shè)M 1,2, ,1995,A是M的子集且滿(mǎn)足條件：當(dāng)xA時(shí)，15xA。試求A中元素個(gè)數(shù)的最大值.10人到書(shū)店買(mǎi)書(shū)，已知(1)每人都買(mǎi)了3種書(shū)；(2)任何兩人所買(mǎi)的書(shū)中，都至少有一種相同。問(wèn)購(gòu)買(mǎi)人數(shù)最多的一種書(shū)最少有幾個(gè)人購(gòu)買(mǎi)？m個(gè)互不相同的正偶數(shù)和n個(gè)互不相同的正奇數(shù)的總和為1987，試求3m4n的最大值。12個(gè)朋友每周聚餐一次，每周分成三組，每組4人，不同組坐不同的桌子，若要求這些朋友中任意兩個(gè)人至少有一次同坐一張桌子，問(wèn)至少需要多少周？已知a 1,a3,a(n3)a(n2)a.若當(dāng)mn時(shí)，a的值都能被9整除，求n1 2 n2 n1 n m的最小值。已知若干個(gè)正整數(shù)之和為1976，求其積的最大值。設(shè)nN,1n100，求f(n)n(100n)(100n1)的最大值。1000n8?設(shè)nN,求f(n)—的最大值。n!練習(xí)題答案1.令A(yù)1,2, ,8，A9,10, ,133，2A3 134,135, ,1995，因?yàn)閤A?，必有15xA^所以x與15x這兩個(gè)數(shù)中至少有一個(gè)不屬于A。從而應(yīng)有TOC\o"1-5"\h\z|A||M||A|1995125 1870.2又因?yàn)閤A，恒有15xA(i1,2,3)。另一方面xA,15xA。所以可構(gòu)造AAA,i i 1 3 1 3則A滿(mǎn)足條件，且|A||A1||A3|81862 1870.綜上，1A的最大值為1870。2?設(shè)購(gòu)買(mǎi)人數(shù)最多的一種書(shū)有x個(gè)人購(gòu)買(mǎi)。設(shè)A是10人之一，已知A買(mǎi)了3種書(shū)，且其余9人中每人所買(mǎi)的書(shū)中都至少有一種與A相同，由抽屜原則知9人中至少有3人，加上A共4人買(mǎi)了同一種書(shū)，故x4。若x4,則A的3種書(shū)均為4人購(gòu)買(mǎi)。同理，其它9人的每種書(shū)也均有4人購(gòu)買(mǎi)。所以10人所買(mǎi)書(shū)的總數(shù)應(yīng)是4的倍數(shù)，即4130,矛盾，所以x5。

下面構(gòu)造例子說(shuō)明X5可行。設(shè)a為互不相同的書(shū)，10人買(mǎi)書(shū)情況如下ia,a,a,a,a,a,a,a,a,123126234(a,a,a),(a,a,a),a,a,a,1 4 16145245(a,a,a),135(a,a,a),256(a,a,a),356a,a,a.346上述購(gòu)書(shū)情況符合要求，故購(gòu)買(mǎi)人數(shù)最多的一種書(shū)最少有5人購(gòu)買(mǎi)3?設(shè)a,a,12,a是互不相同的正偶數(shù)，b,b..,bn2是互不相同的正奇數(shù)，使得b1987nmaa1212abbm1此時(shí)，aaa242mm(m1),12mbbb13(2n1)n2.12n于是有m2mn21987.因而有121m n2198724由柯西不等式有14n<32 42i 1213m—'m n25,1987-2■ 724注意到3m4n的整數(shù)，所以3m4n221.另一方面，當(dāng)m 21,n35時(shí)°m2mn219811987，且3m4n221.所以3m4n的最大值為221。4?因?yàn)?2人共有c266對(duì)，而每張桌有c26對(duì)，第一周有3618對(duì)同桌。第一周后的每12 4一周，同桌4人來(lái)自第一周的3桌，故其中至少有兩人第一周已經(jīng)同桌，即每桌產(chǎn)生的新的同桌對(duì)至少有6-1=5對(duì)，共計(jì)15對(duì)。于是4周至多有同桌對(duì)181515156366.所以n4不行。即n