組合最值與操縱問題

組合最值與操作問題.知識與方法在數(shù)學(xué)競賽中，經(jīng)常有一些與組合問題相關(guān)的整最值問題，簡稱組合最值。所謂組合最值，就是指以整數(shù)、集合、點(diǎn)、線、圓等離散對象為背景，求它們滿足某些約束條件的極大值或極小值。這類問題的解法與一般函數(shù)（連續(xù)變量）極值的解法有很大的差異。對于這類非常規(guī)的極值問題，要針對具體問題，認(rèn)真分析，細(xì)心觀察，選用靈活的策略與方法。通常可以從論證與構(gòu)造兩方面予以考慮。先論證或求得該變量的上界或下界，然后構(gòu)造一個實(shí)例說明此上界或下界可以達(dá)到，這樣便求得了該組合量的極大值或極小值。在論證或求解組合量的上界或下界時(shí)，通常要對組合量做出估計(jì)，在估計(jì)的過程中，構(gòu)造法、分類討論法、數(shù)學(xué)歸納法、反證法、極端原理、抽屜原理等起著重要的作用。在數(shù)學(xué)競賽中，還有一類操作問題。這類問題是指在一定的規(guī)則下，對給定的對象進(jìn)行調(diào)整，探求被調(diào)整對象的初始狀態(tài)或終止?fàn)顟B(tài)及其變化規(guī)律。.范例選講例1.m個互不相同的正偶數(shù)和n個互不相同的正奇數(shù)的總和為1987，對于所有這樣的m與n，問3m+4n的最大值是多少？請證明你的結(jié)論。（1987年第二屆全國數(shù)學(xué)冬令營試題）思路分析：先根據(jù)題設(shè)條件求得 3m+4n的一個上界，然后舉例說明此上界可以達(dá)到，從而得到 3m+4n的最大值。解：設(shè)a1,a2,?,am是互不相同的正偶數(shù)，b1,b2,?,bn是互不相同的正奇數(shù)，使得a1+a2+?+am+b1+b2+?+bn=1987（1）這時(shí)分別有：a1+a2+?+am≥2+4+?+2m=m(m+1)（2）b1+b2+?+bn≥1+3+?+(2n-1)=n2(3)由①,②,③得m2+m+n≤1987,因而有（m+1）2+n2≤1987124④由④及柯西不等式，得3（m+1）+4n≤3242.(m1)2n2519871,224由于3m+4n為整數(shù)，所以3m+4n221,⑤另一方面，當(dāng)m=27,n=35時(shí)，m2+m+n2=1981<1987,且3m+4n=221。故3m+4n的最大值為221。評注：在論證過程中用到了柯西不等式與一般二元一次不定方程的求解方法。例2．設(shè)空間中有2n(n≥2)個點(diǎn)，其中任何四點(diǎn)都不共面。將它們之間任意連接N條線段，這些線段都至少構(gòu)成一個三角形，求N的最小值。思路分析：通過構(gòu)造實(shí)例，說明 N≥ n2+1，進(jìn)而證明當(dāng) N=n2+1時(shí)，若在2n點(diǎn)間連有N條線段，則這些線段至少構(gòu)成一個三角形。其證明過程可用數(shù)學(xué)歸納法或反證法或極端原理，在證明過程中要精打細(xì)算。解法一：將2n個已知點(diǎn)均分為 S和T兩組：S={A，A，?，A}，T={B，B，?B}。1 2 n 1 2 n現(xiàn)將每對點(diǎn)Ai和Bj之間都連結(jié)一條線段 AiBj，而同組的任何兩點(diǎn)之間均不連線，則共有 n2條線段。這時(shí)，2n個已知點(diǎn)中的任何三點(diǎn)中至少有兩點(diǎn)屬于同一組，二者之間沒有連線。因而這 n2條線段不能構(gòu)成任何三角形。這意味著 N的最小值必大于 n2。下面我們用數(shù)學(xué)歸納法來證明：若在 2n個已知點(diǎn)間連有 n2+1條線段，則這些線段至少構(gòu)成一個三角形。當(dāng)n=2時(shí)，n2+1=5，即四點(diǎn)間有五條線段。顯然，這五條線段恰構(gòu)成兩個三角形。設(shè)當(dāng)n=k（k≥2）時(shí)命題成立，當(dāng)n=k+1時(shí)，任取一條線段AB。若從A，B兩點(diǎn)向其余2K點(diǎn)引出的線段條數(shù)之和不小于2k+1，則必定存在一點(diǎn)C，它與A，B兩點(diǎn)間都有連線，從而△ABC即為所求。若從 A，B兩點(diǎn)引出的線段條數(shù)之和不超過 2K，則當(dāng)把A，B兩點(diǎn)除去后，其余的2K點(diǎn)之間至少還有K2+1條線段。于是由歸納假設(shè)知它們至少構(gòu)成一個三角形，這就完成了歸納證明。綜上可知，所求 N的最小值為n2+1。解法二。構(gòu)造例子同解法一，可知所求的 N的最小值不小于n2+1。由于2n個點(diǎn)間連有n2+1條線段，平均每點(diǎn)引出 n條線段還多，故可猜想必定有一條線段的兩個端點(diǎn)引出的線段數(shù)之和不小于2n+1，讓我們用反證法來證明這一點(diǎn)。設(shè)從A1，A2，?，A2n引出的線段條數(shù)分別為 a1，a2，?，a2n且對于任一線段AiAj都有ai+aj≤2n。于是，所有線段的兩個端點(diǎn)所引出的線段條數(shù)之和的總數(shù)不超過 2n（n2+1）。但在此計(jì)數(shù)中，Ai點(diǎn)恰被計(jì)算了ai次，故有2nai2≤2n（n2+1）。 （1）i12n另一方面，顯然有ai=2（n2+1）。由柯西不等式有i12n2n（ai）2≤2n（ai2），i1i12n≥1×4（n2+1）2＞2n（n2+1）（2）ai2i12n（2）與（1）矛盾。從而證明了必有一條線段，從它的兩個端點(diǎn)引出的線段數(shù)之和不小于 2n+1。不妨設(shè)A1A2是一條這樣的線段，從而又有Ak（k≥3），使線段A1Ak，A2Ak都存在，于是△A1A2Ak即為所求。解法三 構(gòu)造例子同解法一，可知所求的 N的最小值不小于n2+1。下面我們用極端原理來證明，當(dāng) N=n2+1時(shí)，這些線段至少構(gòu)成一個三角形。從而所求的 N的最小值即為n2+1。設(shè)2n個已知點(diǎn)間連有 n2+1條線段，且這些線段不構(gòu)成任何三角形，設(shè)A是2n點(diǎn)中引出線段條數(shù)最多的一個點(diǎn)，共引出 k條線段：ABj，j=1，2，?，k。于是{B1，?，Bk}之中任何兩點(diǎn)間都沒有連線，否則必構(gòu)成三角形。因而，從任一 Bj引出的線段條數(shù)不超過 2n-k。除了A，B1，?，Bk之外還有2n-k-1點(diǎn)，其中任何一點(diǎn)引出的線段條數(shù)當(dāng)然不超過 k。于是得到n2+1≤1［k+k(2n-k)+(2n-k-1)k ］=k(2n-k)≤n2,矛盾，這就完成了2全部證明。評注：本題用了三種方法求解，都是先通過例子確定出 N的一個下界，然后用不同的方法證明這個下界是可以達(dá)到的，進(jìn)而求出 N的最小值。解法一用到數(shù)學(xué)歸納法，解法二運(yùn)用了反證法與柯西不等式，解法三則是運(yùn)用了極端原理。例3．集合A的元素都是整數(shù)，其中最小的是 1，最大的是100。除1以外，每一個元素都等于集合 A的兩個數(shù)（可以相同）的和。求集合A的元素個數(shù)的最小值。思路分析：先構(gòu)造一個合乎條件的集合 A，說明A的元素個數(shù)的最小值不可能比 9大，再進(jìn)一步說明 A的元素個數(shù)的最小值就是9。解：構(gòu)造一個元素個數(shù)盡可能少的集合使它滿足條件，如：{1，2，3，5，10，20，25，50，100}，則集合A的元素個數(shù)的最小值不大于9。若{1，2，x1，x2，x3，x4，x5，100}也滿足條件，則x1≤4，x2≤8，x3≤16，x4≤32，x5≤64。但x4+x5=96﹤100，∴x5=50，x3+x4=48﹤50，∴x4=25x2+x3=24﹤25，∴x3=25，與x3是整數(shù)矛盾。2故A的元素個數(shù)的最小值是 9。評注：先構(gòu)造的例子說明集合 A的元素個數(shù)的最小值小于或等于9，后論證A的元素個數(shù)不可能小于 9，這里運(yùn)用了反證法。例4．平面上給定n個點(diǎn)A1，A2，?，An（n≥3），任意三點(diǎn)不共線。由其中K個點(diǎn)對確定K條直線（即過K個點(diǎn)對中的每一點(diǎn)對作一條直線），使這K條直線不相交成三個頂點(diǎn)都是給定點(diǎn)的三角形，求K的最大值。思路分析：先對 n個點(diǎn)中的點(diǎn)對A1，A2進(jìn)行分析，然后再對其余n-2個點(diǎn)中的點(diǎn)對 A3，A4分析，逐步類推，對 K的上界進(jìn)行估計(jì)，然后通過實(shí)例說明 K的上界可以達(dá)到，進(jìn)而求得 K的最大值。解：設(shè)過點(diǎn)對A1，A2的直線為L，則A1，A2不能同時(shí)與其余 n-2個點(diǎn)中的任意一點(diǎn)連結(jié)，即過 A1或A2的直線至多有 n-1條（包括L）。同理，對A3，A4，?An這n-2個點(diǎn)而言，過A3或A4的直線至多有n-3條，??。所以K≤（n-1）+（n-3）+?=(n1)(n3)...n2,若為n偶數(shù)；14(n1)(n3)...n212,若為n奇數(shù)。4另一方面，我們可以把 n個點(diǎn)分成兩組：n為偶數(shù)時(shí)，每組各個點(diǎn)；n為奇數(shù)時(shí)，一組n1個點(diǎn)，一組n1個點(diǎn)。把第一組的每點(diǎn)2 2 2與第二組的每點(diǎn)連結(jié)成 n2或n2 1 條直線，這些直線不相交成三個頂4 4點(diǎn)都是給定點(diǎn)的三角形。所以，當(dāng)n為偶數(shù)時(shí)，k的最大值是n24

