1981年~2019年全國(guó)高中數(shù)學(xué)聯(lián)賽試題分類匯編（15）組合與構(gòu)造（含答案）

PAGE1981年~2019年全國(guó)高中數(shù)學(xué)聯(lián)賽試題分類匯編組合與構(gòu)造部分2019A四、（本題滿分50分）設(shè)V是空間中2019個(gè)點(diǎn)構(gòu)成的集合，其中任意四點(diǎn)不共面．某些點(diǎn)之間連有線段，記E為這些線段構(gòu)成的集合．試求最小的正整數(shù)n，滿足條件：若E至少有n個(gè)元素，則E一定含有908個(gè)二元子集，其中每個(gè)二元子集中的兩條線段有公共端點(diǎn)，且任意兩個(gè)二元子集的交為空集．★解析：為了敘述方便，稱一個(gè)圖中的兩條相鄰的邊構(gòu)成一個(gè)“角”．先證明一個(gè)引理：設(shè)是一個(gè)簡(jiǎn)單圖，且是連通的，則含有個(gè)兩兩無公共邊的角（這里表示實(shí)數(shù)的整數(shù)部分）．引理的證明：對(duì)的元素個(gè)數(shù)歸納證明．當(dāng)時(shí)，結(jié)論顯然成立．下面假設(shè)，并且結(jié)論在較小時(shí)均成立．只需證明，在中可以選取兩條邊構(gòu)成一個(gè)角，在中刪去這兩條邊后，剩下的圖含有一個(gè)連通分支包含條邊．對(duì)這個(gè)連通分支應(yīng)用歸納假設(shè)即得結(jié)論成立．考慮中的最長(zhǎng)路，其中是互不相同的頂點(diǎn)．因?yàn)檫B通，故.情形1：,由于是最長(zhǎng)路，的鄰點(diǎn)均在中，設(shè)，其中．則是一個(gè)角，在中刪去這兩條邊．若處還有第三條邊，則剩下的圖是連通的；若處僅有被刪去的兩條邊，則成為孤立點(diǎn)，其余頂點(diǎn)仍互相連通．總之在剩下的圖中有一個(gè)連通分支含有條邊．情形2：，．則是一個(gè)角，在中刪去這兩條邊后，都成為孤立點(diǎn)，其余的點(diǎn)互相連通，因此有一個(gè)連通分支含有條邊．情形3：，，且與中某個(gè)點(diǎn)相鄰．則是一個(gè)角，在中刪去這兩條邊后，成為孤立點(diǎn)，其余點(diǎn)互相連通，因此有一個(gè)連通分支含有條邊．情形4：，，且與某個(gè)相鄰．由于是最長(zhǎng)路，故的鄰點(diǎn)均在之中．因是一個(gè)角，在中刪去這兩條邊，則是孤立點(diǎn)．若處僅有邊，則刪去所述邊后也是孤立點(diǎn)，而其余點(diǎn)互相連通．若處還有其他邊，，則刪去所述邊后，除外其余點(diǎn)互相連通．總之，剩下的圖中有一個(gè)連通分支含有.引理獲證．………………20分回到原題，題中的和可看作一個(gè)圖．首先證明．設(shè)．在中，首先兩兩連邊，再刪去其中條邊（例如），共連了條邊，則這個(gè)點(diǎn)構(gòu)成的圖是連通圖．再將剩余的個(gè)點(diǎn)配成對(duì)，每對(duì)兩點(diǎn)之間連一條邊，則圖中一共連了條線段．由上述構(gòu)造可見，G中的任何一個(gè)角必須使用相連的邊，因此至多有個(gè)兩兩無公共邊的角．故滿足要求的不小于．……30分另一方面，若，可任意刪去若干條邊，只考慮的情形．設(shè)有個(gè)連通分支，分別有個(gè)點(diǎn)，及條邊．下面證明中至多有個(gè)奇數(shù)．反證法，假設(shè)中有至少個(gè)奇數(shù)，由于是奇數(shù)，故中至少有981個(gè)奇數(shù)，故．不妨設(shè)都是奇數(shù)，顯然．令，則有（），，故，利用組合數(shù)的凸性，即對(duì)，有。可知當(dāng)由個(gè)以及一個(gè)構(gòu)成時(shí)，取得最大值．于是，這與①矛盾．從而中至多有979個(gè)奇數(shù)． ……40分對(duì)每個(gè)連通分支應(yīng)用引理，可知中含有個(gè)兩兩無公共邊的角，其中。綜上，所求最小的是． ……50分2019B四、（本題滿分50分）將一個(gè)凸邊形的每條邊任意染為紅、黃、藍(lán)三種顏色之一，每種顏色的邊各條．證明：可作這個(gè)凸邊形的條在內(nèi)部互不相交的對(duì)角線將其剖分成個(gè)三角形，并將所作的每條對(duì)角線也染為紅、黃、藍(lán)三種顏色之一，使得每個(gè)三角形的三條邊或者顏色全部相同，或者顏色互不相同．★證明：我們對(duì)歸納證明加強(qiáng)的命題：如果將凸邊形的邊染為三種顏色，并且三種顏色的邊均至少有一條，那么可作滿足要求的三角形剖分．…………10分當(dāng)時(shí)，若三種顏色的邊數(shù)為,由對(duì)稱性，只需考慮如下兩種情形，分別可作圖中所示的三角形剖分．若三種顏色的邊數(shù)為,由對(duì)稱性，只需考慮如下三種情形，分別可作圖中所示的三角形剖分．……20分假設(shè)結(jié)論對(duì)（）成立，考慮的情形，將凸邊形記為．情形1：有兩種顏色的邊各只有一條．不妨設(shè)色邊各只有一條．由于，故存在連續(xù)兩條邊均為色，不妨設(shè)是．作對(duì)角線，并將染為色，則三角形的三邊全部同色．此時(shí)凸邊形的三種顏色的邊均至少有一條，由歸納假設(shè)，可對(duì)其作符合要求的三角形剖分．………………30分情形2：某種顏色的邊只有一條，其余顏色的邊均至少兩條．不妨設(shè)色邊只有一條，于是可以選擇兩條相鄰邊均不是色，不妨設(shè)均不是色，作對(duì)角線，則有唯一的染色方式，使得三角形的三邊全部同色或互不同色．此時(shí)凸邊形的三種顏色的邊均至少有一條，由歸納假設(shè)，可對(duì)其作符合要求的三角形剖分．………………40分情形3：每種顏色的邊均至少兩條．作對(duì)角線，則有唯一的染色方式，使得三角形的三邊全部同色或互不同色．此時(shí)凸邊形的三種顏色的邊均至少有一條，由歸納假設(shè)，可對(duì)其作符合要求的三角形剖分．綜合以上種情形，可知的情形下結(jié)論也成立．由數(shù)學(xué)歸納法，結(jié)論獲證．………………50分2017A三、（本題滿分50分）將方格紙中每個(gè)小方格染三種顏色之一，使得每種顏色的小方格的個(gè)數(shù)相等。若相鄰兩個(gè)小方格的顏色不同，則稱他們的公共邊為“分割邊”。試求分割邊條數(shù)的最小值?！锝馕觯河浄指钸叺臈l數(shù)為.首先，將方格紙按如圖所示分成三個(gè)區(qū)域，分別染成三種顏色，粗線上均為分割邊，此時(shí)共有56條分割邊，即。下面證明.將方格紙的行從上至下依次記為,,,列從左至右依次記為,,,行中方格出現(xiàn)的顏色數(shù)記為，列中方格出現(xiàn)的顏色數(shù)記為，三種顏色分別記為，，，對(duì)于一種顏色，設(shè)是表示含有色方格的函數(shù)與列數(shù)之和.記，同理定義，則①由于染色的方格有個(gè)，設(shè)含有色方格的行有個(gè)，列有個(gè)，則色方格一定在這行和列的交叉方格中，因此.從而即.②由于在行中有種顏色的方格，因此至少有條分割邊，同理在行中有種顏色的方格，因此至少有條分割邊，于是，③下面分兩種情形討論.⑴當(dāng)有一行或有一列全部方格同色時(shí)，不妨設(shè)有一行全為色，從而方格紙的33列中均含有的方格，由于的方格有363個(gè)，故至少有行中含有色方格。于是。④由①③④得⑵沒有一行或沒有一列全部方格同色時(shí)，則對(duì)任意，均有，，從而由②知，綜上可知，分割邊條數(shù)的最小值為。2017A四、（本題滿分50分）。設(shè)均是大于的整數(shù)，，是個(gè)不超過的互不相同的正整數(shù)，且互素。證明：對(duì)任意實(shí)數(shù)，均存在一個(gè)（），使得，這里表示實(shí)數(shù)到它最近的整數(shù)的距離。★證明：首先證明兩個(gè)引理：引理1：存在整數(shù)，滿足，并且，.由于互素，即，有裴蜀定理，存在整數(shù)，滿足。①下面證明，通過調(diào)整，存在一組滿足①，且，記，。如果，那么存在，于是，又是大于1的整數(shù)，故由①可知，存在，令，，（，），則，②并且，，所以，如果，則存在，因此有一個(gè).令，，（，），那么②成立，并且，與上面類似可以證明到：，，即說明與均是非負(fù)整數(shù)，故通過有限次上述的調(diào)整，可以得到一組使得①成立，并且結(jié)論獲證。引理2：①對(duì)任意的實(shí)數(shù)，均有；②對(duì)任意整數(shù)和實(shí)數(shù)，有；由于對(duì)任意整數(shù)和實(shí)數(shù)，均有，于是不妨設(shè)，此時(shí)，，若，不妨設(shè)，則，從而若，不妨設(shè)同號(hào)，則當(dāng)時(shí)，有，此時(shí)；當(dāng)時(shí)，注意到總有，故；故①得證；又，由①知，②是成立的。接下來回到原題，由結(jié)論①存在整數(shù)，滿足，并且，.于是，，由引理2得，因此，③若，則由③知，若，則在中存在兩個(gè)相鄰的正整數(shù)。不妨設(shè)相鄰，則，故與中有一個(gè)不小于。綜上，總存在存在一個(gè)（），使得2016A三、（本題滿分50分）給定空間個(gè)點(diǎn)，其中任意四點(diǎn)不在一個(gè)平面上。將某些點(diǎn)之間用線段相連，若得到的圖形中沒有三角形也沒有空間四邊形，試確定所連線段數(shù)目的最大值?！锝馕觯阂赃@10個(gè)點(diǎn)為頂點(diǎn)，所連線段為邊，得到一個(gè)10階簡(jiǎn)單圖G，下證明G的變數(shù)不超過15.設(shè)G的頂點(diǎn)為，一共有條邊，用表示頂點(diǎn)的度。若對(duì)都成立，則。假設(shè)存在滿足，不妨設(shè)，且與均相鄰.于是之間沒有邊，否則就成三角形，所以與之間恰有條邊.對(duì)每個(gè)（），至多與中的一個(gè)頂點(diǎn)相鄰（否則設(shè)與，（）相鄰，則，，，就對(duì)應(yīng)了一個(gè)空間四邊形的四個(gè)頂點(diǎn)，這與題意矛盾），從而與之間的邊數(shù)至多條。在這個(gè)頂點(diǎn)之間，由于沒有三角形，由托蘭定理，至多條邊，因此G的邊數(shù)例如如圖所示的就有條邊，且滿足要求。綜上所述，所連線段數(shù)目的最大值為。2014B四、（本題滿分50分）設(shè)是一個(gè)邊長(zhǎng)為的等邊三角形，在的內(nèi)部和邊界上任取個(gè)點(diǎn).(1)證明：一定存在兩個(gè)點(diǎn)，它們之間的距離小于或等于；（20分）(2)證明：一定存在兩個(gè)點(diǎn)，它們之間的距離嚴(yán)格小于；（30分）★證明：(1)如左下圖1，我們將分成個(gè)邊長(zhǎng)為的小等邊三角形；對(duì)于中間的圖2中六個(gè)灰色的小三角形，我們將它們剖分成三個(gè)全等的三角形；這樣，我們就可以看出就可以被右圖3的個(gè)正六邊形所覆蓋。圖1圖2圖3不難看出，這里的個(gè)正六邊形的直徑為，它們可以被看做只“抽屜”，對(duì)于三角形內(nèi)部和邊界上任取個(gè)點(diǎn)，根據(jù)抽屜原理，至少有一個(gè)正六邊形包含兩個(gè)點(diǎn)。而在這個(gè)正六邊形中，任意兩點(diǎn)間的距離不超過，這樣便證明了我們所要的結(jié)論。（要注意，我們的抽屜的構(gòu)造并不是唯一的，我們還可以用下圖4所示的個(gè)直徑為的圓覆蓋，也可以得到同樣的結(jié)論）圖4圖5(2)這部分要求證明的是嚴(yán)格不等號(hào)。我們要證明在個(gè)點(diǎn)中存在兩個(gè)點(diǎn)，他們間的距離嚴(yán)格小于，注意到直徑為的正六邊形中，間距恰好為的兩個(gè)點(diǎn)一定是距離最遠(yuǎn)的一對(duì)點(diǎn)，另一方面，上面所構(gòu)造的正六邊形抽屜在邊和頂點(diǎn)處是由重復(fù)的，我們通過指定一條邊或者頂點(diǎn)屬于那一個(gè)特定的正六邊形來改造我們的“抽屜”，使得每一個(gè)抽屜不包含正六邊形中距離為的頂點(diǎn)對(duì)，當(dāng)然，在目前的情況我們只需關(guān)心怎么改造頂點(diǎn)即可。我們?cè)诿恳粋€(gè)正六邊形抽屜上去掉一些頂點(diǎn)，使得每一個(gè)抽屜不在包含正六邊形中距離為的頂點(diǎn)對(duì)，如圖5就是一個(gè)辦法，圖中空心的點(diǎn)表示正六邊形中去掉該點(diǎn)，不難看出，這樣的改造還是覆蓋了原來得三角形，且每一個(gè)抽屜不在包含正六邊形中距離為的頂點(diǎn)對(duì)，根據(jù)抽屜原理，我們就證明了：任取個(gè)點(diǎn)，一定存在兩個(gè)點(diǎn)，它們之間的距離嚴(yán)格小于。（這樣的抽屜構(gòu)造也是不唯一的）2013B四、（本題滿分50分）用若干單位小正方形和由三個(gè)單位小方格組成的形“磚”鋪滿一個(gè)的方格棋盤的所有不同可能鋪法的數(shù)目是．下面的圖是時(shí)的兩種不同的鋪法：⑴求；⑵求的個(gè)位數(shù)．★證明：由題意顯然，，當(dāng)時(shí)，我們從左向右地鋪的方格棋盤，無論哪一種鋪法，至多鋪到，我們一定會(huì)完成一個(gè)（）的矩形。這樣我們計(jì)算時(shí)，就可以去尋找與的關(guān)系，又由下圖我們得到⑴由，，得，,,依次下去可得⑵由，，，，可知，一定是奇數(shù)。我們由計(jì)算，對(duì)每一個(gè)，我們有：(,,,,,,,,,,,,,,,,,,,,,,,,),,,,,,…可知，的個(gè)位數(shù)的周期是。而，又等于的奇數(shù)也一定等于，所以的個(gè)位數(shù)為。2012A三、（本題滿分50分）設(shè)是平面上個(gè)點(diǎn)，它們兩兩間的距離的最小值為，求證：★證明：證法一:不妨設(shè)先證明:對(duì)任意正整數(shù),都有顯然,對(duì)均成立,只有時(shí)右邊取等號(hào)……10分所以,只要證明當(dāng)時(shí),有即可.以為圓心,為半徑畫個(gè)圓,它們兩兩相離或外切;以圓心，為半徑畫圓，這個(gè)圓覆蓋上述個(gè)圓‥‥‥‥‥‥‥20分所以‥‥‥‥‥‥‥30分由易知‥‥‥‥‥‥‥‥‥‥‥‥‥‥40分所以對(duì)時(shí)也成立.綜上,對(duì)任意正整數(shù)都有.因而‥‥‥‥‥‥‥‥‥‥‥‥50分證法二:不妨設(shè)以為圓心,為半徑畫個(gè)圓,它們兩兩相離或外切;‥‥‥10分設(shè)是是圓上任意一點(diǎn),由于‥‥‥‥‥‥‥‥‥‥20分因而,以為圓心,為半徑的圓覆蓋上述個(gè)圓‥‥‥‥‥‥‥‥‥30分故‥‥‥‥‥‥‥‥‥40分所以‥‥‥‥‥‥‥‥‥‥‥50分2011A三、（本題滿分50分）設(shè)是給定的正實(shí)數(shù)，．對(duì)任意正實(shí)數(shù)，滿足的三元數(shù)組的個(gè)數(shù)記為．證明：．★證明：對(duì)給定的，滿足，且①的三元數(shù)組的個(gè)數(shù)記為．注意到，若固定，則顯然至多有一個(gè)使得①成立．因，即有種選法，故．同樣地，若固定，則至多有一個(gè)使得①成立．因，即有種選法，故．從而．因此，當(dāng)為偶數(shù)時(shí)，設(shè)，則有．當(dāng)為奇數(shù)時(shí)，設(shè)，則有．綜上所述，．2011A四、（本題滿分50分）設(shè)A是一個(gè)的方格表，在每一個(gè)小方格內(nèi)各填一個(gè)正整數(shù)．稱A中的一個(gè)方格表為“好矩形”，若它的所有數(shù)的和為10的倍數(shù)．稱A中的一個(gè)的小方格為“壞格”，若它不包含于任何一個(gè)“好矩形”．求A中“壞格”個(gè)數(shù)的最大值．★解析：首先證明A中“壞格”不多于25個(gè)．用反證法．假設(shè)結(jié)論不成立，則方格表中至多有1個(gè)小方格不是“壞格”．由表格的對(duì)稱性，不妨假設(shè)此時(shí)第1行都是“壞格”．設(shè)方格表第列從上到下填的數(shù)依次為．記，這里．我們證明：三組數(shù)；及都是模10的完全剩余系．事實(shí)上，假如存在，使，則，即第1行的第至第列組成一個(gè)“好矩形”，與第1行都是“壞格”矛盾．又假如存在，使，則，即第2行至第3行、第列至第列組成一個(gè)“好矩形”，從而至少有2個(gè)小方格不是“壞格”，矛盾．類似地，也不存在，使．因此上述斷言得證．故，所以，矛盾！故假設(shè)不成立，即“壞格”不可能多于25個(gè)．另一方面，構(gòu)造如下一個(gè)的方格表，可驗(yàn)證每個(gè)不填10的小方格都是“壞格”，此時(shí)有25個(gè)“壞格”．11121111101111111111111011112綜上所述，“壞格”個(gè)數(shù)的最大值是25．2011B四、（本題滿分50分）給定個(gè)不同實(shí)數(shù)，其所有全排列組成的集合為.對(duì)于，若恰有兩個(gè)不同的整數(shù)使得成立，則稱該排列為“好排列”.求中“好排列”的個(gè)數(shù).★解析：首先定義：對(duì)于中的一個(gè)排列，如果滿足，則稱該排列為自然排列；對(duì)于中的一個(gè)排列，如果有整數(shù)，使得則稱和構(gòu)成一個(gè)“相鄰逆序”；對(duì)于，如果它恰有一個(gè)“相鄰逆序”，則稱該排列為“一階好排列”，中所有“一階好排列”的個(gè)數(shù)記為；如果它恰有兩個(gè)“相鄰逆序”，則稱該排列為“二階好排列”，中所有“二階好排列”的個(gè)數(shù)記為；依題意知，恰好是要求的中“好排列”的個(gè)數(shù)。由題意知：，，，。以下為了敘述簡(jiǎn)便，我們把由給定的個(gè)不同實(shí)數(shù)的所有全排列構(gòu)成的集合記為（），其次求。我們先來考察與之間的遞推關(guān)系。對(duì)中的每一個(gè)“一階好排列”（記為），我們考慮從中取出最大的數(shù)后剩下的個(gè)數(shù)按原來的順序構(gòu)成的排列（記為）。如果排列是中的“一階好排列”，且“相鄰逆序”為，那么，在排列中，的位置只能在之間或最后；如果排列不是中的“一階好排列”，則排列中的“相鄰逆序”的個(gè)數(shù)不為，顯然排列中“相鄰逆序”的個(gè)數(shù)不能大于（否則，排列不是“一階好排列”，理由是：因?yàn)槭亲畲蟮臄?shù)，所以排列中“相鄰逆序”的個(gè)數(shù)一定不少于排列中“相鄰逆序”的個(gè)數(shù)），從而排列中“相鄰逆序”的個(gè)數(shù)為，此時(shí)排列是一個(gè)自然排列，而排列是“一階好排列”，所以的位置不能在最后（有種可能的位置）。綜合上面的分析可知：，即，所以，即。最后求。我們先來考察與之間的遞推關(guān)系。對(duì)中的每一個(gè)“二階好排列”（記為），我們考慮從中取出最大的數(shù)后剩下的個(gè)數(shù)按原來的順序構(gòu)成的排列（記為）。如果排列是中的“二階好排列”，且“相鄰逆序”為，，那么在排列中，的位置只能在之間或之間，或者排在最后；如果排列不是中的“二階好排列”，則它一定是中的“一階好排列”，設(shè)“相鄰逆序”為，因?yàn)榕帕惺恰岸A好排列”，所以的位置不能在之間，也不能排在最后，其余位置都行，有種可能。綜合上面分析可知：，又，所以，變形為所以，即，因此中“好排列”的個(gè)數(shù)為個(gè)。2010A四、（本題滿分50分）一種密碼鎖的密碼設(shè)置是在正邊形的每個(gè)頂點(diǎn)處賦值和兩個(gè)數(shù)中的一個(gè)，同時(shí)在每個(gè)頂點(diǎn)處染紅、藍(lán)兩種顏色之一，使得任意相鄰的兩個(gè)頂點(diǎn)的數(shù)字或顏色中至少有一個(gè)相同.問：這種密碼鎖共有多少種不同的密碼設(shè)置?！锝馕觯簩?duì)于該種密碼鎖的一種密碼設(shè)置，如果相鄰兩個(gè)頂點(diǎn)上所賦值的數(shù)字不同，在它們所在的邊上標(biāo)上a，如果顏色不同，則標(biāo)上b，如果數(shù)字和顏色都相同，則標(biāo)上c．于是對(duì)于給定的點(diǎn)上的設(shè)置（共有4種），按照邊上的字母可以依次確定點(diǎn)上的設(shè)置．為了使得最終回到時(shí)的設(shè)置與初始時(shí)相同，標(biāo)有a和b的邊都是偶數(shù)條．所以這種密碼鎖的所有不同的密碼設(shè)置方法數(shù)等于在邊上標(biāo)記a，b，c，使得標(biāo)有a和b的邊都是偶數(shù)條的方法數(shù)的4倍．設(shè)標(biāo)有a的邊有條，，標(biāo)有b的邊有條，．選取條邊標(biāo)記a的有種方法，在余下的邊中取出條邊標(biāo)記b的有種方法，其余的邊標(biāo)記c．由乘法原理，此時(shí)共有種標(biāo)記方法．對(duì)i，j求和，密碼鎖的所有不同的密碼設(shè)置方法數(shù)為．①這里我們約定．當(dāng)n為奇數(shù)時(shí)，，此時(shí)．②代入①式中，得．當(dāng)n為偶數(shù)時(shí)，若，則②式仍然成立；若，則正n邊形的所有邊都標(biāo)記a，此時(shí)只有一種標(biāo)記方法．于是，當(dāng)n為偶數(shù)時(shí)，所有不同的密碼設(shè)置的方法數(shù)為．綜上所述，這種密碼鎖的所有不同的密碼設(shè)置方法數(shù)是：當(dāng)n為奇數(shù)時(shí)有種；當(dāng)n為偶數(shù)時(shí)有種．2009*四、（本題滿分50分）在非負(fù)數(shù)構(gòu)成的數(shù)表中每行的數(shù)互不相同，前列中每列的三數(shù)之和為，，均大于。如果的前三列構(gòu)成的數(shù)表滿足如下性質(zhì)（）：對(duì)于數(shù)表中任意一列（）均存在某個(gè)使得⑶。求證：⑴最小值，一定來自數(shù)表的不同列；⑵存在數(shù)表中唯一的一列，，使得數(shù)表仍然具有性質(zhì)（）?！镒C明：（i）假設(shè)最小值不是取自數(shù)表的不同列。則存在一列不含任何.不妨設(shè)由于數(shù)表P中同一行中的任何兩個(gè)元素都不等，于是另一方面，由于數(shù)表具有性質(zhì)（），在（3）中取=2，則存在某個(gè)使得.矛盾。(ii)由抽屜原理知中至少有兩個(gè)值取在同一列。不妨設(shè).由前面的結(jié)論知數(shù)表的第一列一定含有某個(gè)，所以只能是.同樣，第二列中也必含某個(gè)不妨設(shè).于是，即是數(shù)表中的對(duì)角線上數(shù)字：記M=｛1，2，...，9｝，令集合顯然且.因?yàn)?，所?故.于是存在使得.顯然，下面證明數(shù)表具有性質(zhì)（）.從上面的選法可知這說明又由滿足性質(zhì)（），在（3）中取，推得于是下證對(duì)任意的存在某個(gè)使得.假若不然，則且.這與的最大性矛盾。因此，數(shù)表滿足性質(zhì)（）。下證唯一性。設(shè)有使得數(shù)表，具有性質(zhì)（）.不失一般性，我們假定（4），。由于，，及（i），有又由（i)知：或者，或者如果成立，由數(shù)表具有性質(zhì)（），則，（5），由數(shù)表滿足性質(zhì)（），則對(duì)于至少存在一個(gè)使得，又由（4），（5）式知，所以只能有同樣由數(shù)表滿足性質(zhì)（），可推得于是，即數(shù)表·如果成立，則，，（6），由數(shù)表滿足性質(zhì)（），對(duì)于，存在某個(gè)使得，由及（4）和（6）式知，于是只能有類似地，由滿足性質(zhì)（）及可推得，從而。2007*二、（本題滿分40分）。如圖所示，在的長(zhǎng)方形棋盤的每個(gè)小方格的中心點(diǎn)各放一個(gè)棋子。如果兩個(gè)棋子所在的小方格共邊或者共頂點(diǎn)，那么稱這兩個(gè)棋子相連?，F(xiàn)從這個(gè)棋子中取出一些，使得棋盤上剩下的棋子，沒有五個(gè)在一條直線（橫豎斜方向）上依次相連。問最少取出多少個(gè)棋子才能滿足要求？并說明理由?！锝馕觯航猓鹤钌僖〕?1個(gè)棋子，才可能滿足要求。其原因如下：如果一個(gè)方格在第i行第j列，則記這個(gè)方格為(i，j)。第一步證明若任取10個(gè)棋子，則余下的棋子必有一個(gè)五子連珠，即五個(gè)棋子在一條直線（橫、豎、斜方向）上依次相連。用反證法。假設(shè)可取出10個(gè)棋子，使余下的棋子沒有一個(gè)五子連珠。如圖1，在每一行的前五格中必須各取出一個(gè)棋子，后三列的前五格中也必須各取出一個(gè)棋子。這樣，10個(gè)被取出的棋子不會(huì)分布在右下角的陰影部分。同理，由對(duì)稱性，也不會(huì)分布在其他角上的陰影部分。第1、2行必在每行取出一個(gè)，且只能分布在(1，4)、(1，5)、(2，4)、(2，5)這些方格。同理(6，4)、(6，5)、(7，4)、(7，5)這些方格上至少要取出2個(gè)棋子。在第1、2、3列，每列至少要取出一個(gè)棋子，分布在(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個(gè)棋子。這樣，在這些區(qū)域內(nèi)至少已取出了10個(gè)棋子。因此，在中心陰影區(qū)域內(nèi)不能取出棋子。由于①、②、③、④這4個(gè)棋子至多被取出2個(gè)，從而，從斜的方向看必有五子連珠了。矛盾。 圖1 圖2第二步構(gòu)造一種取法，共取走11個(gè)棋子，余下的棋子沒有五子連珠。如圖2，只要取出有標(biāo)號(hào)位置的棋子，則余下的棋子不可能五子連珠。綜上所述，最少要取走11個(gè)棋子，才可能使得余下的棋子沒有五子連珠。2005*12、如果自然數(shù)的各位數(shù)字之和等于，那么稱為“吉祥數(shù)”.將所有吉祥數(shù)從小到大排成一列，若，則◆答案：★解析：因?yàn)榉匠痰姆秦?fù)整數(shù)解的個(gè)數(shù)為，而使，（）的整數(shù)解個(gè)數(shù)為?，F(xiàn)取，可知，位吉祥數(shù)的個(gè)數(shù)為因?yàn)槭切稳绲臄?shù)中最小的一個(gè)吉祥數(shù)，且，，，對(duì)四位吉祥數(shù)，其個(gè)數(shù)為滿足的非負(fù)整數(shù)解的個(gè)數(shù)，即個(gè)。又是第個(gè)吉祥數(shù)，即，從而，。又，，而所以從大到小最后六個(gè)五位吉祥數(shù)依次是，所以第個(gè)吉祥數(shù)是，即2003*三、（本題滿分50分）。由個(gè)點(diǎn)和這些點(diǎn)之間的條連線段組成一個(gè)空間圖形，其中，，，。已知此圖中任四點(diǎn)不共面，每點(diǎn)至少有一條連線段，存在一點(diǎn)至少有條連線段．證明：圖中必存在一個(gè)空間四邊形(即由四點(diǎn)和四條連線段組成的圖形)．★證明：證明：設(shè)點(diǎn)集為，與連線的點(diǎn)集為，且．于是．又顯然有，．若存在一點(diǎn)與其余點(diǎn)都連線，不妨設(shè)．則中個(gè)點(diǎn)的連線數(shù)(注意：)．(由)但若在這個(gè)點(diǎn)內(nèi)，沒有任一點(diǎn)同時(shí)與其余兩點(diǎn)連線，則這個(gè)點(diǎn)內(nèi)至多連線條，故在中存在一點(diǎn)，它與兩點(diǎn)、(互不相等，且)連了線，于是連成四邊形．現(xiàn)設(shè)任一點(diǎn)連的線數(shù)．且設(shè)．且設(shè)圖中沒有四邊形．于是當(dāng)時(shí)，與沒有公共的點(diǎn)對(duì)，即()．記，則由，得()，且當(dāng)且時(shí)，與無公共點(diǎn)對(duì)．從而中點(diǎn)對(duì)個(gè)數(shù)．即(由平均不等式)(注意)，即得到(兩邊同乘以)即．(注意到)得．(各取部分因數(shù)比較)①又②（這里用到前面所得到的式子，）③（這里也用到前面所得到的式子，）又、、、均為正整數(shù)，從而由②、③得，④由①、④矛盾，知原命題成立．又證：畫一個(gè)表格，記題中個(gè)點(diǎn)為，若與連了線，則將表格中第行列的方格中心涂紅．于是表中共有個(gè)紅點(diǎn)，當(dāng)時(shí)，則表格中的行及列各有個(gè)紅點(diǎn)．且表格的主對(duì)角線上的方格中心都沒有涂紅．由已知，表格中必有一行有個(gè)紅點(diǎn)．不妨設(shè)最后一行前格為紅點(diǎn)．其余格則不為紅點(diǎn)(若有紅點(diǎn)則更易證)，于是：?jiǎn)栴}轉(zhuǎn)化為：證明存在四個(gè)紅點(diǎn)是一個(gè)邊平行于格線的矩形頂點(diǎn)．若否，則表格中任何四個(gè)紅點(diǎn)其中心都不是一個(gè)邊平行于格線的矩形頂點(diǎn)．于是，前行的前個(gè)方格中，每行至多有個(gè)紅點(diǎn)．去掉表格的第行及前列，則至多去掉個(gè)紅點(diǎn)．于是在余下方格表中，至少有個(gè)紅點(diǎn)．設(shè)此表格中第行有()個(gè)紅點(diǎn)，于是，同行的紅點(diǎn)點(diǎn)對(duì)數(shù)的總和為．其中．(由于當(dāng)時(shí)，，故當(dāng)紅點(diǎn)總數(shù)為個(gè)時(shí)，可取行每行取個(gè)紅點(diǎn)，行每行取個(gè)紅點(diǎn)時(shí)取最小值，由下證可知紅點(diǎn)數(shù)多于此數(shù)時(shí)更有利于證明．)，但．由假設(shè)，不存在處在不同行的2個(gè)紅點(diǎn)對(duì)，使此四點(diǎn)兩兩同列，所以，有(由于去掉了列，故還余列，不同的列對(duì)數(shù)為)即，所以．即即顯然矛盾．故證．2001*三、（本題滿分50分）)將邊長(zhǎng)為正整數(shù)m，n的矩形劃分成若干邊長(zhǎng)均為正整數(shù)的正方形．每個(gè)正方形的邊均平行于矩形的相應(yīng)邊．試求這些正方形邊長(zhǎng)之和的最小值．★解析：記所求最小值為，我們可以證明．(*)其中表示和的最大公約數(shù)．事實(shí)上，不妨設(shè)，(1)關(guān)于歸納，可以證明存在一合乎題意的分法，使所得正方形邊長(zhǎng)之和恰為． 當(dāng)時(shí),命題顯然成立． 假設(shè)當(dāng)時(shí)，結(jié)論成立（）．當(dāng)時(shí)，若，則命題顯然成立．若，從矩形中切去正方形（如圖），由歸納假設(shè)矩形有一種分法使得所得正方形邊長(zhǎng)之和恰為.于是原矩形有一種分法使得所得正方形邊長(zhǎng)之和為。(2)關(guān)于歸納可以證明(*)成立．當(dāng)時(shí),由于，顯然．假設(shè)當(dāng)m≤k時(shí)，對(duì)任意1≤n≤m有f(m，n)=m+n-(m，n)．若，當(dāng)時(shí)顯然)．當(dāng)時(shí)，設(shè)矩形按要求分成了個(gè)正方形，其邊長(zhǎng)分別為，不妨設(shè)．顯然或．若，則在與之間的與平行的任一直線至少穿過二個(gè)分成的正方形（或其邊界），于是不小于與之和．所以．若，則一個(gè)邊長(zhǎng)分別為和的矩形可按題目要求分成邊長(zhǎng)分別為的正方形，由歸納假設(shè)。從而．于是當(dāng)時(shí)，．再由(1)可知。1997*三、（本題滿分50分）在的長(zhǎng)方形表格中每一格填入一個(gè)非負(fù)實(shí)數(shù)，第行第列中填入的數(shù)為（，）如表，然后將表每列中的數(shù)按從小到大的次序從上到下重新排列為（）。如表。求最小的自然數(shù)，使得只要表中填入的數(shù)滿足（），則當(dāng)時(shí)，在表中就能保證?！锝馕觯涸诒?中，取()，其余各數(shù)均取，于是，每列各數(shù)之和均等于．但重新填入后，前行之和均等于．第行之和等于．故．反之，如果表中第行的個(gè)數(shù)涂黃，行共個(gè)數(shù)涂紅，則這些涂紅的數(shù)在表中至多分布在行中，于是除這行外的其余各行中的每個(gè)數(shù)都不小于同列中涂黃的數(shù)，即涂黃個(gè)數(shù)的和≤沒有涂紅數(shù)的行的每一行數(shù)的和≤1．于是表2中第行的數(shù)的和≤1，故第行的數(shù)的和≤1．即能保證表2中第行的數(shù)的和≤1．∴．1996*四、（本題滿分35分）有（）個(gè)人聚會(huì)，已知：⑴每人至少同其中個(gè)人互相認(rèn)識(shí)；⑵對(duì)于其中任意個(gè)人，或者其中有人相識(shí)，或者余下的任中有人相識(shí)。證明：這個(gè)人中必有三人兩兩相識(shí)?！镒C明：作一個(gè)圖，用個(gè)點(diǎn)表示這個(gè)人，凡二人認(rèn)識(shí)，則在表示此二人的點(diǎn)間連一條線．問題即，在題設(shè)條件下，存在以這點(diǎn)中的某三點(diǎn)為頂點(diǎn)的三角形．設(shè)點(diǎn)連線條數(shù)最多，在與連線的所有點(diǎn)中點(diǎn)連線最多，與連線的點(diǎn)除外的集合為，與連線的點(diǎn)除外的集合為．1°設(shè)，則每點(diǎn)至少連條線，中都至少有個(gè)點(diǎn)．⑴若存在一點(diǎn)，與都連線，則滿足要求；⑵若沒有任何兩點(diǎn)與此二點(diǎn)都連線(圖1)，則由，，，故得，且圖中每點(diǎn)都連條線．若(或)中存在兩點(diǎn)，這兩點(diǎn)間連了一條線，則此二點(diǎn)與連出三角形，若中任何兩點(diǎn)間均未連線，中任兩點(diǎn)也未連線，則中不存在兩點(diǎn)連線，中也不存在兩點(diǎn)連線．與已知矛盾．2°設(shè)．則每點(diǎn)至少連條線，中都至少有個(gè)點(diǎn)．⑴若存在一點(diǎn)，與都連線，則滿足要求；⑵若沒有任何兩點(diǎn)與此二點(diǎn)都連線，且，則由時(shí)(圖2)，則由，，，，故得，，，若(或)中存在兩點(diǎn)，這兩點(diǎn)間連了一條線，則此二點(diǎn)與連出三角形，若中任何兩點(diǎn)間均未連線，中任兩點(diǎn)也未連線，則中不存在兩點(diǎn)連線，中也不存在兩點(diǎn)連線．與已知矛盾．⑶若沒有任何兩點(diǎn)與此二點(diǎn)都連線，且，即每點(diǎn)都只連條線．這時(shí)，必有一點(diǎn)與均未連線，設(shè)為．與中個(gè)點(diǎn)連線，與中個(gè)點(diǎn)連線，，且．否則若，則中各點(diǎn)均未連線，中各點(diǎn)也未連線．矛盾．故．且由于，即中至少有一個(gè)，不妨設(shè)，現(xiàn)任取中與連線的一點(diǎn)，由于與中其余各點(diǎn)均未連線，若與中的所有與連線的點(diǎn)均未連線，則連線數(shù)，矛盾，故至少與此個(gè)點(diǎn)中的一點(diǎn)連線．故證．1995*四、（本題滿分35分）將平面上的每個(gè)點(diǎn)都以紅，藍(lán)兩色之一著色。證明：存在這樣兩個(gè)相似的三角形，它們的相似比為，并且每一個(gè)三角形的三個(gè)頂點(diǎn)同色。★證明：首先證明平面上一定存在三個(gè)頂點(diǎn)同色的直角三角形．任取平面上的一條直線，則直線上必有兩點(diǎn)同色．設(shè)此兩點(diǎn)為，不妨設(shè)同著紅色．過作直線的垂線、，若或上有異于的點(diǎn)著紅色，則存在紅色直角三角形．若、上除外均無紅色點(diǎn)，則在上任取異于P的兩點(diǎn)，則必著藍(lán)色，過R作的垂線交于T，則T必著藍(lán)色．即為三頂點(diǎn)同色的直角三角形．設(shè)直角三角形三頂點(diǎn)同色(為直角)．把補(bǔ)成矩形(如圖)．把矩形的每邊都分成等分(為正奇數(shù)，，本題中取)．連結(jié)對(duì)邊相應(yīng)分點(diǎn)，把矩形分成個(gè)小矩形．邊上的分點(diǎn)共有個(gè)，由于為奇數(shù)，故必存在其中兩個(gè)相鄰的分點(diǎn)同色，(否則任兩個(gè)相鄰分點(diǎn)異色，則可得異色)，不妨設(shè)相鄰分點(diǎn)同色．考察所在的小矩形的另兩個(gè)頂點(diǎn)，若異色，則或?yàn)槿齻€(gè)頂點(diǎn)同色的小直角三角形．若同色，再考察以此二點(diǎn)為頂點(diǎn)而在其左邊的小矩形，…．這樣依次考察過去，不妨設(shè)這一行小矩形的每條豎邊的兩個(gè)頂點(diǎn)都同色．同樣，邊上也存在兩個(gè)相鄰的頂點(diǎn)同色，設(shè)為，則考察所在的小矩形，同理，若所在小矩形的另一橫邊兩個(gè)頂點(diǎn)異色，則存在三頂點(diǎn)同色的小直角三角形．否則，所在列的小矩形的每條橫邊兩個(gè)頂點(diǎn)都同色．現(xiàn)考察所在行與所在列相交的矩形，如上述，都與同色，為頂點(diǎn)同色的直角三角形．由，故，且相似比為，且這兩個(gè)直角三角形的頂點(diǎn)分別同色．證明2：首先證明：設(shè)為任意正實(shí)數(shù)，存在距離為的同色兩點(diǎn)．任取一點(diǎn)(設(shè)為紅色點(diǎn))，以為圓心，為半徑作圓，若圓上有一個(gè)紅點(diǎn)，則存在距離為的兩個(gè)紅點(diǎn)，若圓上沒有紅點(diǎn)，則任一圓內(nèi)接六邊形的六個(gè)頂點(diǎn)均為藍(lán)色，但此六邊形邊長(zhǎng)為．故存在距離為的兩個(gè)藍(lán)色點(diǎn)．下面證明：存在邊長(zhǎng)為，，的直角三角形，其三個(gè)頂點(diǎn)同色．如上證，存在距離為的同色兩點(diǎn)(設(shè)為紅點(diǎn))，以為直徑作圓，并取圓內(nèi)接六邊形，若中有任一點(diǎn)為紅色，則存在滿足要求的紅色三角形．若為藍(lán)色，則存在滿足要求的藍(lán)色三角形．下面再證明本題：由上證知，存在邊長(zhǎng)為，，及的兩個(gè)同色三角形，滿足要求．證明3：以任一點(diǎn)為圓心，及為半徑作兩個(gè)同心圓，在小圓上任取9點(diǎn)，必有5點(diǎn)同色，設(shè)為，作射線，交大圓于，則此五點(diǎn)中必存在三點(diǎn)同色，設(shè)為．則與為滿足要求的三角形．1994*四、（本題滿分35分）給定平面上的點(diǎn)集，中任意三點(diǎn)均不共線，將中的所有的點(diǎn)任意分成組，使得每組至少有個(gè)點(diǎn)，且每點(diǎn)恰好屬于一組，然后黃在同一組的任意兩點(diǎn)用一條線段相連，不在同一組的兩點(diǎn)不連線段，這樣得到一個(gè)圖案，不同的分組方式得到不同的圖案，將圖案中所含的以中的點(diǎn)為頂點(diǎn)的三角形個(gè)數(shù)記為。⑴求的最小值；⑵設(shè)是的一個(gè)圖案，若中的線段（指以的點(diǎn)為端點(diǎn)的線段）用種顏色染色，每條線段恰好染一種顏色。證明：存在一個(gè)染色方案，使染色后不含以的點(diǎn)為頂點(diǎn)的三邊顏色相同的三角形?！镒C明：設(shè)中分成的個(gè)子集的元素個(gè)數(shù)分別為()，．且．則．即求此式的最小值．設(shè)．即．則．這就是說，當(dāng)與的差大于1時(shí)，可用及代替與，而其余的數(shù)不變．此時(shí)，的值變?。谑强芍?，只有當(dāng)各的值相差不超過1時(shí)，才能取得最小值．．故當(dāng)組中有個(gè)點(diǎn)，組中有個(gè)點(diǎn)時(shí)，達(dá)到最小值．．⑵取個(gè)點(diǎn)為一小組，按圖1染成二色．這樣的五個(gè)小組，如圖2，每個(gè)小圓表示一個(gè)五點(diǎn)小組．同組間染色如圖1，不同組的點(diǎn)間的連線按圖2染成兩色．這個(gè)點(diǎn)為一組，共得組．染色法相同．其中組去掉個(gè)點(diǎn)及與此點(diǎn)相連的所有線．即得一種滿足要求的染色．1992*三、（本題滿分35分）在平面直角坐標(biāo)系中，任取個(gè)格點(diǎn)()滿足：⑴，()；⑵任何三點(diǎn)不在一條直線上．試證明：在以()為頂點(diǎn)的所有三角形中，必有一個(gè)三角形的面積不大于．★證明：如圖，滿足條件的格點(diǎn)只能是圖中這個(gè)格點(diǎn)中的個(gè)．把這個(gè)格點(diǎn)分成三個(gè)矩形：矩形、、．若所取的個(gè)點(diǎn)中有三個(gè)點(diǎn)在上述三個(gè)矩形中的某一個(gè)中，則此三點(diǎn)即滿足要求．若三個(gè)矩形中均無所取點(diǎn)中的點(diǎn)，則必是每個(gè)矩形中有所取的個(gè)點(diǎn)．⑴若中有所取的點(diǎn)，則此點(diǎn)與矩形中的兩點(diǎn)滿足要求；⑵若上述點(diǎn)均未取，則中必有兩點(diǎn)，此時(shí)若中有所取的點(diǎn)，則亦有三點(diǎn)滿足要求；⑶若亦未取，則必在中取了點(diǎn)，矩形中取了點(diǎn)：此時(shí)取兩點(diǎn)，或兩點(diǎn)，或兩點(diǎn)，或兩點(diǎn)，或兩點(diǎn)，則無論中取任一點(diǎn)，與之組成三角形面積均滿足要求．若取兩點(diǎn)，則矩形中必有一點(diǎn)異于，取此點(diǎn)與滿足要求．綜上可知，必有滿足要求的點(diǎn)存在．1990*三．(本題滿分35分)某市有所中學(xué)，第所中學(xué)派出名代表(，)來到體育館觀看球賽，全部學(xué)生總數(shù)為．看臺(tái)上每一橫排有個(gè)座位，要求同一學(xué)校的學(xué)生必須坐在同一橫排，問體育館最少要安排多少橫排才能夠保證全部學(xué)生都能坐下．★解析：首先，，故每排至少可坐所學(xué)校的學(xué)生．，故如果沒有“同一學(xué)校的學(xué)生必須坐在同一橫排”的限制，則全部學(xué)生只要坐在排就夠了．現(xiàn)讓這些學(xué)生先按學(xué)校順序入坐，從第一排坐起，一個(gè)學(xué)校的學(xué)生全部坐好后，另一個(gè)學(xué)校的學(xué)生接下去坐，如果在某一行不夠坐，則余下的學(xué)生坐到下一行．這樣一個(gè)空位都不留，則坐排，這些學(xué)生就全部坐完．這時(shí)，有些學(xué)校的學(xué)生可能分坐在兩行，讓這些學(xué)校的學(xué)生全部從原坐處起來，坐到第排去．由于，這種情況只可能在第一行末尾與第二行開頭、第二行末尾與第三行開頭、……第九行末尾與第十行開頭這處發(fā)生，故需要調(diào)整的學(xué)校不超過所，于是第行至多各坐所學(xué)校的學(xué)生，就可全部坐完．這說明行保證夠坐．其次證明，行不能保證就此學(xué)生按條件全部入坐：．．取所學(xué)校，其中所學(xué)校人，所學(xué)校人．則對(duì)前所學(xué)校的學(xué)生，每排只能坐所學(xué)校而不能坐所學(xué)校．故排只能坐其中所學(xué)校的學(xué)生．即排不夠坐．綜上可知，最少要安排橫排才能保證全部學(xué)生都能坐下．1987*二．在坐標(biāo)平面上，縱橫坐標(biāo)都是整數(shù)的點(diǎn)稱為整點(diǎn)．試證：存在一個(gè)同心圓的集合，使得⑴每個(gè)整點(diǎn)都在此集合的某個(gè)圓周上；⑵此集合的每個(gè)圓周上，有且只有一個(gè)整點(diǎn)．(辛澤爾定理)★證明：取一點(diǎn)，其兩個(gè)坐標(biāo)都是無理數(shù)，例如，先證明，以為圓心，任意長(zhǎng)為半徑作的圓，至多通過一個(gè)格點(diǎn)．設(shè)某個(gè)以為圓心的圓通過兩個(gè)格點(diǎn)，()，則．展開整理得，．左邊是有理數(shù)，右邊當(dāng)且僅當(dāng)時(shí)為有理數(shù)．故證．于是可知以為圓心的圓至多通過一個(gè)格點(diǎn)．現(xiàn)考慮，平面上所有的點(diǎn)與的距離，這些距離沒有兩個(gè)相等．故可以把所有的距離按從小到大排隊(duì)．對(duì)應(yīng)的整點(diǎn)依次為．以W為圓心，以為半徑作圓，則此圓恰經(jīng)過整點(diǎn)．且此圓只經(jīng)過這個(gè)整點(diǎn)．現(xiàn)取以為圓心，所有為半徑的同心圓集．則每個(gè)整點(diǎn)都在此同心圓集合中的某個(gè)圓上，且每個(gè)圓上都有且只有一個(gè)整點(diǎn)．1987*三．()名乒乓球選手單打若干場(chǎng)后，任意兩個(gè)選手已賽過的對(duì)手恰好都不完全相同，試證明：總可以從中去掉一名選手，而使在余下的選手中，任意兩個(gè)選手已賽過的對(duì)手仍然都不完全相同．★證明：證明1：用表示選手，而用表示