2022年16組合與構(gòu)造1981-2018年歷年數(shù)學(xué)聯(lián)賽48套真題WORD版分類匯編含詳細(xì)答案

1、1981 年2022 年全國高中數(shù)學(xué)聯(lián)賽一試試題分類匯編 16 組合與構(gòu)造2022A 三、（此題滿分50 分）將3333方格紙中每個小方格染三種顏色之一,使得每種顏色的小方格的個數(shù)相等；如相鄰兩個小方格的顏色不同,就稱他們的公共邊為“ 分割邊”；試求分割邊條數(shù)的最小值；解析： 記分割邊的條數(shù)為L .第一,將方格紙按如下列圖分成三c ,cj色方格1,cj個區(qū)域,分別染成三種顏色,粗線上均為分割邊,此時共有56 條分割邊,即L56；下面證明L56. 將方格紙的行從上至下依次記為A ,A , A 33,列從左至右依次記為B ,B , B 33,行iA 中方格顯現(xiàn)的顏色數(shù)記為niA,列B 中方格顯現(xiàn)的

2、顏色數(shù)記為niB,三種顏色分別記為1c ,c ,對于一種顏色jc ,設(shè)nic是表示含有c 色方格的函數(shù)與列數(shù)之和. 中含有記A i,cj1,A i 中含有cj色方格,同理定義Bi,cj1,B icj色方格,B i中不含cj色方格0,A i 中不含0jBi,3n33333333就nA inBiA i,cjBi,cjA i,ccji1i1j1j1i1j由于染c 色的方格有1332363個,設(shè)含有jc 色方格的行有a 個,列有 b 個,就c 色方3格一定在 這a行和b列的交叉方 格中,因此ab363. 從而iB 中有nc iab2 ab236338即nic39.j,1,2,3由于在行iA 中有niA

3、種顏色的方格,因此至少有niA1條分割邊,同理在行niB種顏色的方格,因此至少有niB1條分割邊,于是,33 33 33 3L n A i 1 n B i 1 n A i n B i 66 n c j 66 i 1 i 1 i 1 j 1下面分兩種情形爭論 . 當(dāng)有一行或有一列全部方格同色時,不妨設(shè)有一行全為 1c 色,從而方格紙的 33 列中均含有 1c 的 方 格 , 由 于 1c 的 方 格 有 363 個 , 故 至 少 有 11 行 中 含 有 1c 色 方 格 ； 于 是n 1c 11 33 44；由得 L n c 1 n c 2 n c 3 66 44 39 39 66 56沒有

4、一行或沒有一列全部方格同色時,就對任意 1 i 33,均有 n iA 2,n B i 2,33從而由知,L n A i n B i 66 33 4 66 56i 1綜上可知,分割邊條數(shù)的最小值為 56；2022A 四、（此題滿分 50 分）；設(shè) m, n 均是大于 1的整數(shù),m n,a 1 , a 2 , , a n 是 n 個不超過 m 的互不相同的正整數(shù),且 a 1 , a 2 , , a n 互素；證明：對任意實數(shù) x ,均存在一個 i（1 i n）,使得 a i x 2 x,這里 y 表示實數(shù) y 到它最近的整數(shù)的距離；m m 1 證明： 第一證明兩個引理：引理 1：存在整數(shù)c 1,c

5、2,nc,滿意c 1 a 1c 2a 2cnan1,并且cim,1in. 由于a1,a2,an互素,即a 1,a2,an1,有裴蜀定理,存在整數(shù)c 1,c 2,nc,滿意c 1 a 1c2a2c na n1；m, 記下 面 證 明 , 通 過 調(diào) 整 , 存 在 一 組c 1,c2,cn滿 足 , 且ciS 1c 1,c 2,c nc i0,c imS 1c 1,c 2,c ncj0；cjm假如 S 1 0,那么存在 ci m 1,于是 a ic i 1,又 a 1 , a 2 , , a n 是大于 1 的整數(shù),故由可知,存在 jc 0,令 c i /c i a j,c /j c j a i

6、,c k / c k（1 k n,k i , j）,就/ / / / /c 1 a 1 c 2 a 2 c na n 1, 并且 0 m a j c i c i,c j c j a k m,所以 S 1 c 1、, c、2 , , c n / S 1 c 1 , c 2 , , c n,S 2 c 1、, c、2 , , c n / S 2 c 1 , c 2 , , c n假如 S 2 0,就存在 c j m,因此有一個 ic 0 .令 c i / c i a j,c /j c j a i,c k / c k（1 k n,k i , j）,那么成立,并且 m c i / c i , c j

7、c /j 0,與上面類似可以證、/、/明到：S 1 c 1 , c 2 , , c n S 1 c 1 , c 2 , , c n,S 2 c 1 , c 2 , , c n S 2 c 1 , c 2 , , c n,即說明 S 1與 S 均是非負(fù)整數(shù), 故通過有限次上述的調(diào)整,可以得到一組使得成立,并且 S 1 S 2 0結(jié)論獲證；引理2：對任意的實數(shù)a,b,均有abab；對任意整數(shù)1u 和實數(shù) v ,有,此時aa,uvuv；由于對任意整數(shù)u 和實數(shù) x ,均有uxx,于是不妨設(shè)a,b1,22bb,如ab0,不妨設(shè)a0b,就ab1,1,從而22abababab如ab0,不妨設(shè)a,b同號,就

8、當(dāng)ab1時,有ab1,1,222ab1,故此時abababab；當(dāng)ab1時,留意到總有22ab1abab；故得證；2又yy,由知,是成立的；c nan1,并且接下來回到原題,由結(jié)論存在整數(shù)c 1,c 2,cn,滿意c 1 a 1c2a2nci m,1 i n . 于 是,c i a i x x,由 引 理 2 得i 1n n nx c i a i x c i a i x m a i x,i 1 i 1 i 1因此,max ai x 1 x 1 i n mn如 n m2 1,就由知,max 1 i n ai xmn 1xm 2m x1如 n m 1, 就 在 a 1 , a 2 , , a n