當(dāng)n為奇數(shù)時(shí)，k的最大值是n2 1。4評注：本題在對 K進(jìn)行估計(jì)時(shí)，要對 n分奇數(shù)，偶數(shù)進(jìn)行討論。例5空間中有1989個點(diǎn)，其中任何三點(diǎn)都不共線。把它們分成點(diǎn)數(shù)各不相同的30組，在任何三個不同的組中各取一點(diǎn)為頂點(diǎn)作三角形。試問要使這種三角形的總數(shù)最大，各組的點(diǎn)數(shù)應(yīng)為多少？（1989年全國中學(xué)生數(shù)學(xué)冬令營試題）思路分析：先把 1989個以知點(diǎn)分成個數(shù)分別為 n1，n2，?，n30的30組，其頂點(diǎn)在三個不同組的三角形總數(shù)可表示為S=ninjnk.，然后通過逐步調(diào)整法求S的最大值。1i j k n解：設(shè)1989個已知點(diǎn)分成30組，各組的點(diǎn)數(shù)分別為n1，n2，?，n30.因此，頂點(diǎn)在不同組的三角形的總數(shù)為S=ninjnk.1ijkn30于是，本題即是問在ni1989且n1，n2，?，n30互不相同的條i1件下，S在何時(shí)取得最大值。由于把1989個點(diǎn)分成30組只有有限種不同的分法，故必有一種分法使S達(dá)到最大值。設(shè)n1<n2<?<n30為使S達(dá)到最大值的各組的點(diǎn)數(shù)。（1）對于i=1,2,?,29，均有ni+1-ni≤2。若不然，設(shè)有i0使30ni0+1-ni0≥3，不妨設(shè)i0=1這時(shí)我們改寫S=n1n2nk+（n1+n2）k3njnk+ninjnk。3jk303ijk30令n11=n1+1，n12=n2-1，則n11<n12<n3，n11+n12=n1+n2，n11 n12= n1 n2 + n2- n1-1> n1 n2。所以當(dāng)用n11 ，n12代替n1，n2時(shí)，將使

