數(shù)學(xué)奧林匹克題解E組合數(shù)學(xué) E2計數(shù)和離散最值031-040)

1、E2-031 在一種“咬格子”的游戲中，兩名選手輪流“咬”一個由單位正方形組成的5×7網(wǎng)格所謂“咬一口”，就是一個選手在剩下的正方形中挑一個正方格子去掉（“吃掉”）它的左面的一條邊（朝上延長）與底邊（朝右延長）所確定的象限中的全部正方形格子，如圖a所示，有陰影的格子是選定的，吃掉的是這個有陰影的及打“×”的四個格子（虛線部分是在這之前已被“吃掉”的）游戲的目標(biāo)是要對手“咬”最后一口圖b所示的是35個正方形組成的集合的一個子集，它是在“咬格子”游戲過程中可能出現(xiàn)的一個子集在游戲過程中，可能出現(xiàn)的不同的子集總共有多少個？整個網(wǎng)格及空集也計算在內(nèi)【題說】 第十屆（1992年）美國

2、數(shù)學(xué)邀請賽題12【解】 根據(jù)游戲規(guī)則，每次“吃”剩下的圖形有如下特點：從左到右，各列的方格數(shù)不增因為如某一方格被“吃”，那么它右面和上面的格子全部被“吃”于是每次剩下的圖形從A到B的上邊界是一條由7段橫線與5段豎線組成的折線，且它是不增的；反之，每一條這樣的折線，也對應(yīng)一塊“吃”剩下的方格集 E2-032 1克、30克、50克三種砝碼共110個，總重量為1000克，問其中30克的砝碼有多少個？【題說】 第一屆（1990）希望杯高一二試題2（4）原是填空題【解】 設(shè)1克、30克和50克砝碼數(shù)分別有x、y、z，則有以下關(guān)系：（2）-（1）得29y+49z=890  &

3、#160;                                             （3）因29 890，49 890，所以y0，z0即y1，z

4、1從而890=29y+49z29+49z由于z是整數(shù)，故z17令z=1，2，17，代入（3），知：只有當(dāng)z=1時，y=29是唯一整數(shù)解又由（1）知，x=80即這一組砝碼中有29個30克的砝碼E2-033 下圖中將等邊三角形每邊3等分，過等分點作每邊平行線，這樣所形成的平行四邊形個數(shù)，記為f（3），則f（3）=15將等邊三角形每邊n等分，過各分點作各邊平行線，所形成的平行四邊形個數(shù)記為f（n），求f（n）表達(dá)式【題說】 第二十三屆（1991年）加拿大數(shù)學(xué)奧林匹克題5【解】 如圖所示的平行四邊形，由a、b、c、d四個數(shù)決定這4個數(shù)滿足a1， b1， c0，d02a+b+c+dn即0a1+b1+c+

5、dn-2其中a1=a-1，b1=b-1，c，d均為非負(fù)整數(shù)因此平行四邊形的總數(shù)為【別解】 在BA、BC的延長線上分別取E、F，使BE=BF=n+1，則EF=n+1圖中的平行四邊形，每一邊恰好與EF相交于一點這四點不同，都是EF上的格點（即將EF等分為n+1份的分點）反之，從EF的n+2個格點（包括E、F在內(nèi)）中任取四點，過靠近E的兩點作AB的平行線，過另兩點作BC的平行線，便可得到一個圖中的平行四邊形，所以E2-034 若平面上有997個點，如果每兩點連成一條線段，且中點涂成紅色證明：平面上至少有1991個紅點你能找到一個正好是1991個紅點的特例嗎？【題說】 1991年亞太地區(qū)數(shù)學(xué)奧林匹克題

6、2【證】 在給定的997個點中，設(shè)M、N兩點間的距離最大，分別以 M、N為圓心，MN/2為半徑作圓，這兩個圓僅有一個公共點，即MN的中點E于是MP的中點必在M內(nèi)部或圓周上，這樣的995個點互不相同同理，NP的中點必在N內(nèi)部或圓周上，這樣的995個點互不相同，而且與上面的995個中點均不相同，加上點E，共有2×995+1=1991個紅點x軸上橫坐標(biāo)分別為1，2，997的997個點就是滿足要求的例子 E2-035 A，B分別是坐標(biāo)平面上的格點的集合：A=（x，y）|x，y為正整數(shù)，1x20，1y20B=（x，y）|x，y為正整數(shù)，2x19，2y19A中的點分別染成紅色或藍(lán)色染成

