45屆imo試題全解與思路分析

45屆imo試題全解與思路分析考試時(shí)間：______分鐘總分：______分姓名：______第一題設(shè)集合S={1,2,3,...,n}，A和B是S的兩個(gè)非空子集，且A∪B=S。如果A和B的元素個(gè)數(shù)之差為1，那么滿足條件的A和B的對數(shù)有多少個(gè)？第二題在銳角三角形ABC中，內(nèi)角A,B,C的對邊分別為a,b,c。如果a2+b2-c2=ab，求sinA+sinB+sinC的最大值。第三題給定一個(gè)由n個(gè)整數(shù)組成的序列a?,a?,...,a?。定義序列b?,b?,...,b?如下：對于每個(gè)i(1≤i≤n)，b?是a?,a?,...,a?中最大值與最小值之差。求證：序列b?,b?,...,b?的所有元素之和至多為n2-1。第四題函數(shù)f:R→R滿足對于所有x,y∈R，都有f(x+y)=f(x)+f(y)+xy。如果f(1)=2，求f(0)的值。第五題設(shè)P是單位圓內(nèi)一點(diǎn)，其坐標(biāo)為(cosθ,sinθ)，其中0<θ<π/2。過點(diǎn)P作圓的切線，分別交x軸和y軸于點(diǎn)A和B。記線段AB的中點(diǎn)為M。求點(diǎn)M到原點(diǎn)O的距離的最小值。第六題證明：對于任意正整數(shù)n≥2，在n×n的國際象棋棋盤上，不能放置超過?n2/2?個(gè)國王，使得它們互不攻擊。其中，國王在棋盤上可以攻擊同一行、同一列或同一對角線上的任意一個(gè)相鄰方格。第七題設(shè)x,y,z是正實(shí)數(shù)，且滿足x+y+z=1。求表達(dá)式(x+1/x)2+(y+1/y)2+(z+1/z)2的最小值。第八題在一個(gè)無向圖中，每個(gè)頂點(diǎn)的度數(shù)都是3。如果圖中有20個(gè)頂點(diǎn)，問圖是否必然包含一個(gè)包含至少6條邊的環(huán)？請證明你的結(jié)論。第九題設(shè)正整數(shù)n≥3。考慮所有可能的n元正整數(shù)數(shù)組(a?,a?,...,a?)，其中1≤a?≤n對于所有i∈{1,2,...,n}。如果數(shù)組中任意兩個(gè)相鄰的元素之差都不超過1，那么這樣的數(shù)組有多少個(gè)？第十題設(shè)P(x)是一個(gè)次數(shù)為n的實(shí)系數(shù)多項(xiàng)式，且對于所有x∈R，都有P(x)≥0。如果P(x)有n個(gè)不同的實(shí)根，證明：P(x)必須是常數(shù)多項(xiàng)式。試卷答案第一題解析思路設(shè)|A|=k，則|B|=n-k。由于|A|和|B|之差為1，所以有兩種情況：k=n-k-1，即k=(n-1)/2，或k=n-k+1，即k=(n+1)/2。需要分別計(jì)算這兩種情況下的A和B的對數(shù)。對于k=(n-1)/2，從n個(gè)元素中選取k個(gè)元素的方法數(shù)為C(n,k)，即C(n,(n-1)/2)。對于k=(n+1)/2，方法數(shù)為C(n,k)=C(n,(n+1)/2)。將兩種情況下的方法數(shù)相加，得到滿足條件的A和B的對數(shù)總數(shù)。第二題解析思路由已知條件a2+b2-c2=ab，利用余弦定理得到cosC=(a2+b2-c2)/(2ab)=ab/(2ab)=1/2。因?yàn)槿切蜛BC是銳角三角形，所以C=π/3。然后利用三角形內(nèi)角和定理得到A+B=π-C=2π/3。利用正弦函數(shù)的性質(zhì)和A+B的值，可以將sinA+sinB表示為sinA+sin(2π/3-A)=sinA+(sin2π/3cosA-cos2π/3sinA)=sinA+(√3/2cosA+1/2sinA)=(3/2)sinA+(√3/2)cosA=√3sin(A+π/6)。由于0<A<π/2，所以π/6<A+π/6<2π/3，因此sin(A+π/6)的最大值為1。當(dāng)且僅當(dāng)A+π/6=π/2，即A=π/3時(shí)取到最大值。此時(shí)sinB=sin(2π/3-A)=sin(π/3)=√3/2。所以sinA+sinB+sinC=√3/2+√3/2+√3/2=3√3/2。第三題解析思路使用歸納法證明。基礎(chǔ)情況n=1，序列a?有一個(gè)元素，b?=a?-a?=0，和為0，滿足n2-1=0。假設(shè)對于n=k時(shí)，和至多為k2-1。考慮n=k+1的情況。當(dāng)a<0xE2><0x82><0x99>?添加到序列時(shí)，如果a<0xE2><0x82><0x99>?>b<0xE2><0x82><0x99>，則b<0xE2><0x82><0x99>?=b<0xE2><0x82><0x99>-a<0xE2><0x82><0x99>?，新增加的差為a<0xE2><0x82><0x99>?-0=a<0xE2><0x82><0x99>?。如果a<0xE2><0x82><0x99>?<b<0xE2><0x82><0x99>，則b<0xE2><0x82><0x99>?=b<0xE2><0x82><0x99>-a<0xE2><0x82><0x99>?，新增加的差為(a<0xE2><0x82><0x99>?-a<0xE2><0x82><0x99>?)=0。因此，新增加的差至多為a<0xE2><0x82><0x99>?。所以b<0xE2><0x82><0x99>?+...+b<0xE2><0x82><0x99>?的和至多為(k2-1)+a<0xE2><0x82><0x99>?≤k2-1+(k+1)-1=(k+1)2-1。即對于n=k+1也成立。由歸納法原理，結(jié)論成立。第四題解析思路令y=0，代入函數(shù)方程得到f(x)=f(x)+f(0)+0*02=f(x)+f(0)。因此f(0)=0。這是最直接的求解f(0)的方法。第五題解析思路設(shè)切線方程為y=k(x-cosθ)+sinθ。令y=0，解得x=cosθ-sinθ/k。令x=0，解得y=sinθ-kcosθ。所以A(cosθ-sinθ/k,0)，B(0,sinθ-kcosθ)。中點(diǎn)M的坐標(biāo)為((cosθ-sinθ/k)/2,(sinθ-kcosθ)/2)。利用兩點(diǎn)間距離公式計(jì)算OM的長度：√[((cosθ-sinθ/k)/2)2+((sinθ-kcosθ)/2)2]=1/2√[(cosθ-sinθ/k)2+(sinθ-kcosθ)2]=1/2√[cos2θ-2cosθsinθ/k+sin2θ/k2+sin2θ-2kcosθsinθ+k2cos2θ]。將sin2θ/k2替換為(1-cos2θ)/k2，并整理，得到1/2√[1-cos2θ/k2+1-2cosθsinθ/k+k2cos2θ-2kcosθsinθ+k2cos2θ]=1/2√[2-2cosθsinθ/k+2k2cos2θ-2kcosθsinθ]。提取公因數(shù)1/2，得到1/2√[2(1-cosθsinθ/k+k2cos2θ-kcosθsinθ)]。為了找到最小值，可以將其寫為1/2√[2(k2cos2θ-kcosθsinθ+1-cosθsinθ/k)]。注意到k是切線的斜率，k=tanθ。將k替換為tanθ，得到1/2√[2(tan2θ-tanθsinθ+1-sinθ/tanθ)]。進(jìn)一步化簡為1/2√[2(sec2θ-sinθcosθ+1-sin2θ/cos2θ)]=1/2√[2(1/cos2θ-sinθcosθ+1-sin2θ/cos2θ)]=1/2√[2(2/cos2θ-sinθcosθ)]=1/2√[4/cos2θ-2sinθcosθ]=1/2√[4-2sinθcosθ*cos2θ]=1/2√[4-2sinθcos3θ]。令h(θ)=4-2sinθcos3θ。求h(θ)的最小值。h'(θ)=-2(cos?θ+3sin2θcos2θ)=-2cos2θ(cos2θ+3sin2θ)=-2cos2θ(1+2sin2θ)。在(0,π/2)內(nèi)，cos2θ>0，1+2sin2θ>0，所以h'(θ)<0。因此h(θ)在(0,π/2)內(nèi)單調(diào)遞減。h(θ)的最小值在θ=π/2處取得，但θ=π/2時(shí)M點(diǎn)在原點(diǎn)，距離為0。考慮θ接近0的情況，h(θ)接近4。當(dāng)θ=π/6時(shí)，cosθ=√3/2，sinθ=1/2，h(π/6)=4-2*(1/2)*(√3/2)3=4-2*(1/2)*(√3/8)=4-(√3/8)=32/8-√3/8=(32-√3)/8。所以O(shè)M2=1/4*[(32-√3)/8]2=(32-√3)2/256=(1024-64√3+3)/256=1027/256。最小值在θ=π/6時(shí)取得，最小距離為√(1027/256)=1027^(1/2)/16。另一種方法是利用直角三角形AMO，其中M是AB中點(diǎn)，O是圓心。OM=OA*cos(∠OAM)=1*cos(∠OAM)。∠OAM是角θ/2的一半，即∠OAM=θ/4。所以O(shè)M=cos(θ/4)。利用cos(θ/4)的最小值在θ=π/2時(shí)取得，即cos(π/8)=√(2+√2)/2。所以最小值為√(2+√2)/2。這里似乎與之前的計(jì)算結(jié)果不同，需要重新審視計(jì)算過程或方法。更準(zhǔn)確的方法是利用M點(diǎn)坐標(biāo)直接計(jì)算OM距離，并找到其最小值。M(x,y)如第一題解析思路所示。OM2=x2+y2=((cosθ-sinθ/k)/2)2+((sinθ-kcosθ)/2)2=(1/4)[(cosθ-sinθ/k)2+(sinθ-kcosθ)2]。展開并整理，得到OM2=(1/4)[cos2θ-2cosθsinθ/k+sin2θ/k2+sin2θ-2kcosθsinθ+k2cos2θ]=(1/4)[cos2θ+sin2θ/k2+sin2θ-2cosθsinθ(k+1/k)+k2cos2θ]=(1/4)[1+sin2θ/k2-2cosθsinθ(k+1/k)+k2cos2θ]。令k=tanθ，則sinθ/k=cotθ，sin2θ/k2=1/tan2θ。代入得到OM2=(1/4)[1+1/tan2θ-2cosθcotθ(tanθ+1/tanθ)+tan2θcos2θ]=(1/4)[1+1/tan2θ-2cosθ(1+1/tan2θ)+(sin2θ/cos2θ)cos2θ]=(1/4)[1+1/tan2θ-2cosθ-2cosθ/tan2θ+sin2θ]=(1/4)[1+1/tan2θ-2cosθ-2cosθsin2θ/cos2θ+sin2θ]=(1/4)[1+1/tan2θ-2cosθ-2sin2θ+sin2θ]=(1/4)[1+1/tan2θ-2cosθ-sin2θ]=(1/4)[cos2θ+1-2cosθ-sin2θ]=(1/4)[2cos2θ-2cosθ]=(1/2)[cos2θ-cosθ]。令u=cosθ，則OM2=(1/2)[u2-u]。這是一個(gè)關(guān)于u的二次函數(shù)，開口向上，頂點(diǎn)為u=1/2。當(dāng)u=1/2時(shí)，OM2取得最小值(1/2)[(1/2)2-1/2]=(1/2)[1/4-1/2]=(1/2)(-1/4)=-1/8。這個(gè)結(jié)果顯然是錯(cuò)誤的，因?yàn)榫嚯x平方不可能為負(fù)。問題出在令u=cosθ的范圍上。二次函數(shù)的頂點(diǎn)u=1/2不在cosθ的典型范圍[0,1]內(nèi)（對于0<θ<π/2，cosθ∈(0,1)）。需要考慮cosθ在(0,1)內(nèi)的端點(diǎn)或內(nèi)部極值。函數(shù)f(u)=(1/2)(u2-u)在u∈(0,1)內(nèi)單調(diào)遞減（因?yàn)閒'(u)=u-1/2<0）。所以最小值在u接近1時(shí)取得，即θ接近0時(shí)。此時(shí)cosθ接近1，sinθ接近0。OM2接近(1/2)[1-1]=0。當(dāng)θ=π/2時(shí)，M點(diǎn)在原點(diǎn)，OM=0。所以O(shè)M的最小值為0。另一種更準(zhǔn)確的處理方法是利用M點(diǎn)坐標(biāo)和θ的關(guān)系。M=((cosθ-sinθ/tanθ)/2,(sinθ-tanθcosθ)/2)=((cosθ-sinθcotθ)/2,(sinθ-sinθ)/2)=((cosθ-cosθ)/2,0)=(0,0)。所以點(diǎn)M總是位于原點(diǎn)。因此，點(diǎn)M到原點(diǎn)O的距離為0。這顯然是最小值。第六題解析思路證明國王不能超過?n2/2?個(gè)。假設(shè)可以放置n2/2+1個(gè)國王，記為K?,K?,...,K_(n2/2+1)。考慮棋盤上任意一個(gè)方格，它最多可以與周圍8個(gè)方格相鄰。如果這個(gè)方格被國王占據(jù)，那么它最多可以攻擊8個(gè)方格。如果這個(gè)方格未被占據(jù)，那么它最多可以被周圍8個(gè)方格中的國王攻擊。設(shè)G是所有國王的集合，|G|=n2/2+1。設(shè)C是棋盤上所有方格的集合，|C|=n2。設(shè)A是被國王攻擊的方格的集合，A的每個(gè)方格最多被4個(gè)相鄰方格中的國王攻擊（角落方格最多被3個(gè)，邊方格最多被5個(gè)，內(nèi)部方格最多被8個(gè)，但無論如何，每個(gè)方格被攻擊的次數(shù)是有限的，且不超過其周圍方格中國王的數(shù)量）。但是，每個(gè)國王K_i可以攻擊的方格數(shù)是有限的，不超過8。因此，被所有國王攻擊的方格總數(shù)|A|≤8*|G|=8*(n2/2+1)=4n2+8。但是，棋盤上每個(gè)方格最多被4個(gè)相鄰方格中的國王攻擊。因此，被攻擊的方格總數(shù)|A|不會(huì)超過棋盤上所有方格數(shù)|C|的一半，即|A|≤n2/2。因此，我們得到矛盾：4n2+8≤n2/2。即8n2+16≤n2，這顯然不成立。因此，假設(shè)不成立，國王的數(shù)量不能超過n2/2。另一方面，可以構(gòu)造性地放置?n2/2?個(gè)國王而不使它們互相攻擊。例如，當(dāng)n為偶數(shù)時(shí)，將棋盤劃分為n/2×n/2的小方格，在每個(gè)小方格的中心放置一個(gè)國王。當(dāng)n為奇數(shù)時(shí)，將棋盤劃分為(n-1)/2×(n-1)/2的小方格，在每個(gè)小方格的中心放置一個(gè)國王，然后在最后一行和最后一列的中間方格各放置一個(gè)國王。這樣放置的國王數(shù)量為(n-1)2/4+2=(n2-2n+1)/4+8/4=(n2-2n+9)/4=?n2/2?。可以驗(yàn)證這些國王不會(huì)互相攻擊。因此，國王的數(shù)量可以達(dá)到?n2/2?。結(jié)合兩方面，國王的數(shù)量不超過?n2/2?。第七題解析思路使用柯西-施瓦茨不等式（Cauchy-SchwarzInequality）。對于任意的正實(shí)數(shù)x,y,z，有(x+1/x)2+(y+1/y)2+(z+1/z)2≥(x+1/x+y+1/y+z+1/z)2/3。等號(hào)成立當(dāng)且僅當(dāng)x+1/x=y+1/y=z+1/z。由于x+y+z=1，所以x+1/x+y+1/y+z+1/z=(x+y+z)+(1/x+1/y+1/z)=1+(1/x+1/y+1/z)。所以原表達(dá)式≥(1+(1/x+1/y+1/z))2/3。現(xiàn)在需要估計(jì)1/x+1/y+1/z。使用調(diào)和平均數(shù)與算術(shù)平均數(shù)不等式（AM-HMInequality）：1/(x+y+z)≥3/(x+y+z+x+y+z)=3/(2(x+y+z))=3/(2*1)=3/2。所以1/x+1/y+1/z≥3/(x+y+z)=3/1=3。因此，原表達(dá)式≥(1+3)2/3=42/3=16/3。等號(hào)成立當(dāng)且僅當(dāng)x+1/x=y+1/y=z+1/z，且x+y+z=1。等號(hào)成立當(dāng)且僅當(dāng)x=y=z=1/3（因?yàn)閤+1/x在x>0時(shí)在x=1時(shí)取到最小值2）。所以最小值為16/3，當(dāng)且僅當(dāng)x=y=z=1/3時(shí)取得。第八題解析思路使用圖論中的結(jié)論。一個(gè)3-正則圖（每個(gè)頂點(diǎn)度數(shù)為3）如果包含一個(gè)環(huán)，那么這個(gè)環(huán)的長度至少為4。因?yàn)槿绻h(huán)的長度為3，那么三個(gè)頂點(diǎn)形成一個(gè)三角形，每個(gè)頂點(diǎn)的度數(shù)為3，意味著每個(gè)頂點(diǎn)都與其他兩個(gè)頂點(diǎn)相連，這與三角形只有3條邊的性質(zhì)矛盾。因此，任何環(huán)的長度至少為4。如果圖中有20個(gè)頂點(diǎn)，那么邊的總數(shù)為3*20/2=30。如果圖包含一個(gè)長度至少為6的環(huán)，那么這個(gè)環(huán)至少有6條邊。假設(shè)存在一個(gè)長度至少為6的環(huán)。設(shè)這個(gè)環(huán)為v?,v?,...,v?。這個(gè)環(huán)使用了6條邊。剩下的14個(gè)頂點(diǎn)構(gòu)成了一個(gè)子圖，其中每個(gè)頂點(diǎn)的度數(shù)為3-1=2（因?yàn)槊總€(gè)頂點(diǎn)在環(huán)上貢獻(xiàn)了1條度數(shù)，總共3度數(shù)，剩下2度數(shù)在子圖中）。這個(gè)子圖有14個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)度數(shù)為2，總度數(shù)為14*2=28。但是，子圖的邊數(shù)少于14（因?yàn)槊總€(gè)頂點(diǎn)至少與環(huán)上的一個(gè)頂點(diǎn)相連，且不能自環(huán)）。因此，子圖的邊數(shù)不可能達(dá)到28。這與圖的邊數(shù)總和為30矛盾。因此，假設(shè)不成立，圖中不包含長度至少為6的環(huán)。所以，圖是否必然包含一個(gè)包含至少6條邊的環(huán)？答案是：否。可以構(gòu)造一個(gè)不包含長度至少為6的環(huán)的3-正則圖。例如，對于n≥4，可以構(gòu)造一個(gè)由兩個(gè)n階循環(huán)群的并集組成的圖，每個(gè)循環(huán)群有n個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)度數(shù)為n/2（當(dāng)n為偶數(shù)時(shí)），或者n個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)度數(shù)為(n+1)/2（當(dāng)n為奇數(shù)時(shí)）。對于n=4，就是兩個(gè)K?的并集，沒有環(huán)。對于n=5，可以構(gòu)造一個(gè)圖，類似于兩個(gè)K?.2的并集，沒有長度為6的環(huán)。因此，結(jié)論是否定的。第九題解析思路使用卡特蘭數(shù)（CatalanNumber）的遞推公式。設(shè)a_n表示滿足條件的數(shù)組的個(gè)數(shù)。對于n=1，只有一個(gè)數(shù)組(1)。a_1=1。對于n=2，有兩個(gè)數(shù)組(1,1)和(1,2)。a_2=2。對于n≥3，考慮數(shù)組的第一個(gè)元素a?。如果a?=1，那么剩下的n-1個(gè)元素組成的數(shù)組必須滿足條件，且第一個(gè)元素不能大于1。這相當(dāng)于在1到n-1的范圍內(nèi)構(gòu)造滿足條件的數(shù)組，共有a_(n-1)個(gè)。如果a?=2，那么第二個(gè)元素a?必須等于1（否則差會(huì)超過1），剩下的n-2個(gè)元素組成的數(shù)組必須滿足條件，且第一個(gè)元素不能大于1。這相當(dāng)于在1到n-2的范圍內(nèi)構(gòu)造滿足條件的數(shù)組，共有a_(n-2)個(gè)。類似地，如果a?=3，那么a?=2，a?=1，剩下的n-3個(gè)元素組成的數(shù)組必須滿足條件，共有a_(n-3)個(gè)。依此類推，如果a?=n-1，那么后面n-1個(gè)元素必須嚴(yán)格遞減，即(n-2,n-3,...,1)，這是唯一一種可能，共有a_1=1個(gè)。因此，遞推關(guān)系為a_n=a_(n-1)+a_(n-2)+...+a_1+a_0=a_(n-1)+a_(n-2)+...+a_1（因?yàn)閍_0=1）。這個(gè)遞推關(guān)系與Catalan數(shù)的遞推關(guān)系a_n=a_(n-1)+a_(n-2)+...+a_1=(2n-2)!/(n!*(n-1)!)類似。實(shí)際上，對于這個(gè)問題，滿足條件的數(shù)組個(gè)數(shù)正好等于第n-1個(gè)Catalan數(shù)C_(n-1)=(2(n-1)-2)!/((n-1)!*((n-1)-1)!)=(2n-4)!/(n!*(n-2)!)。這是因?yàn)樵跇?gòu)造過程中，如果將1視為一個(gè)單位，那么構(gòu)造過程類似于在n個(gè)括號(hào)中插入n-1個(gè)逗號(hào)使得表達(dá)式平衡的過程，這正好對應(yīng)Catalan數(shù)的定義。因此，滿足條件的數(shù)組個(gè)數(shù)a_n=C_(n-1)=(2n-4)!/(n!*