S變大，矛盾。（2）使

ni+1

-ni=2的

i

值至多一個。若有

1≤io<j

o≤29，使nIo+1-nIo=2，njo+1-n

jo=2，則當(dāng)用

n1io=nio+1，n1jo1=njo+1-1

代替nio，njo+1時(shí)，將使S變大，這不可能。（3）若30組的點(diǎn)數(shù)從小到大每相鄰兩組都差 1，設(shè)30組的點(diǎn)數(shù)依次為K-14，K-13，?，K，K+1，?，K+15，則有K-14）+（K-13）+?+K+（K+1）+?+（K+15）=30K+15這時(shí)點(diǎn)的總數(shù)為 5的倍數(shù)，不可能是 1989。故知n1<n2<?<n30中，相鄰兩數(shù)之差恰有一個為 2而其余的全為1。（4）設(shè)nj=mj1,j1,2,,io,mj,jio1,,30.其中1≤io≤29。于是有io1)+30j)=1989，(mj(mj1yio130m-io=1524，由此解得m=51，io=6。所以當(dāng)S取得最大值時(shí)，30組點(diǎn)數(shù)依次為51，52，?，56，58，59，?，81。評注：本題運(yùn)用逐步調(diào)整的方法，得到了使 S取最大值的必要條件和充分條件，其間運(yùn)用了反證法。例6．某市有n所中學(xué)，第i所中學(xué)派出Ci名學(xué)生到體育館觀看球賽（1≤Ci≤39，i=1，2，?，n），全部學(xué)生總數(shù)為nCi=1990?？磁_上每一橫排有 199個座位。要求同一學(xué)校的學(xué)生必i1須坐在同一橫排。問體育館最少要安排多少橫排才能保證全部學(xué)生都能坐下？（1990年全國高中數(shù)學(xué)聯(lián)賽二試）思路分析：利用 1≤Ci≤39，對每排至少可坐的學(xué)生人數(shù)或每排至多可留出的空位數(shù)進(jìn)行分析，確定出至少需要的橫排數(shù)。解：由于1≤Ci≤39，故每一橫排至少可坐 161人，于是只要有13排，至少可坐161×13=2093人，當(dāng)然能坐下全部學(xué)生1990人。下面我們來看12排座位能否安排下全部學(xué)生。注意，這時(shí)共有199×12=2388個座位，坐了1990人后，還有398個座位。因此，如果每排的空位數(shù)都不超過 33個，便可安排下全部學(xué)生。將所有學(xué)校學(xué)生從多到少重新編號，于是有C1≥C2≥C3≥?≥Cn。這樣存在非負(fù)整數(shù) m，使Cm≥34而Cm+1≤33。（若m=0，則意味著所有 Ci都不超過33）。設(shè)m=5p+r（0≤r﹤5）。將前5p個學(xué)校的學(xué)生安排在前 p排就坐，每排5個學(xué)校，每排至少坐 170人，空位至多 29個。接下去按次序使其余學(xué)校的學(xué)生就坐，每排都是坐到不能全部坐下下一學(xué)校的學(xué)生為止，則每排的空位都不會超過32個，直到第11排為止。這11排空位不超過32×11=352個，所以至少已坐了1837人，全部中學(xué)生中至多還有1990-1837=153人沒坐下，當(dāng)然可將他們安排在第12排就坐?？梢?，只要有12排座位，即可使全部學(xué)生按要求就坐。最后，讓我們來看，只有 11排座位情形如何？這時(shí)，只有 199個空位，要想安排下全部學(xué)生，每排空位平均不能達(dá)到 19個?，F(xiàn)設(shè)n=80，前79所學(xué)校各有25人，最后一個學(xué)校有 15人，則25×79+15=1990。除了一排可以安排 25×7＋15=190人就坐之外，其余10排至多安排175人，故11排至多安排190＋175×10=1940人就坐。這個例子說明只有 11排座位是不夠的。因此，為了安排下1990名學(xué)生，最少需要 12排座位。評注：為了求得橫排數(shù)的最小值，先進(jìn)行估計(jì)，說明 12個橫排可以達(dá)到要求，在論證過程中，以數(shù)字 33作為分界線，精確計(jì)算，達(dá)到了目的。然后通過構(gòu)造實(shí)例說明 11個安排不夠。例7．設(shè)S={1，2，?，10}，A1，A2，?，Ak是S的子集，滿足條件：（1）｜Ai｜=5（i=1，2，?，k）；（2）｜Ai∩Aj｜≤2（1≤i<j≤k）。求K的最大值。（1994年國家集訓(xùn)隊(duì)試題）思路分析：應(yīng)當(dāng)根據(jù)子集滿足的條件推導(dǎo)出一個K的上界。作如下試探：令

A1={1，2，3，4，5},

各子集間至多有

2個公共元，令A(yù)2={1

，2，6，7，8}，此時(shí)，若

{1，2}

A3，則必有｜A1∩A3｜≥3或｜A2∩A3｜≥3矛盾。由此得到第一個猜想：

A1，A2，?

Ak中至多有兩個集合包含同一個

2元子集。令A(yù)={1，3，6，9，10}，此時(shí)，若3

1∈A，則此時(shí)4

A1

，A，A中除23

1外均至多還有一個元素同時(shí)屬于 A4，｜A4｜≤4，矛盾。由此得到第二個猜想：S中每一個元素至多屬于 A1，A2，?，Ak中的3個集合。此時(shí)可求得

K的一個上界。解：（1）對

S的任意一個

2元子集{a，b}

S，A1

，A2，?Ak中至多有兩個集合包含

{a，b}。否則，設(shè)有

A1

{a，b}，A2

{a，b}，A3 {a，b}，則由于｜Ai∩Aj｜≤2（1≤i<j≤k），所以Ai-{a，b}兩兩不交（

i=1

，2，3），上述

Ai-{a

，b}表示差集：

A-B={x｜x∈A且

xB}。但｜

Ai-{a

，b}｜=3

（i=1

，2，3），于是｜S｜≥3×3＋

2=11，矛盾。2）對S的任意一個元素a，A1，A2，?Ak至多有三個集合包含{a}。設(shè)已有A1{a}，A2{a}，A3{a}，若｜Ai∩Aj｜=1（1≤i<j≤3），則｜A1∪A2∪A3｜=3×4＋1=13，矛盾。設(shè)b≠a，且a，b∈A1∩A2，則｜A1∪ A2｜=8，根據(jù)（1），b A3且｜A3∩A1｜≤2，｜A3∩A2｜≤2，所以A3中至多還有2個元素不屬于A1∪

A2，即

A1

A2

A3。同理，若還有

A4

{a}

，那么

A1

A2

A4，從而｜

A3∩A4｜≥3，矛盾。故對任意

a∈S，a

至多屬于

A1

，A2，?

Ak中

3個子集，所以S中每個元素至多在｜A1｜ +｜A2｜+? +｜Ak｜中作了3重計(jì)數(shù)，故｜A1｜+｜A2｜+?+｜Ak｜≤3｜S｜=30，所以K≤6。按照上述思路，可構(gòu)造出符合條件的 6個子集：{1，2，3，4，5}，{1，2，6，7，8}，{1，3，6，9，10}{2，4，7，9，10}，{3，5，7，8，10}，{4，5，6，8，9}故K的最大值為6評注：從探求必要條件入手，再驗(yàn)證其充分性，這種從必要到充分的思想方法也是數(shù)學(xué)競賽中一種常用的思想方法。例8．設(shè)S={1,2,3,?,280}，求最小的正整數(shù)n，使得S的每個有n個元素的子集都含有5個兩兩互素的數(shù)。思路分析：先通過構(gòu)造S的子集，得到n的下界；然后再通過構(gòu)造S的另一類子集，又說明n的上述下界可以達(dá)到，從而確定出n的最小值。解：設(shè)A1={S中被2整除的數(shù)}，A2={S中被3整除的數(shù)}，A3={S中被5整除的數(shù)}，A={S中被7整除的數(shù)}，并記A=A∪A∪A∪A，則利用容斥原4 1 2 3 4理計(jì)算得|A|=216由于在A中任取5個數(shù)必有兩個數(shù)在同一個 Ai中(i=1,2,3,4) ，且不互素，故 n≥217.另一方面，設(shè)B1={1和S中的一切素?cái)?shù)}，B2={22,32,52,72,112,132},B3={2×131,3×89,5×53,7×37,11×23,13×19}B4={2×127,3×83,5×47,7×31,11×19,13×17}B5={2×113,3×79,5×43,7×29,11×17}B6={2×109,3×73,5×41,7×23,11×13}記B=B∪B∪?∪B,則|B|=88，于是S-B含有192個元素。在1 2 6S中任取217個數(shù)，由于217-192=25，故至少有25個元素在B中，且25=4×6+1，故這25個元素中必有5個數(shù)屬于同一Bi,顯然他們兩兩互素。故n的最小值為217。評注：根據(jù)問題的特點(diǎn)，構(gòu)造恰當(dāng)?shù)淖蛹迨峭瓿杀绢}解答的關(guān)鍵。例9如圖，在7×8的長方形棋盤的每個小方格的中心點(diǎn)各放一個棋子。如果兩個棋子所在的小方格共邊或共頂點(diǎn)，那么稱這兩個棋子相連?，F(xiàn)從這56個棋子中取出一些，使得棋盤上剩下的棋子，沒有五個在一條直線（橫、豎、斜方向）上依次相連。問最少取出多少個棋子才可能滿足要求？并說明理由。（2007年高中數(shù)學(xué)聯(lián)賽加試試題）解：最少要取出 11個棋子，才可能滿足要求。其原因如下：如果一個方格在第 i行第j列，則記這個方格為(i，j)。第一步證明若任取 10個棋子，則余下的棋子必有一個五子連珠，即五個棋子在一條直線（橫、豎、斜方向）上依次相連。用反證法。假設(shè)可取出 10個棋子，使余下的棋子沒有一個五子連珠。如圖 1，在每一行的前五格中必須各取出一個棋子，后三列的前五格中也必須各取出一個棋子。這樣，10個被取出的棋子不會分布在右下角的陰影部分。同理，由對稱性，也不會分布在其他角上的陰影部分。第1、2行必在每行取出一個，且只能分布在(1，4)、(1，5)、(2，4)、(2，5)這些方格。同理(6，4)、(6，5)、(7，4)、(7，5)這些方格上至少要取出2個棋子。在第1、2、3列，每列至少要取出一個棋子，分布在(3，1)、(3，2)、(3，3)、(4，1)、(4，2)、(4，3)、(5，1)、(5，2)、(5，3)所在區(qū)域，同理(3，6)、(3，7)、(3，8)、(4，6)、(4，7)、(4，8)、(5，6)、(5，7)、(5，8)所在區(qū)域內(nèi)至少取出3個棋子。這樣，在這些區(qū)域內(nèi)至少已取出了10個棋子。因此，在中心陰影區(qū)域內(nèi)不能取出棋子。由于①、②、③、④這4個棋子至多被取出2個，從而，從斜的方向看必有五子連珠了。矛盾。圖1 圖2第二步構(gòu)造一種取法，共取走 11個棋子，余下的棋子沒有五子連珠。如圖2，只要取出有標(biāo)號位置的棋子，則余下的棋子不可能五子連珠。綜上所述，最少要取出 11個棋子，才可能使得余下的棋子沒有五子連珠。例10、對一個正整數(shù)操作如下：去掉其個位數(shù)，再加上個位數(shù)的5倍（如：39?3+9′5=48），問71998能否經(jīng)過這樣有限次操作變?yōu)?9987？解：設(shè)此操作將an變?yōu)閍n+1，un為an的個位數(shù)，則an=10tn+un，tn為非負(fù)整數(shù)。所以an+1=tn+5uno50tn+5un=5(10tn+un)=5an(mod7)，而71998o0(mod7)，19987o3(mod7)。所以不可能由71998變?yōu)?9987。例11．如圖所示，圓形的水池被分割為2n（n≥5）個“格子”。我們把有公共隔墻（公共邊或公共?。┑摹案褡印狈Q為相鄰的，從而每個“格子”都有三個鄰格。水池中一共跳入了4n+1只青蛙，青蛙難于安靜共處，只要某個“格子”中有不少于3只青蛙，那么遲早一定會有其中3只分別同時(shí)跳往三個不同鄰格。證明：只要經(jīng)過一段時(shí)間之后，青蛙便會在水池中大致分布均勻。所謂大致分布均勻，就是任取其中一個“格子”，或者它里面有青蛙，或者它的3個鄰格里都有青蛙。證明：我們把一個格子中出現(xiàn)一次三只青蛙同時(shí)分別跳向三個鄰格的事件稱為該格子發(fā)生一次 “爆發(fā)”。而把一個格子或者是它里面有青蛙，或者是它的三個相鄰的格子里面都有青蛙，稱為該格子處于“平衡狀態(tài)”。容易看出，一個格子只要一旦有青蛙跳入，那么它就一直處于“平衡狀態(tài)”。事實(shí)上，只要不“爆發(fā)”，那么該格子中的青蛙不會動，它當(dāng)然處于“平衡狀態(tài)”；而如果發(fā)生“爆發(fā)”，那么它的三個鄰格中就都有青蛙，并且只要三個鄰格都不“爆發(fā)”，那么它就一直處于“平衡狀態(tài)”；而不論哪個鄰格發(fā)生“爆發(fā)”，都會有青蛙跳到它里面，它里面就一定有青蛙，所以它也一直處于平衡狀態(tài)。這樣一來，為證明題中斷言，我們就只要證明：任何一個格子都遲早會有青蛙跳入。任取一個格子，把它稱為格A，把它所在的扇形稱為1號扇形，把該扇形中的另一個格子稱為格B，如圖。我們證明格A遲早會有青蛙跳入。ABBA3n3n2121按順時(shí)針方向依次將其余扇形接著編號為 2至n號。首先證明1號扇形遲早會有青蛙跳入。假設(shè) 1號扇形中永無青蛙到來，那么就不會有青蛙越過 1號扇形與n號扇形之間的隔墻。我們來考察青蛙所在的扇形編號的平方和。由于沒有青蛙進(jìn)入 1號扇形（尤其沒有青蛙越過1號扇形與n號扇形之間的隔墻），所以只能是有 3只青蛙由某個k(3≤k≤n-1)號扇形分別跳入 k-1，k和k+1號扇形各一只，因此平方和的變化量為(k-1)2+k2+(k+1)2-3k2=2即增加2。一方面，由于青蛙的跳動不會停止（因?yàn)榭傆幸粋€格子里有不少于3只青蛙），所以平方和的增加趨勢不會停止；但是另一方面，青蛙所在扇形編號的平方和不可能永無止境地增加下去（不會大于(4n+1)n2），由此產(chǎn)生矛盾，所以遲早會有青蛙越過 1號扇形與n號扇形之間的隔墻，進(jìn)入 1號扇形。我們再來證明1號扇形遲早會有三只青蛙跳入。如果 1號扇形中至多有兩只青蛙跳入，那么它們都不會跳走，并且自始至終上述平方和至多有兩次變?。ㄖ荒茉趦芍磺嗤茉竭^1號扇形與n號扇形之間的隔墻時(shí)變?。?，以后便一直持續(xù)不斷地上升，從而又重蹈剛才的矛盾。所以1號扇形遲早會有3只青蛙跳入。如果這三只青蛙中有位于A格的，那么格A中已經(jīng)有青蛙跳入；如果這3只青蛙全都位于格B，那么格B會發(fā)生“爆發(fā)”，從而有青蛙跳入格A。.訓(xùn)練題對有限集A，存在函數(shù)f:N*→A,具有下述性質(zhì)：若i,j∈N*,且|i-j| 是素?cái)?shù)，則f(i) ≠f(j) ，問集合 A中至少有幾個元素？．10人到書店買書，已知（1）每人都買了三種書；（2）任何兩人所買的書中，都至少有一種相同。問購買的人數(shù)最多的一種書最少有幾個人購買？．在一個有限的實(shí)數(shù)數(shù)列中，任何七個連續(xù)項(xiàng)之和都是負(fù)數(shù)，而任何十一個連續(xù)項(xiàng)之和都是正數(shù)，試問這樣的數(shù)列最多能有多少項(xiàng)？．給定平面上的點(diǎn)集P={P1,P2,?,P1994},P中任三點(diǎn)不共線，將P中點(diǎn)任意分成 83組，使每組至少有 3個點(diǎn)，每點(diǎn)恰好屬于一組。將每組中任二點(diǎn)均連成一線段，不在一組的兩點(diǎn)不連線段。這樣得到了一個圖G。顯然，不同連接線段的方式，得到不同的圖。圖G中所含以P中點(diǎn)為頂點(diǎn)的三角形的個數(shù)記為m(G)。1）求m(G)的最小值m0;2）設(shè)G*是使m(G*)=m0的一個圖，若將G*中的線段用4種顏色染色，每條線段恰好染一種顏色。則存在一種染色法，使 G*中線段染色后，不含同色邊三角形。5．在7×7個小方格的正方形里，劃出 K個小方格的中心，使其中任何四個點(diǎn)都不是其邊與正方形的邊平行的矩形的頂點(diǎn)，這種 K的最大可能值是多少？6．在100×25的長方形表格中每一格填入一個非負(fù)實(shí)數(shù)，第 i行第j列中填入的數(shù)為xi,j(i=1,2,?,100;j=1,2,?,25)，如表1。然后將表1每列中的數(shù)按由大到小的次序從上到下重新排列為 x’1,j≥x’2,j≥?≥x’100,j(j=1,2, ?,25), 如表2。求最小自然數(shù)K，使得只要表1中填入的數(shù)滿足25xi,j 1(i 1,2,...,100)，則當(dāng)i≥K時(shí)，在表 2中就能保證j1