9、中 存 在 兩 個 相 鄰 的 正 整 數(shù) ； 不 妨 設(shè) a 1,a 2 相 鄰 , 就2x 2 xx a 2 x a 1 x a 2 x a 1 x,故 a2 x 與 a1 x 中有一個不小于；2 m m 1綜上,總存在存在一個 i （1 i n）,使得 a i x 2 xm m 1 2022A 三、（此題滿分 50 分）給定空間 10個點,其中任意四點不在一個平面上；將某些點之間用線段相連,如得到的圖形中沒有三角形也沒有空間四邊形,試確定所連線段數(shù)目的最大值；解析： 以這 10 個點為頂點,所連線段為邊,得到一個10 階簡潔圖 G,我們證明G 的變數(shù)不超過 15. 設(shè) G 的頂點為 v

10、1 , v 2 , , v 10,一共有 k 條邊,用 D iv 表示頂點 iv 的度；如 D iv 3 對101 1i ,1 ,2 ,3 , 10 都成立,就 k D iv 10 3 15；2 i 1 2假 設(shè) 存 在 iv 滿 足 D iv 4, 不 妨 設(shè) D v 1 n 4, 且 v 與 v 2 , , v n 1 均 相 鄰 . 于 是v 2 , , v n 1 之間沒有邊,否就就成三角形,所以 v 與 v 2 , , v n 1 之間恰有 n 條邊 . 對每個 j （n 2 j 10）,v 至多與 v 2 , , v n 1 中的一個頂點相鄰（否就設(shè) v 與 v ,tv（2 s t

11、 n 1）相鄰,就 v ,2v ,v ,j tv 就對應(yīng)了一個空間四邊形的四個頂點,這與題意沖突）,從而 v 2 , , v n 1 與 v n 2 , , v 10 之間的邊數(shù)至多 10 n 1 9 n 條；在vn2,vn這9n個頂點之間,由于沒有三角形,由托蘭定理,至多94n2條邊,因此 G的邊數(shù)kn9n9n299n292515444ABC 的內(nèi)部例如如下列圖的就有15條邊,且滿意要求；綜上所述,所連線段數(shù)目的最大值為15；2022B 四、（此題滿分50 分）設(shè)ABC 是一個邊長為23的等邊三角形,在和邊界上任取 11 個點 . 1 證明：肯定存在兩個點,它們之間的距離小于或等于1；（20

12、 分）對于中間的圖2 證明：肯定存在兩個點,它們之間的距離嚴(yán)格小于1；（30 分）證明： 1如左下圖 1,我們將ABC分成16個邊長為3 的小等邊三角形；22 中六個灰色的小三角形,我們將它們剖分成三個全等的三角形；這樣,我們就可以看出ABC 就可以被右圖3 的10個正六邊形所掩蓋；圖 3 圖 1 圖 2 不難看出,這里的 10 個正六邊形的直徑為 1,它們可以被看做 10只“ 抽屜”,對于三角形ABC 內(nèi)部和邊界上任取 11個點,依據(jù)抽屜原理,至少有一個正六邊形包含兩個點；而在這個正六邊形中,任意兩點間的距離不超過 1,這樣便證明白我們所要的結(jié)論；（要留意,我們的抽屜的構(gòu)造并不是唯獨的,我們

13、仍可以用下圖 掩蓋 ABC ,也可以得到同樣的結(jié)論）4 所示的 10個直徑為 1的圓圖 4 圖 5 2這部分要求證明的是嚴(yán)格不等號；我們要證明在 11個點中存在兩個點,他們間的距離嚴(yán)格小于 1,留意到直徑為 1的正六邊形中,間距恰好為 1的兩個點肯定是距離最遠(yuǎn)的一對點,另一方面,上面所構(gòu)造的正六邊形抽屜在邊和頂點處是由重復(fù)的,我們通過指定一條邊或者頂點屬于那一個特定的正六邊形來改造我們的“ 抽屜”,使得每一個抽屜不包含正六邊形中距離為 1的頂點對,當(dāng)然,在目前的情形我們只需關(guān)懷怎么改造頂點即可；我們在每一個正六邊形抽屜上去掉一些頂點,使得每一個抽屜不在包含正六邊形中距離為 1的頂點對,如圖 5

14、 就是一個方法,圖中空心的點表示正六邊形中去掉該點,不難看出,這樣的改造仍是掩蓋了原先得三角形 ABC ,且每一個抽屜不在包含正六邊形中距離為 1的頂點對,依據(jù)抽屜原理,我們就證明白：任取 11個點,肯定存在兩個點,它們之間的距離嚴(yán)格小于1；（這樣的抽屜構(gòu)造也是不唯獨的）2022B 四、（此題滿分50 分）用如干單位小正方形和由三個單位小方格組成的n3形“ 磚”鋪滿一個 2 n 的方格棋盤的全部不同可能鋪法的數(shù)目是T 下面的圖是時的兩種不同的鋪法：求T 10；求T 2022的個位數(shù)T225,23,我們證明： 由題意明顯T 11,當(dāng)n3時,我們從左向右地鋪n的方格棋盤,無論哪一種鋪法,至多鋪到一