7、紅色的點有219個，其中有180個包含于B中，又四個角上的點（1，1），（1，20），（20，1），（20，20）都染成藍(lán)色將水平或垂直方向上相鄰兩點按下列要求用紅、藍(lán)、黑色的線段連接起來：兩點均為紅色時，用紅線連接；兩點均為藍(lán)色時，用藍(lán)線連結(jié)；兩點為一紅一藍(lán)時，用黑線連結(jié)問：（長度為1的）黑線有237段時，（長度為1的）藍(lán)線有多少段？【題說】 1992年日本數(shù)學(xué)奧林匹克預(yù)選賽題9【解】 集合A中有400個點，其中紅點有219個，藍(lán)點有181個，在B內(nèi)有藍(lán)點144個A的四周有76個點，其中紅點39個，藍(lán)點37個（包括四個角上的點）每個角上的點引出2條線段；每個邊界上（除四個角）的點引出3條線段

8、；每個B內(nèi)的點引出4條線段因此，對于藍(lán)點共引出線段2×4+3×33+4×144=683（段）其中黑線有237段，所以藍(lán)線有683-237=446（段）這些藍(lán)線在上述計數(shù)時，被重復(fù)計算了一次，故實際上有藍(lán)線446÷2=223（段） E2-036 設(shè)集合A=1，2，10A到A的映射f滿足下列兩個條件：（1）對任意XA，f(30（x）=x；（2）對每個正整數(shù)k，1k29，至少存在一個aA，使得f(k（a）a其中f(1（x）=f（x），f(2（x）=f（f（x），f(k+1（x）=f（f(k（x），求這樣的映射的總數(shù)，【題說】 1992年日本數(shù)學(xué)奧林匹

9、克預(yù)選賽題12【解】 設(shè)A劃分成3個互不相交的子集：a1，a2，a3，a4，a5b1，b2，b3c1，c2并且定義映射f：f（a1）=a2，f（a2）=a3，f（a3）=a4，f（a4）=a5，f（a5）=a1；f（b1）=b2，f（b2）=b3，f（b3）=b1；f（c1）=c2，f（c2）=c15，3，2兩兩互素，30是它們的最小公倍數(shù)由條件知，f不是恒等映射，且 f由若干個循環(huán)組成，這些循環(huán)的階數(shù)的最小公倍數(shù)應(yīng)為30從而，f是滿足條件（1）、（2）的唯一一類映射所以，f的總數(shù)相當(dāng)于從10個元素中選取5個，再從剩余的5個中選3個，它們再分別進行循環(huán)排列的個數(shù)故所求映射的總數(shù)是 E

10、2-037  一副牌有 2n+ 1張，由一張王及標(biāo) 1至 n的牌每種各兩張組成這2n +1張排成一行，王在正中間，對每個k，1kn，兩張標(biāo)k的牌之間恰有k-1張牌確定所有不超過10并且有這種排法的n對哪些n，不可能這樣排？【題說】第二十四屆（1992年）加拿大數(shù)學(xué)奧林匹克題5【解】設(shè)標(biāo)i的牌，從左數(shù)起位置為ai與bi（aibi，i=1，2，n因為王牌位置為n+1，bi=i+ai，所以即因此4n（n+1）n=1，2，5，6，9，10不滿足上述要求n=3時，解為232J311n=4時，解為2423J4311n=7時，解為2723563J7546114n=8時，解為78426247J865

11、31135 E2-038  在4000至7000之間有多少個四個數(shù)字均不相同的偶數(shù)？【題說】第十一屆（1993年）美國數(shù)學(xué)邀請賽題1【解】答：728若千位數(shù)字為4或6，這時千位數(shù)字有2種選法，個位數(shù)字有4種選法，百位數(shù)字有8種選法，十位數(shù)字有7種選法所以共有2×4×8×7=448個數(shù)符合要求同理，若千位數(shù)字為5，有 1× 5× 8× 7= 280個偶數(shù)符合要求所以，共有448+280=728個 E2-039  令S為一個有6個元素的集合問有多少種不同的方法可以把S分成兩個不一定不同的子集，使得這

12、兩個子集的并恰好是S？兩子集的順序不必考慮，如a，c，b，c，d，e，f與b，c，d，e，f，a，c算一種分法【題說】第十一屆（1993年）美國數(shù)學(xué)邀請賽題8【解】365設(shè)S=AUB，S中每一個元素，或?qū)儆贏，或僅屬于B，或同時屬于A、B，共3種情況所以如果S中有n個元素，共有3n種方法選擇集合A和B除了A=B=S的情況，如果不計順序每種情形算了2次，所以共有種分法特別地，n=6時，共有365種分法E2-040  紅色和白色的椅子各有5張，圍成一個圓圈，共有多少種不同的排法？同色的椅子是沒有區(qū)別的，經(jīng)旋轉(zhuǎn)后排列的順序一致的排法只算1種【題說】1994年日本數(shù)學(xué)奧林匹克預(yù)選賽題7【解】將椅子的位置編號為09紅色椅子的位置是集合A=0，然有f(10（R