25x'i,j 1成立。j 1X1,1X1,2?X1,25表1X’1,1X’1,2?X’1,25X2,1X2,2?X2,25表2X’2,1X’2,2?X’2,25????????XX?X’100’100?’100100,100,XXX100,,1225,1,2257、有n張卡片，每張卡片上有 1到n中的1個數(shù)，且每張卡片上的數(shù)不同。n張卡片一字排開，可進(jìn)行如下操作：即將相鄰兩張1卡片調(diào)換過來。證明：無論卡片如何排列，最多經(jīng)過 n(n-1)次操作2后，卡片按從大到小順序排列。四.訓(xùn)練題提示或解答1． 因?yàn)?,3,6,8 這四個數(shù)字中任何兩個數(shù)字的差的絕對值均為素?cái)?shù)，由題意知

f(1),f(3),f(6),f(8)

是A中四個兩兩不等的元素。從而|A|

≥4.另一方面，若令

A={0,1,2,3},f:

N*

A的對應(yīng)關(guān)系為：若

x∈

N*

,x=4k+r,

則

f(x)=r,

其中K∈N,r=0,1,2,3

，則任取

x,y

∈

N*,

若|x-y|

為素?cái)?shù)，假設(shè)

f(x)=f(y), 則x≡y(mod4),于是 4||x-y|, 這與|x-y| 是素?cái)?shù)矛盾。故集合A中至少含有4個元素。2． 設(shè)其中甲買了三種書，因他與其余 9個人中每人都至少有一種書相同，所以，甲的三種書中，購買人數(shù)最多的一種書不少于4人購買。若購買人數(shù)最多的一種書有4人購買，則甲的三種書均為4人購買，其他9人的每種書也均為4人購買。因而，10人買書的總數(shù)是4的倍數(shù)，即4|30，矛盾。于是，購買的人最多的一種書至少有 5人購買?？紤]下面的購買方式：{B1,B2,B3},{B1,B2,B4},{B2,B3,B5},{B1,B3,B6},{B1,B4,B5},{B2,B4,B6},{B3,B4,B5},{B1,B5,B6},{B2,B5,B6},{B3,B4,B6}設(shè)已知數(shù)列為a1,a2,?,an?？疾煜旅娴呐帕校篴1,a2,a3,a4,a5,a6,?,a11,a2,a3,a4,a5,a6,a7,?,a12,a3,a4,a5,a6,a7,a8,?,a13,???????,a7,a8,a9,a10,a11,a12,?,a17,由題設(shè)條件，每一橫行之和為正數(shù)，故表中所有數(shù)之和為正數(shù)。另一方面，每一列的數(shù)之和為負(fù)數(shù)。將所有列的數(shù)的和相加，其和為負(fù)，既又得到表中所有數(shù)之和為負(fù)數(shù)。矛盾，故這樣的數(shù)列最多能有16項(xiàng)。下面我們構(gòu)造一個有 16項(xiàng)的滿足條件的數(shù)列：5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5 。綜上可知，滿足題中要求的數(shù)列最多有 16項(xiàng)。4．（1）設(shè)各組所含點(diǎn)數(shù)為 x1,x2,?,x83,則x1+x2+?+x83=1994,且m(G)=C3x1+C3x2+?+C3x83,(*)若x1-x2>1,則將第一組的一個點(diǎn)移到第二組。因?yàn)?Cx1

