資源描述：
《奧數(shù)：第20講 組合問題第05講》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第20講組合問題第05講構造與論證之三例1某學校的學生中，沒有一個學生讀過學校圖書館的所有圖書，又知道圖書館內任何兩本書都至少被一個同學都讀過．問：能否找到兩個學生甲、乙和三本書A、B、C，使得甲讀過A、B，沒讀過C，乙讀過B、C，沒讀過A?說明判斷過程．答案能．分析由題目特征，從極端情形入手，考慮讀書最多的同學，從而把所有圖書分為此同學讀過的和沒讀過的兩部分，再進一步構造．詳解假設學生甲讀書最多，因為沒有一個學生讀過學校圖書館的所有圖書，所以取甲讀過的書B，沒讀過的書C；又因為圖書館內任何兩本書都是至少被一個學生都讀
2、過，不妨設學生乙同時讀過書B、C．由甲讀書最多可知甲讀過的書中必有一本書A，乙沒讀過．從而找到兩個學生甲、乙和三本書A、B、c，符合題意．例2將5×9的長方形分成10個邊長為整數(shù)的長方形，證明：無論怎樣分法，分得的長方形中必有兩個是完全相同的．證明因為在各種形狀的整數(shù)邊長的長方形中，面積最小的互不相同的一些長方形為：1×1、1×2、1×3、1×4,2×2、1×5、1X6、2×3、1×7、1×8、2×4……從中取10個面積最小的互不相同的長方形，面積之和為1+2+3+4X2+5+6×2+7+8=46．而5×9的長方形面積
3、為45，46>45，所以不管怎樣分法，分得的長方形中必有兩個是完全相同的．評注論證圖形必重復出現(xiàn)或數(shù)據(jù)必重復出現(xiàn)的這類問題，常常先考慮若不重復出現(xiàn)的結論，得出與題設矛盾．例3有9位數(shù)學家，每人至多能講3種語言，每3個人中至少有2個人有共通的語言．求證：在這些數(shù)學家中至少有3人能用同一樣語言交談．分析任取某一人，如果與他有共通語言的人超過3個，則這些人中必可找到某2人都用同_-一種語言與他交談．則這3人能用同一種語言交談；如果與他有共通語言的人不超過3個，則至少有5人都與他沒有共通語言，可知5個人中任2個都有共通語言．對
4、這5個人中的某一人來講，他至少與4個人有共通語言．即可歸結為前面分析的情況．證明為方便起見，稱這．9位數(shù)學家為A、B、C、D、E、F、G、H、r考慮與A有共通語言的人數(shù)．①若超過3人與A有共通語言，不妨設為B、C、D、E等人，而每人至多能講3種語言，所以B、C、D、E等人中必至少有兩人用同一種語言與A交談(不妨設為B、C),則A、B、C3人都用同一種語言交談．②若不超過3人與A有共通語言，則至少有5人與A沒有共通語言(不妨設為E、F、G、H、I)．因為每3個人中至少有2個人有共通語言，考慮E、F、G、H、I這5人中的任
5、2人與A所組成的這3人，知道這5人中的任2人必有共通語言.不妨考慮E，則E至少與F、G、H、I4人都有共通語言．此情形與①相類似，結論也是肯定的．綜上所述，可以證明：在這些數(shù)學家中至少有3人能用同一種語言交談．例4在平面上有7個點，其中任意3個點都不在同一條直線上．如果在這7個點之間連結18條線段，那么這些線段最多能構成多少個三角形?答案23個．分析因為7個點之間任2點連結一條線段，應連成=21條．現(xiàn)在只連結18條，少3條，可從這沒連結的3條線段入手考慮．若正面思考18條線段所構成的三角形，情況復雜，無從下手．詳解平面
6、上這7個點，任意3點都不在同一條直線上，若任意2點連結，共可連結出=21條段線．現(xiàn)在只連結18條線段，有3條沒有連出，要使得這18條線段所構成的三角形最多，需使得沒連出的這3條線段共同參與的三角形總數(shù)最多，故這3條線段共點．對于這3條線段中的任何一條，還與其他5個點本應構成5個三角形，故這3條線段沒連出，至少少構成5×3-3=12個三角形．而平面內任何三點不共線的7個點，若任何2點連線，共可構成c；=35個三角形．故現(xiàn)在最多可構成三角形35-12=23個．評注有關平面上的點線問題，常從整體把握．條件中給出的線段較多時，
7、則可轉化考慮其反面，即沒有連出的線段．再結合整體情況尋找思路．例5在9×9棋盤的每格中都有一只甲蟲，根據(jù)信號它們同時沿著對角線各自爬到與原來所在格恰有一個公共頂點的鄰格中，這樣某些格中有若干只甲蟲，而另一些格空著，問空格數(shù)最少是多少?答案9．分析此題可先從簡單情形入手．對于2×2棋盤，黑白染色后，黑、白格的甲蟲沿對角線交換，棋盤格不空；對于3×3棋盤，黑白染色后，角上4個黑格均與中心黑格為鄰，故至少出現(xiàn)3個空格．其實，對于2n×2n的棋盤，棋盤格可以不空；而對于(2n+1)×(2n+1)的棋盤，必至少空2n+1格．詳解
8、從簡單情形入手考慮．．①對2X2棋盤黑白染色(如圖：20—1)，則易知兩黑格及兩白格分別對換甲蟲即可使棋盤格不空；從而得到2n×2n棋盤可劃分為若干塊2×2棋盤，棋盤格均不空．②對3×3棋盤黑白染色(如圖20—2)，注意到圖中有5個黑格，黑格中的甲蟲爬行后必進入黑格，且四個角上的黑格內的甲蟲必爬入中心黑格，而中心黑格內的甲蟲只能爬