15、 定會 完成 一個2k（k,123, ,） 的矩 形； 這樣 我們 運算T 時 , 就可 以去 查找 與3Tn1,Tn2,Tn3的關(guān)系,又由下圖我們得到T nTn14 Tn22 T n由T 11,T 25,得T 311,T433,T587,依次下去可得T 1013377由TnT n14 Tn22 Tn3,T 11,T 25,T 311,可知,T 肯定是奇數(shù)； 我們由mod5運算T2022,對每一個T ,我們有：2,T 61,T 70,T 83,T90,T 102,T 113,T 11,T20,T 31,T43,T 5T 12 1 , T 13 2 , T 14 2 , T 15 2 , T 1

16、6 4 , T 17 1 , T 18 1 , T 19 3 , T 20 4 , T 21 3 , T 22 0, T 23 0 , T 24 1 , T 25 1 , T 26 0 , T 27 1 , T 28 3 , T 29 2 , T 30 1 , 可知,T 的個位數(shù)的周期是 24 ；而 2022 21 mod 24,又 mod 5 等于 3的奇數(shù) mod 10 也肯定等于 3,所以 T 2022 的個位數(shù)為 3 ；2022A 三、（此題滿分 50 分）設(shè) P P P 2 , , P 是平面上 n 1 個點,它們兩兩間的距離的最小值為 d d 0,求證：P P 0 1 P P 0

17、2 P P 0 n d n n 1.3 證 明 ： 證 法 一 : 不 妨 設(shè) P P 0 1 P P 0 2 P P 0 n . 先 證 明 : 對 任 意 正 整 數(shù) k , 都 有dP P k 13明顯 , P P k d dk 1 對 k 1,2, ,8 均成立 , 只有 k 8 時右邊取等號 10 分3所以 , 只要證明當(dāng) k 9 時, 有 P P k dk 1 即可 . 3以 iP i 0,1,2, , 為圓心 , d 為半徑畫 k 1 個圓 , 它們兩兩相離或外切 ; 以 0P 圓心,2P P k d為半徑畫圓,這個圓掩蓋上述 k 1 個圓 20 分2所以 P P k d 2 k

18、 1 d 2P P k d k 1 1 30 分2 2 2由 k 9 易知 k 1 1 k 1 40 分2 3所以 P P k dk 1 對 k 9 時也成立 . 3綜上 , 對任意正整數(shù) k 都有 P P k dk 1 . 3d n因而 P P 1 P P 2 P P n n 1. 50 分3證法二 : 不妨設(shè) P P 1 P P 2 P P n .以 iP i 0,1,2, , 為圓心 , d 為半徑畫 k 1 個圓 , 它們兩兩相離或外切 ; 10 分2設(shè) Q 是是圓 iP 上任意一點 , 由于P Q P P PQ P P d P P k 1 P P k 3 P P 20 分2 2 23

19、因而 , 以 P 為圓心 , P P k 為半徑的圓掩蓋上述個圓 30 分2故 3P P k 2 k 1 d 2P P k dk 1 k 1,2, , n 40 分2 2 3所以 P P 1 P P 2 P P n d n n 1. 50 分32022A 四、（此題滿分 50 分）設(shè) A 是一個 3 9 的方格表,在每一個小方格內(nèi)各填一個正整數(shù)稱 A 中的一個 m n 1 m 3 , 1 n 9 方格表為“ 好矩形”,如它的全部數(shù)的和為 10的倍數(shù)稱 A 中的一個 1 1 的小方格為“ 壞格”,如它不包含于任何一個“ 好矩形”求 A 中“ 壞格” 個數(shù)的最大值解析： 第一證明 A 中“ 壞格”

20、 不多于25 個由表格的用反證法假設(shè)結(jié)論不成立,就方格表A 中至多有1 個小方格不是“ 壞格”對稱性,不妨假設(shè)此時第1 行都是“ 壞格”T 9都是模設(shè)方格表A 第 i 列從上到下填的數(shù)依次為ai,bi,ci,i,12,9kk記S kai,T kbic i,k,1,02,9,這里S0T00i1i1我們證明：三組數(shù)S0,S 1,S 9；T0,T 1,T9及S0T0,S 1T 1,S 910 的完全剩余系事實上,假如存在m ,n,0mn9,使SmS nmod10,就,就na iSnSm0 mod10,im1即第 1 行的第m1至第 n 列組成一個“ 好矩形”,與第 1 行都是“ 壞格” 沖突又假如存

21、在m ,n ,0mn9,使TmTnmod10nbiciT nTm0 mod10,2 個小方格不是 “ 壞im11列至第 n 列組成一個 “ 好矩形” ,從而至少有即第 2 行至第 3 行、第m格” ,沖突類似地,也不存在m ,n,0mn9,使SmT mS nTnmod10因此上述斷言得證故99995 mod10,S kT kS kTk012k0k0k0999所以SkTkSkTk550mod10,10 的小方格都是“ 壞格”k0k0k0沖突！故假設(shè)不成立,即“ 壞格” 不行能多于25 個另一方面,構(gòu)造如下一個39的方格表,可驗證每個不填此時有 25 個“ 壞格” 1 1 1 2 1 1 1 1

22、10 1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 2 綜上所述,“ 壞格” 個數(shù)的最大值是252022B 四、（此題滿分50 分）給定n個不同實數(shù),其全部全排列組成的集合為A .對于a a2,anA ,如恰有兩個不同的整數(shù)i j1,2,. ,n1使得aia i1,ajaj1成立,就稱該排列為“ 好排列”.求A 中“ 好排列” 的個數(shù)解析： 第肯定義：對于 A 中的一個排列a 1,a2,an,假如滿意a 1a2an,就稱該排列為自然排列；對于 A 中的一個排列 a 1 , a 2 , , a n,假如有整數(shù) i ,1 2 , , n 1,使得 a i a i 1 就稱i