1

3Cx2

1

3Cx1

3Cx2

3Cx1

1

3Cx2

2Cx2

3Cx1

1

2Cx1

1

3Cx2

2Cx2

2Cx1

<0,m(G)將1減小。所以在

m(G)最小時(shí)，每兩個

xi

的差≤1因1994=83×24+2=24×81+2×25故符合條件的使 m(G)最小的每組法只有一種： 81組各含24點(diǎn)，二組各含25點(diǎn)，這時(shí)，m0=81C324+2C325=168544(2)對25點(diǎn)的組染色如下：將點(diǎn)分為 5組：y1,y2,y3,y4,y5,每組5點(diǎn)；每組線段按圖（A）染a,b二色；不同組間的連線，按圖（B）染另二色c,d。這樣染色，沒有同邊三角形。至于24點(diǎn)的組，只須從25點(diǎn)的組中去掉一點(diǎn)以及連結(jié)它的所有線段即可，當(dāng)然也不會有同色邊的三角形出現(xiàn)。圖（A） 圖B）5．考慮mxm的正方形，設(shè)xi是第i行中適合條件的小方格的中m心的數(shù)目，則 xi k。如果在某行標(biāo)出某兩個方格的中心，那么在i 1另外任何一行不能標(biāo)相同列的一對方格。在第I行有1xi(xi1)對標(biāo)2出的方格。又因?yàn)槊啃袠?biāo)出的方格對不同，故有mxi(xi1)m(m1)，從而22i1mmm(x1...xm)2k2xi2m(m1)xim(m1)k，又因?yàn)閤i2,i1i1i1mm故k2≤m(m-1)+k，解得K1(mm4m3),當(dāng)m=7時(shí)，k≤21,Km2的最大值為21，如圖：*********************．令x1,1=x2,1=x3,1=x4,1=x5,2=x6,2=x7,2=x8,2=0,?,x97,25=x98,25=x99,25=x100,25=0,其余元素為

