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

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