23、a 和 ia 1 構(gòu)成一個“ 相鄰逆序”；對于 a 1 , a 2 , , a n A,假如它恰有一個“ 相鄰逆序”,就稱該排列為“ 一階好排列”,A 中全部“ 一階好排列”的個數(shù)記為 f 1n ；假如它恰有兩個 “ 相鄰逆序”,就稱該排列為 “ 二階好排列” , A 中全部“ 二階好排列” 的個數(shù)記為f2n；依題意知,f2n恰好是要求的A中“ 好排列” 的個數(shù)；由題意知：1f 1 0,1f 2 1,f 2 1 f 2 2 0,2f 3 1；以下為了表達(dá)簡便,我們把由給定的 k 個不同實數(shù)的全部全排列構(gòu)成的集合記為 A k（k ,1 2 , , n）,其次求 f 1n ；我們先來考察 f 1k

24、 1 與 f 1k 之間的遞推關(guān)系；對 A k 1 中的每一個“ 一階好排列”（記為 a ）,我們考慮從中取出最大的數(shù) a k 1 后剩下的k 個數(shù) a 1 , a 2 , , a k 按原先的次序構(gòu)成的排列（記為 b ）；假如排列 b 是 A 中的“ 一階好排列”,且“ 相鄰逆序” 為 a i a i 1,那么,在排列 a 中,a k 1 的位置只能在 a ia i 1 之間或最終；假如排列 b 不是 A 中的“ 一階好排列”,就排列 b 中的“ 相鄰逆序” 的個數(shù)不為 1,顯然排列 b 中“ 相鄰逆序” 的個數(shù)不能大于 1（否就,排列 a 不是“ 一階好排列”,理由是：因為 a k 1 是

25、最大的數(shù),所以排列 a 中“ 相鄰逆序” 的個數(shù)肯定不少于排列 b 中“ 相鄰逆序” 的個數(shù)）,從而排列 b 中“ 相鄰逆序”的個數(shù)為 0,此時排列 b 是一個自然排列, 而排列 a 是“ 一階好排列” ,所以ak1的位置不能在最終（有k 種可能的位置） ；kkk,即綜合上面的分析可知：f1k1 2f1f1k1 k1 12f1kk1,a1后剩下的 k所以f1nn142n2,即f1n 2nn1；最終求f2n ；我們先來考察f2k1與f2k之間的遞推關(guān)系；對A k1中的每一個 “ 二階好排列” （記為c）,我們考慮從中取出最大的數(shù)個數(shù)a1,a2,ak按原先的次序構(gòu)成的排列（記為d ）；假如排列 d

26、 是 A 中的“ 二階好排列”,且“ 相鄰逆序” 為 a i a i 1,a j a j 1,那么在排列 c 中,a k 1 的位置只能在 a ia i 1 之間或 a ja j 1 之間,或者排在最終；假如排列 d 不是 A 中的“ 二階好排列”,就它肯定是 A 中的“ 一階好排列”,設(shè)“ 相鄰逆序” 為 a i a i 1,由于排列 c 是“ 二階好排列”,所以 a k 1 的位置不能在 a i a i 1 之間,也不能排在最終,其余位置都行,有 k 1 種可能；綜合上面分析可知：f 2 k 1 3 f 2 k k 1 f 1 k ,又 f 1 n 2 nn 1,所以f 2 k 1 3 f

27、 2 k k 1 2 kk 1 ,變形為f 2 k 1 k 2 2 k 1 1 k 1 k 2 3 f 2 k k 1 2 k 1 k k 1 2 2所 以 f 2 n n 1 2 n 1n n 1 27 3 n 3,即2f 2 n 3 n n 1 2 n 1n n 1,2因此 A 中“ 好排列” 的個數(shù)為 3 n n 1 2 n 1 n n 1 個；22022A 四、（此題滿分 50 分）一種密碼鎖的密碼設(shè)置是在正 n 邊形 A 1 A 2 A n 的每個頂點處賦值 0 和 1兩個數(shù)中的一個,同時在每個頂點處染紅、藍(lán)兩種顏色之一,使得任意相鄰的兩個頂點的數(shù)字或顏色中至少有一個相同.問：這種密

28、碼鎖共有多少種不同的密碼設(shè)置；解析： 對于該種密碼鎖的一種密碼設(shè)置,假如相鄰兩個頂點上所賦值的數(shù)字不同,在它們所在的邊上標(biāo)上 a,假如顏色不同,就標(biāo)上 b,假如數(shù)字和顏色都相同,就標(biāo)上 c于是對于給定的點 A 上的設(shè)置（共有 4 種）,依據(jù)邊上的字母可以依次確定點 A 2 , A 3 , , A 上的設(shè)置為了使得最終回到 A 時的設(shè)置與初始時相同,標(biāo)有 a 和 b 的邊都是偶數(shù)條所以這種密碼鎖的全部不同的密碼設(shè)置方法數(shù)等于在邊上標(biāo)記 a,b,c,使得標(biāo)有 a 和 b 的邊都是偶數(shù)條的方法數(shù)的 4 倍設(shè)標(biāo)有 a 的邊有 2i 條,0 i n,標(biāo)有 b 的邊有 2 j 條,0 j n 2 i選取

29、2i 條2 22i 2 j邊標(biāo)記 a 的有 C n 種方法,在余下的邊中取出 2 j 條邊標(biāo)記 b 的有 C n 2 i 種方法,其余的邊標(biāo)記 c由乘法原理,此時共有2i C nC2j2i種標(biāo)記方法對i,j 求和,密碼鎖的全部不同的密碼n設(shè)置方法數(shù)為nn2i1a,42C2i22 C nj2ini0j0n2i這里我們商定C010當(dāng) n 為奇數(shù)時,n2i0,此時2C n 2ji2n2 i2nj0n2i1nn2 in2C2i2C2ji42C2i222C2in 22i代入式中,得4nn2nn 1ni0j0i0i0nCk2n knCk2n kk 12n 12nnk0k0in,就式仍舊成立；如in 2,就