1，則每行

25個數(shù)之和為

0+24×

1=1，此時(shí)在表

1中每24

24列元素恰有

4個為

0，因而調(diào)整為表二后最后四行全為

0，但前

96行的數(shù)全為

1，每行之和為

25〉1。這說明最小的

K≥97.以下證明24

24K的最小值時(shí)97。因?yàn)楹笕校ǖ?98，99，100行）只能容納75個元素，所以表一中必定有某一行（設(shè)為第 r行），它的全部25個元素，在調(diào)整后的表二中處于前面 97行中。否則每行至少有一個元素落入后三行，則至少有 100個元素落入后三行，這不可能。這說明在表二中，x97,j’≤xr,j(xr,j仍在表二中的第 j列，行數(shù)不一定是r。但行號≤97。）從而對任意i≥97，有xi,j’≤ x97,j’ ≤xr,j。所以當(dāng)i≥97時(shí)，25xi',j25xr,j1。故K的最小值是97。j1j17．證明：現(xiàn)將n號卡片按操作移向第一個位置，不難知道，至多移動n-1次后，n號卡片將到達(dá)第1個位置，而剩下的n-1張卡片中，同理有：n-1號卡片之多經(jīng)過n-2次操作后可到達(dá)第2位，??，2號卡片至多經(jīng)過1次操作，可到達(dá)第n-1位。故至多操作n-1?i=1n(n-1)次后，卡片將按從大到小順序排列。i=1 22009年全國高中數(shù)學(xué)聯(lián)賽模擬試題華南師大附中李興懷第一試一、填空題（每小題7分，共8個小題，滿分56分）1、已知集合A={(x,y)|y=ax+2},B={(x,y)|y=|x+1|}，且AB是一個單元素集，則實(shí)數(shù)a的取值范圍是________。2、對任意實(shí)數(shù)x，函數(shù)f(x)=x2-2x-|x-1-a|-|x-2|+4的值都是非負(fù)實(shí)數(shù)，則實(shí)數(shù)a的取值范圍是________。3、不等式|log2x-3|+|2x-8|39的解集是________。4、已知函數(shù))=2px，若常數(shù)，y=f(wx)在區(qū)fx4sinxsin(+)+cos2xw>0(A42間[-p,2p]上是增函數(shù)，則w的取值范圍是___________。235、P為橢圓x2+y2=1在第一象限上的動點(diǎn)，過點(diǎn)P引圓x2+y2=9的兩條切線169PA,PB，切點(diǎn)分別為A,B。直線AB與x軸、y軸分別交于點(diǎn)M,N，則DMON的面積的最小值是_________。6、空間有四個球，它們的半徑分別為2，2，3，3，每個球都與其余三個球相切，另有一個小球與這四個球都外切，則這個小球的半徑為___________。7、設(shè)正四面體的四個頂點(diǎn)是A,B,C,D，各棱長度為1米，有一個小蟲從A點(diǎn)開始按以下規(guī)則前進(jìn)：在每一個頂點(diǎn)處用同樣的概率選擇通過這個頂點(diǎn)的三條棱之一，并一直爬到這個棱的盡頭，則它爬了7米以后恰好位于頂點(diǎn)A的概率是________________。8、從1，2，?，1000個任選k個數(shù)，若在所選的數(shù)中總有三個構(gòu)成三角形的邊長，則k最小值是___________。二、解答題9、（本題滿分14分）設(shè)n?N*，求證3￡(1+1)n<2。22n10、（本題滿分15分）設(shè)各項(xiàng)均為正數(shù)的數(shù)列{an}滿足3a1=2,an=an2+1an+2(n?N*)，記bn=a1a2×an，且bn322對n2恒成立，求數(shù)列{bn}的通項(xiàng)公式。11、（本題滿分15分）設(shè)函數(shù)f(x)=sinx，如果對任意x30，都有f(x)￡ax，求實(shí)數(shù)a的取值范2+cosx圍。第二試一．（本題滿分50分）已知數(shù)列{an}滿足a1=1，2an=(2n-3)an-1，n=2,3,4,×。求證：對任何正整數(shù)nn，有?ak<1。2nk=1二．（本題滿分50分）在直角三角形ABC中，ACB與邊，，相切于點(diǎn)，，，連接與內(nèi)切圓BCCAABDEFAD

90，△ABC的內(nèi)切圓O分別O相交于點(diǎn)P，連接BP，CP，若BPC 90，求證：AE AP PD．三．（本題滿分50分）求所有的素?cái)?shù)對（p，q），使得pq5p5q．四．（本題滿分50分）n個點(diǎn)P1,P2,,Pn順次在一條直線上，每個點(diǎn)染上白、紅、綠、藍(lán)、紫色中的一種顏色，若對任意相鄰的兩點(diǎn)Pi,Pi1(i1,2,,n1)，要么這兩點(diǎn)同色，要么至少有一點(diǎn)為白色，則稱之為好的染法。求好的染法的總數(shù)。2009年全國高中數(shù)學(xué)聯(lián)賽模擬試題

第一試解答一．填空題1、解：作出函數(shù)

y=|x+1|的圖像，然后討論直線

y=ax+2的位置，由圖像可知：當(dāng)a31時(shí)，

A

B是單元集；

-1<a<1時(shí)，

A

B是二元集；

a￡-1時(shí)，

A

B也是單元集。故所求

a的取值范圍是

(-

￥,-1]

[1,+￥]。第1題圖ì=-|1+a|+2302、解：由條件知?，解得-2￡a￡1。í?=-|a|+230?f(1)下面證明：當(dāng)-2￡a￡1時(shí)，對任意x?R，都有f(x)30，事實(shí)上，記t=x-1，則f(x)=t2-|t-a|-|t-1|+3，記g(t)=t2+3-|t-a|-|t-1|，當(dāng)t￡a時(shí)，g(t)=t2+3-(a-t)-(1-t)=(t+1)2+(1-a)30當(dāng)a<t￡1時(shí)，g(t)=t2+3-(t-a)-(1-t)=t2+2+a結(jié)合a32知g(t)30；當(dāng)t>1時(shí)，g(t)=t2+3-(t-a)-(t-1)=t2-2t+4+a=(t-1)2+3+a33a31+所以當(dāng)-2￡a￡1時(shí)，總有f(x)30，故滿足條件的a構(gòu)成的集合為{a|-2￡a￡1}。3、解：由條件知x>0，分三種情形討論：（1）當(dāng)x?(0,3]時(shí)，原不等式變形為2x+log2x￡2，由于f(x)=2x+log2x在(0,3]上遞增，結(jié)合 f(1)=2，可知0<x￡1。2）當(dāng)x?(3,8]，原不等式變形為2x-log2x314，記g(x)=2x-log2x，則g'(x)=2xln2-1，當(dāng)x33時(shí)，2xln238ln2，1￡1，又xln2xln23ln28ln2-1=ln28-1>0，所以g(x)在x33時(shí)單調(diào)遞增，又3ln2ln8g(4)=24-log24=14故此時(shí)不等式的解集為[4,8]；（3）當(dāng)x>8時(shí)，原不等式變?yōu)?x+log2x320，而x>8時(shí)，2x+log2x>28+log28=259>20，故x>8滿足原不等式。故所求不等式的解集為(0,1][4,+￥)。4、解：f(x)=2sinx+1，而f(wx)=2sinwx+1在[-p,2p]上是增函數(shù)，故23p,2p]2kp-p2kp+p，故2k-1￡-1w，2k+132w，[-[2,2]，其中k?Z23íww2223即4k￡1-w<1，4k34w-1>-1，從而k=0，故w?(0,3]。345、解：設(shè)P(4cos,3sin)，q?(0,p)，則直線AB的方程為qq24xcos+3ysinq=9，q故|OM|=9,|ON|=3,SDMON=1|OM|A|ON|=27327，當(dāng)4cosqsinq24sin2q4q=p，即P為(22,32)時(shí)等式成立，故SDMON的最小值為27。424第5題圖6、解：如圖，以四個球的球心為頂點(diǎn)作四面體 ABCD，AB=6,CD=4，AC=BC=AD=BD=5，設(shè)AB、CD的中點(diǎn)分別為 F，E，小球的球心為 O，由圖形的對稱性可知 O點(diǎn)在EF上。設(shè)小球的半徑為 r，則OE= OC2-EC2= (r+2)2-22= r(r+4)，OF= OA2-AF2= (r+3)2-33= r(r+6)EF=AE2-AF2=AD2-DE2-AF2=52-22-32=12,因?yàn)镋F=OF+0F，所以12=r(r+4)+r(r+6)，解得r=6，故這個小球的半徑為6。1111AFODBEC第6題圖7、解：設(shè)an表示小蟲走過 n米后又達(dá)到 A點(diǎn)的概率（n=0，1，2??），若小蟲爬過n-1米而不在A點(diǎn)，則概率是1-an-1，而從A外的一點(diǎn)向A爬來的概率是1，因此有3an=1(1-an-1)，又知a0=1，可計(jì)算得a7=182，故所求概率為182。37297298、解：選取 15個數(shù)：1，2，3，5，8，13，21，34，55，89，233，377，610，987，其中的任三個數(shù)均不能組成三角形的三邊，所以 k316。設(shè)選出的 16個數(shù)a1<a2< ×<a16，若沒有三個數(shù)構(gòu)成三角形的三邊長，則a131,a232,a33a1+a233,a43a2+a335,×,a153a13+a143987,a163a14+a1531597，這與a16￡1000矛盾，所以選出的 16個數(shù)，必有三個數(shù)組成三角形的三邊，綜上， k的最小值為16.二、解答題9、證明：