30、正 n 邊形的全部邊都標(biāo)記n 31當(dāng) n 為偶數(shù)時,如2此時只有一種標(biāo)記方法于是,當(dāng)n 為偶數(shù)時,全部不同的密碼設(shè)置的方法數(shù)為4inC2in2iC2j2 i41n01C2i2n2i124in2 C nin 22 i1n 3322220nj0nin0綜上所述,這種密碼鎖的全部不同的密碼設(shè)置方法數(shù)是：當(dāng)n 為奇數(shù)時有 3n1種；當(dāng) n 為偶數(shù)時有 3n3種2022* 四、（此題滿分 50 分）在非負(fù)數(shù)構(gòu)成的39數(shù)表x11x 12x 13x 14x 15x16x 17x18x 19x 17x28x390,Px21x22x 23x24x25x26x27x28x 29x31x 32x 33x 34x35

31、x36x37x38x 39中 每 行 的 數(shù) 互 不 相 同 , 前 6 列 中 每 列 的 三 數(shù) 之 和 為 1 ,x11x 12x 13滿意如x27,x37,x18,x38,x19,x29均大于 1；假如 P 的前三列構(gòu)成的數(shù)表Sx21x22x 23x31x32x 33使得x1 k,123,下性質(zhì)（ O）：對于數(shù)表 P 中任意一列x2k（k,12 ,9,）均存在某個ix3kx 12x 1kx1 kuiminxi1,xi2,x 13；求證：最小值uiminx i1,x i2,x 13,i,1,23肯定來自數(shù)表S 的不同列；存在數(shù)表 P 中唯獨的一列x 1k,k1 2,3,使得33數(shù)表Sx

32、11x 2kx21x 22x2k仍x 3kx31x 32x3k然具有性質(zhì)（ O ）；證明：（i ）假設(shè)最小值 u i min x i 1 , x i 2 , x i 3 , i 1 , 2 3, 不是取自數(shù)表 S 的不同列；就存在一列不含任何 iu . 不妨設(shè) u i x i 2i ,1 2 3, . 由于數(shù)表 P 中同一行中的任何兩個元素都不等,于是 u i x i 2i ,1 2 3, . 另一方面,由于數(shù)表 S 具有性質(zhì)（）,在（ 3）中取 k =2,就存在某個0i ,1 2 3, 使得 x i 02 u i 0 . 沖突；ii 由抽屜原理知 min x 11 , x 12 , min

33、x 21 , x 22 , min x 31 , x 32 中至少有兩個值取在同一列；不妨設(shè) min x 21 , x 22 x 22 , min x 31 , x 32 x 32 . 由前面的結(jié)論知數(shù)表 S 的第一列肯定含有某個 iu ,所以只能是 x 11 u 1 . 同樣, 其次列中也必含某個 ui ,i ,1 2 . 不妨設(shè) x 22 u 2 . 于是 u 3 x 33,即 iu 是數(shù)表 S 中的對角線上數(shù)字：x 11 x 12 x 13S x 21 x 22 x 23x 31 x 32 x 33記 M= 1,2,., 9,令集合 I k M | x ik min x i 1 , x

34、i 2 , i 3,1 明顯 I k M | x 1 k x 11 , x 3 k x 32 且 ,1 ,2 3 I . 由于 x 18 , x 38 1 x 11 , x 32,所以 8 I . 故 I . 于是存在 k * I 使得 x 2 k * max x 2 k | k I . 明顯,*k ,1 ,2 3 .x 11 x 12 x 1 k *下面證明 3 3 數(shù)表 S x 21 x 22 x 2 k * 具有性質(zhì)（）. x 31 x 32 x 3 k *從上面的選法可知 u i : min x i 1 , x i 2 , x ik* min x 1 , x i 2 , i ,1 3

35、. 這說明x 1 k* min x 11 , x 12 u 1 , x 3 k* min x 31 , x 32 u 3又由 S 滿意性質(zhì)（）,在（3）中取 k k *,推得 x k * u 2 , 于是 u 2 min x 21 , x 22 , x 2 k * x 2 k *下 證 對 任 意 的 k M , 存 在 某 個 i ,1 2 3, 使 得 u i x ik . 假 如 不 然 , 就x ik min x i 1 , x i 2 , i 3,1 且 x 2 k x 2 k * . 這與 x 2k * 的最大性沖突；因此,數(shù)表 S 滿意性質(zhì)（）；x 11 x 12 x 1 k下證

36、唯獨性；設(shè)有 k M 使得數(shù)表 S ,S . x 21 x 22 x 2 kx 31 x 33 x 3 k具 有 性 質(zhì) （） . 不 失 一 般 性 , 我 們 假 定 u 1 min x 11 , x 12 , x 13 x 11（ 4 ）u 2 min x 21 , x 22 , x 23 x 22,u 3 min x 31 , x 32 , x 33 x 33；x 32 x 31由 于 x 32 x 31,x 22 x 21, 及 （ i ）,有 u . 1 min x 11 , x 12 , x 1 k x 11 . 又 由 （ i 知 ： 或者 a u . 3 min x 31 ,

37、 x 32 , x 3 k x 3 k,或者 b u . 2 min x 21 , x 22 , x 2 k x 2 k .假如 a 成立,由數(shù)表 S.具有性質(zhì)（）,就 u . 1 min x 11 , x 12 , x 1 k x 11,（5）u . 2 min x 21 , x 22 , x 2 k x 22,u . 3 min x 31 , x 32 , x 3 k x 3 k由數(shù)表 S.滿意性質(zhì)（）,就對于 3 M 至少存在一個 i ,1 2 , 3 使得 u . i x i 3,又由（ 4）,（5）式知,u . 1 x 11 x 13 , u . 2 x 22 x 23 . 所以只能