(11)n=C0+C1(1)+C2(1)2+××+Cr(1)r+×+Cn(1)n+2nnn2nn2nn2nn2n1 n

1

32n又Cnr(1)r2n故

21)(n2)(nr1)1r1rn(n--+=××-A()￡()，r!nr22(11)n11(1)2+××+(1)r+××+(1)n2n22221-(1)n+11222=1=-2n<1-2故3￡(1+1)n<2。22n10．解：由于bn=a1a2××an，則log2bn=log2a1+log2a2+×+log2an令xn=log2an,n=1,2×,Sn表示{xn}的前n項(xiàng)和，則bn=2Sn，由題設(shè)x1=1,xn=3xn+1+xn+2,(n?N*)①2Sn=x1+x2+××+xn33(n32)②23，又x1=1，故x231③②式對n=2成立，所以x1+x2322下面用反證法證明：x2￡1。假設(shè)x2>1，由①得xn+2+2xn+1=1(xn+1+2xn)222故{xn+1+2xn}是首項(xiàng)為x2+2，公比為1的等比數(shù)列，故2xn+1+2xn=1A(x2+2)，n?N*，④2n-1又由①xn+2+1xn+1=-2(xn+1-1xn)，因此{(lán)xn+1-1xn}是首項(xiàng)為x2-1，公比212122為-2的等比數(shù)列，故xn+1-xn=(-2)n-1A(x2-)，n?N*⑤52112由④-⑤得n-1*xn=(x2+2)An-1-(x2-)(-2)，n?N⑥2225Sn=(x2+2)(2-1(x2-11-(2)n*對n求和得n-1)-)-,n?N⑦2223由題設(shè)，知Sn+133，n?N*，且由反證假設(shè)x2>1，有2212k)-1)22k+1+115，（這里在⑦中取(x2+2)(2-(x2-33n=2k+1,k31）224從而(x2-122k+1+1-1)-15<2x21，k?N*)3￡(x2+2)(22k4+2246x2322k14對k?N*即不等式x212恒成立，但這是不可能的，矛盾，因此x2￡1，結(jié)合③式，x2=1，因此221代入⑦式，Sn=2-11a2=2x2=2-2，將x2=，n?N*，所以bn=2Sn=22n-1。22n-111．解：令g(x)=ax-f(x)，則2cosx+12+3=3(11)2+a-1g'(x)=a-+cosx)2=a-2+cosx-，(22+cosx(cosx+2)233故當(dāng)a31時(shí)，g'(x)30，所以g(x)在0,上是增函數(shù)，又g(0)=0，所以當(dāng)3x30時(shí)，g(x)3g(0)=0，即f(x)￡ax。當(dāng)0<a<1時(shí)，令h(x)=sinx-3ax，則h'(x)=cosx