38、有 u . 3 x 3 k x 33 . 同樣由數(shù)表 S 滿意性質(zhì)（）,可推得 x 33 x 3 k . 于是 k 3,即數(shù)表 S S .如 果 b 成 立 , 就 u . 1 min x 11 , x 12 , x 1 k x 11,u . 1 min x 11 , x 12 , x 1 k x 11,（ 6 ）u . 2 min x 21 , x 22 , x 2 k x 2 k,u . 3 min x 31 , x 32 , x 3 k x 32由數(shù)表 S.滿意性質(zhì)（）,對于 k * M,存在某個 i ,1 2 3, 使得 u . i x ik *,由 k * I 及（ 4）和（ 6）式

39、知,x 1 k * x 11 u . 1 , x 3 k * x 32 u . 3 .于是只能有 x 2 k* u . 2 x 2 k . 類似地, 由 S 滿意性質(zhì) （）及 k M 可推得 x 2 k u 2 x 2 k *,從而 k * k；2007* 二、（此題滿分 40 分）；如下列圖, 在 7 8 的長方形棋盤的每個小方格的中心點各放一個棋子； 假如兩個棋子所在的小方格共邊或者共頂點,那么稱這兩個棋子相連；現(xiàn)從這 56 個棋子中取出一些,使得棋盤上剩下的棋子,沒有五個在一條直線（橫豎斜方向） 上依次相連；問最少取出多少個棋子才能滿意要求？并說明理由；解析：解： 最少要取出 11 個棋

40、子,才可能滿意要求；其緣由如下：假如一個方格在第 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這些方格上至少要取出

41、 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)至少取出 區(qū)域內(nèi)至少已取出了 10 個棋子；3 個棋子；這樣,在這些因此,在中心陰影區(qū)域內(nèi)不能取出棋子；由于、這 4 個棋子至多被取出 2 個,從而,從斜的方向看必有五子連珠了；沖突；圖 1 圖 2 其次步構(gòu)造一種取法,共取走11 個棋子,余下的棋子沒有五子連珠；如圖2,只要取出有標(biāo)號位置的棋子,就余下的棋子不行能五子連珠；綜上所述,最少要取走a11 個

42、棋子,才可能使得余下的棋子沒有五子連珠；. 將全部吉利數(shù)從小2005* 12、假如自然數(shù)a 的各位數(shù)字之和等于7 ,那么稱 a 為“ 吉利數(shù)”到大排成一列a1,a2,3,如an2005,就a5n 答案： 5200解析：由于方程 x 1 x 2 x k m 的非負(fù)整數(shù)解的個數(shù)為 C m mk 1,而使 1x 1,ix 0（i 2）的整數(shù)解個數(shù)為 C m m 1k 2；現(xiàn)取 m 7,可知, k 位吉利數(shù)的個數(shù)為 p k C k 65由于 2005是形如 2 abc 的數(shù)中最小的一個吉利數(shù),且 p 1 1,p 2 7,p 3 28,對6四位吉利數(shù) 1 abc,其個數(shù)為滿意 a b c 6 的非負(fù)整數(shù)

43、解的個數(shù),即 C 6 3 1 28 個；又 2005是第 1 7 28 28 1 65 個吉利數(shù),即 a 66 2005,從而 n 65,5n 325；又 p 4 84,p 5 210,而 p 1 p 2 p 3 p 4 p 5 330所以從大到小最終六個五位吉利數(shù)依次是 70000 , 61000 , 60100 , 60010 , 60001 , 52000,所以第 325個吉利數(shù)是 52000,即 a 5n 520002003* 三、（此題滿分 50 分）；由 n 個點和這些點之間的 l 條連線段組成一個空間圖形,其中2 1 2n q q 1,l q q 1 1,q 2,q N；已知此圖

44、中任四點不共面,每點至少2有一條連線段,存在一點至少有 q 2 條連線段證明：圖中必存在一個空間四邊形 即由四點A ,B ,C,D和四條連線段AB,BC,CD,DA組成的圖形 證明：證明：設(shè)點集為VA 0,A 1,A n1,與iA 連線的點集為B ,且B ib i于是11bin1又明顯有n1b i2 lqq122,i0如存在一點與其余點都連線,不妨設(shè)b 0n1就B 中n1個點的連線數(shù)lb 01qq121n1 留意：2qq1q2qn1 1q1n11n11q1n11n211 由q2 22但如在這n1 個點內(nèi),沒有任一點同時與其余兩點連線,就這n1個點內(nèi)至多連線n21條,故在B 中存在一點iA ,它

45、與兩點jA 、A i,j,k互不相等,且i,j,k1連了線,于是A 0,A j,A i,A k連成四邊形現(xiàn)設(shè)任一點連的線數(shù)n2且設(shè)b 0q2n2且設(shè)圖中沒有四邊形于是當(dāng)ij時,iB 與B 沒有公共的點對,即B iBj1 0i,jn1 記B 0VB 0,就由BiB 01,得BiB 0bi1 i,12 ,n1 ,且當(dāng)1i,jn1且ij時,n1BiB 0與BjB 0無公共點對從而B 中點對個數(shù)B iB 0 中點對個數(shù)即i1C2b0n1C2B0n12 C b i11n12 b i3 b i21n11n1b i23n1b i2nni1B ii1i1i1i122 由平均不等式 111n12 l0b 02n

46、32lb 0b 02n11221n12lb2312 l2n22l12lb 0n12lb 02n2 留意12b 0 兩邊同乘以2 n1 2n1n1q2n1q12 ,qq121b 01即得到C2nq2b 0n2n1n即nb 0n1b0n1q2b 02n1q12b 0留意到1qq1 b 0n1b 0nqqb0nqn3b 0 各取部分因數(shù)比較得qq1n又nqn3b0qn1b 0q1b 0n3q1q2n3q2q1nn0210（這里用到前面所得到的式子b0q2,qq1q2qn1）2q2qn1q2b0q1nb 0qb0qn2qq2qn（這里也用到前面所得到的式子b 0q2,qq1q2qn1）又nqn3b 0

47、、nqq2b 0、qn1b 0、q1nb 0均為正整數(shù),從而由、得,qq1nb 0n1b 0nqq2b 0nqn3b0由、沖突,知原命題成立又證： 畫一個 n n 表格,記題中 n 個點為 A 1 , A 2 , , A n,如 iA 與 A 連了線,就將表格 j中第 i 行 j 列的方格中心涂紅于是表中共有 l2 個紅點, 當(dāng) d A i m 時,就表格中的 i 行及i 列各有 m 個紅點且表格的主對角線上的方格中心都沒有涂紅由已知,表格中必有一行有q2個紅點不妨設(shè)最終一行前q2格為紅點其余格就不為紅點 如有紅點就更易證 ,于是：問題轉(zhuǎn)化為：證明存在四個紅點是一個邊平行于格線的矩形頂點如否,

48、就表格中任何四個紅點其中心都不是一個邊平行于格線的矩形頂點2于是,前n1行的前q2個方格中,每行至多有1個紅點去掉表格的第n 行及前q列,就至多去掉q2n1 q2q2qq121個紅點于是在余下n1 nq2方格表中,至少有2 2 2 3 22 l q 1 1 q q 1 2 q 1 1 q q q 個紅點設(shè)此表格中第 i 行有 m i ,1 2 , , n 1 個紅點,于是,同行的紅點點對數(shù)的總和為n 12 2 2 2 2 2C mi其中 q q n 1 由于當(dāng) n k 時,C n C k C n 1 C k 1,故當(dāng)紅點總數(shù)為i 1n 13 2 2 2q q q 個時,可取 q 行每行取 q

49、個紅點, q行每行取 q 1 個紅點時 C mi 取最小值,i 1n 12 2 2 2由下證可知紅點數(shù)多于此數(shù)時更有利于證明 ,但 q C q qC q 1 C m ii 1由假設(shè),不存在處在不同行的 2 個紅點對,使此四點兩兩同列, 所以,有 由于去掉了 q 2列,故仍余 q 2 1 列,不同的列對數(shù)為 C q 22 1 n 1即 C m 2i C q 22 1,所以 q 2q q 1 q q 1 q 2 q 2 1 q 2 2i 1即 q q 1 q 2q 2 q 1 q 1 q 2 2即 q 3q 2 2 q q 3q 2 2 q 2 明顯沖突故證2001* 三、（此題滿分 50 分）

50、將邊長為正整數(shù) m,n 的矩形劃分成如干邊長均為正整數(shù)的正方形每個正方形的邊均平行于矩形的相應(yīng)邊試求這些正方形邊長之和的最小值解析： 記所求最小值為fm ,n ,AA 1DmD1 CC我們可以證明fm ,n mnm ,n* 其中m ,n表示 m 和 n 的最大公約數(shù)事實上,不妨設(shè)mn,1 關(guān)于 m 歸納,可以證明存在一合乎題意的分法,使所得正Dn方形邊長之和恰為mnm ,n當(dāng)m1 時 ,命題明顯成立k1）當(dāng)mk1時,如AA1 B假設(shè)當(dāng)mk時,結(jié)論成立（nk1,就命題明顯成立如nk1,從矩形 ABCD 中切去正方形1D（如圖）,DD1 n由歸納假設(shè)矩形A 1BCD1有一種分法使得所得正方形邊長之

51、和恰為mnnm ,nmm ,n .于是原矩形 ABCD 有一種分法使得所得正方形邊長之和為mnm ,n；2 關(guān)于 m 歸納可以證明 * 成立當(dāng) m 1 時,由于 n 1,明顯 f m , n 1 m n m , n 假設(shè)當(dāng) m k 時,對任意 1nm 有 f m,n= m+n- m, n如 m k 1,當(dāng) n k 1 時明顯 f m , n k 1 m n m , n 當(dāng) 1 n k 時,設(shè)矩形 ABCD 按要求分成了 p 個正方形,其邊長分別為 a 1 , a 2 , , a p,不妨設(shè) a 1 a 2 a p明顯 a1 n 或 a1 n如 a1 n,就在 AD 與 BC 之間的與 AD 平

52、行的任始終線至少穿過二個分成的正方形（或其邊界）,于是 a 1 a 2 a p 不小于 AB 與 CD 之和所以a 1 a 2 a p 2 M m n m , n 如 a1 n,就一個邊長分別為 m n 和 n 的矩形可按題目要求分成邊長分別為 a 2 , , a p的正方形,由歸納假設(shè) a 2 a p m n n m , n m m , n ；從而 a 1 a 2 a p m n m , n 于是當(dāng) m k 1 時,f m , n m n m , n 再由 1 可知 f m , n m n m , n ；1997* 三、（此題滿分 50 分）在 100 25 的長方形表格中每一格填入一個非負(fù)

53、實數(shù),第 i行第j 列中填入的數(shù)為 ix,（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 ；求最小25的自然數(shù) k ,使得只要表 1中填入的數(shù)滿意 ix , j 1（i ,1 2 , 100）,就當(dāng) i k 時,在j 1表 2 中就能保證25/ ix ,j1；4i,3ix4 i,2ix4i,1ix4 i,i0 i,12,25 ,其余各數(shù)均j1解析： 在表 1 中,取x取 1 ,于是,每列各數(shù)之和均等于 1但重新填入后,前 96行

54、之和均等于 25 1第24 2497 , 98 , 99 , 100 行之和等于 0 故 k 97反之,假如表 2 中第 97行的 25個數(shù)涂黃,98 100 行共 75個數(shù)涂紅,就這些涂紅的數(shù)在表 1中至多分布在 75行中,于是除這 75行外的其余各行中的每個數(shù)都不小于同列中涂黃的數(shù),即涂黃 4個數(shù)的和沒有涂紅數(shù)的行的每一行數(shù)的和1于是表 2 中第 97 行的數(shù)的和 1,故第 98 , 99 , 100 行的數(shù)的和 1即能保證表 2 中第 97 100 行的數(shù)的和 1k 971996* 四、（此題滿分 35 分）有n（n 6）個人聚會,已知：每人至少同其中 n 個人相互熟悉；2對于其中任意

55、n 個人,或者其中有 2 人相識,或者余下的任中有 2人相識；2證明：這 n 個人中必有三人兩兩相識；證明：作一個圖,用 n 個點表示這 n 個人,凡二人熟悉,就在表示此二人的點間連一條線問題即,在題設(shè)條件下,存在以這 n 點中的某三點為頂點的三角形設(shè)點 a 連線條數(shù)最多,在與 a 連線的全部點中點 b 連線最多,與 a 連線的點除 b 外的集合為 A ,與 b 連線的點除 a 外的集合為 B 1設(shè)n2 ,就每點至少連k 條線,A,B中都至少有k1 個點如存在一點 c ,與 a, b 都連線,就 a , b , c 滿意要求；如沒有任何兩點與此二點都連線 圖 1 ,就由 A B,A B 2k

56、2,A k 1 B k 1, 故得 A B k 1,且圖中每點都連 k 條線如 A 或A BB 中存在兩點,這兩點間連了一條線,就此二點與 a 連出三角形,如 A 中任何 k k-1兩點間均未連線,B中任兩點也未連線,就 A b 中不存在兩點連線,B a 2k+1個點中也不存在兩點連線與已知沖突a b圖22設(shè) n 2k 1就每點至少連 k 條線,A, B 中都至少有 k 1 個點如存在一點 c ,與 a, b 都連線,就 a , b , c 滿意要求；如沒有任何兩點與此二點都連線,且 A k,就由 B k 1 時 圖 2 ,就由A B,A B 2k 1,A k,B k 1,故得 A B 2k

57、1,A k,B k 1,如 A 或 B 中存在兩點,這兩點間連了一條線,就此二點與 a 連出 c三角形,如 A中任何兩點間均未連線,B中任兩點也未連線,就 A b 中不存k-1 Ak 1 k 2k-1 B在兩點連線,B a 中也不存在兩點連線與已知沖突2k+1個點如沒有任何兩點與此二點都連線,且 A k 1,即每點都只連 k 條線這 a圖 3 b時,必有一點與 a, b 均未連線,設(shè)為 c c 與 A中 k 個點連線,與 B 中 k 個點連線,k 1 k 2 k,且 1 k 1 , k 2 k 1否就如 k 2 0,就 A b 中各點均未連線,B a , c中各點也未連線沖突故 k 1k 2

58、1且由于 n 6,即 k 1, k 2 中至少有一個 2 ,不妨設(shè)k 1 2,現(xiàn)任取 B 中與 c 連線的一點 1b ,由于 1b 與B中其余各點均未連線,如 1b 與A中的所有與 c 連線的點均未連線,就 1b 連線數(shù) 2 k 1 k 1 k 1,沖突,故 1b 至少與此 k 個點中的一點連線故證1995* 四、（此題滿分 35 分）將平面上的每個點都以紅,藍(lán)兩色之一著色；證明：存在這樣兩個相像的三角形,它們的相像比為1995,并且每一個三角形的三個頂點同色；SR證明： 第一證明平面上肯定存在三個頂點同色的直角三角形任取平面上的一條直線l ,就直線 l 上必有兩點同色設(shè)此兩點為P,Q,不妨l

59、l 1P設(shè)P,Q同著紅色 過P,Q作直線 l 的垂線1l 、2l,如1l 或2l上有異于P,Q的點著紅Tl 2Q色,就存在紅色直角三角形如1l 、2l 上除P,Q外均無紅色點,就在1l 上任取異于P的兩點R,S,就R,S必著藍(lán)色,過R作 1l 的垂線交2l于 T,就 T 必著藍(lán)色RST即為三頂點同色的直角三角形設(shè)直角三角形ABC三頂點同色 B為直角 把ABC補(bǔ)成矩形ABCD 如圖 把EA矩形的每邊都分成n 等分 n 為正奇數(shù),n1,此題中取n1995 連結(jié)對邊相應(yīng)分點,把矩形 ABCD 分成2 n 個小矩形AB 邊上的分點共有n1個,由于 n 為奇數(shù),故必存在其中兩個相鄰的分點同色, 否就任兩

60、個相鄰分點異色,就可得A,B異色 ,不妨設(shè)相鄰分點E,FD同色考察E,F所在的小矩形的另兩個頂點E/, F/,如E/, F/異E色,就/ EFE 或DFF/為三個頂點同色的小直角三角形如GMHNFFE/, F/同色,再考察以此二點為頂點而在其左邊的小矩形, 這CPQB樣依次考察過去,不妨設(shè)這一行小矩形的每條豎邊的兩個頂點都同色同樣, BC 邊上也存在兩個相鄰的頂點同色,設(shè)為 P, Q,就考察 PQ 所在的小矩形,同理,如 P, Q 所在小矩形的另一橫邊兩個頂點異色,就存在三頂點同色的小直角三角形否就,PQ 所在列的小矩形的每條橫邊兩個頂點都同色現(xiàn)考察 EF 所在行與PQ 所在列相交的矩形GHN