奥数：第20讲 组合问题第05讲

《奥数：第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个边长为整数的长方形，证明：无论怎样分法，分得的长方形中必有两个是完全相同的．证明因为在各种形状的整数边长的长方形中，面积最小的互不相同的一些长方形为：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，所以不管怎样分法，分得的长方形中必有两个是完全相同的．评注论证图形必重复出现或数据必重复出现的这类问题，常常先考虑若不重复出现的结论，得出与题设矛盾．例3有9位数学家，每人至多能讲3种语言，每3个人中至少有2个人有共通的语言．求证：在这些数学家中至少有3人能用同一样语言交谈．分析任取某一人，如果与他有共通语言的人超过3个，则这些人中必可找到某2人都用同_-一种语言与他交谈．则这3人能用同一种语言交谈；如果与他有共通语言的人不超过3个，则至少有5人都与他没有共通语言，可知5个人中任2个都有共通语言．对

4、这5个人中的某一人来讲，他至少与4个人有共通语言．即可归结为前面分析的情况．证明为方便起见，称这．9位数学家为A、B、C、D、E、F、G、H、r考虑与A有共通语言的人数．①若超过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人都有共通语言．此情形与①相类似，结论也是肯定的．综上所述，可以证明：在这些数学家中至少有3人能用同一种语言交谈．例4在平面上有7个点，其中任意3个点都不在同一条直线上．如果在这7个点之间连结18条线段，那么这些线段最多能构成多少个三角形?答案23个．分析因为7个点之间任2点连结一条线段，应连成=21条．现在只连结18条，少3条，可从这没连结的3条线段入手考虑．若正面思考18条线段所构成的三角形，情况复杂，无从下手．详解平面

6、上这7个点，任意3点都不在同一条直线上，若任意2点连结，共可连结出=21条段线．现在只连结18条线段，有3条没有连出，要使得这18条线段所构成的三角形最多，需使得没连出的这3条线段共同参与的三角形总数最多，故这3条线段共点．对于这3条线段中的任何一条，还与其他5个点本应构成5个三角形，故这3条线段没连出，至少少构成5×3-3=12个三角形．而平面内任何三点不共线的7个点，若任何2点连线，共可构成c；=35个三角形．故现在最多可构成三角形35-12=23个．评注有关平面上的点线问题，常从整体把握．条件中给出的线段较多时，

7、则可转化考虑其反面，即没有连出的线段．再结合整体情况寻找思路．例5在9×9棋盘的每格中都有一只甲虫，根据信号它们同时沿着对角线各自爬到与原来所在格恰有一个公共顶点的邻格中，这样某些格中有若干只甲虫，而另一些格空着，问空格数最少是多少?答案9．分析此题可先从简单情形入手．对于2×2棋盘，黑白染色后，黑、白格的甲虫沿对角线交换，棋盘格不空；对于3×3棋盘，黑白染色后，角上4个黑格均与中心黑格为邻，故至少出现3个空格．其实，对于2n×2n的棋盘，棋盘格可以不空；而对于(2n+1)×(2n+1)的棋盘，必至少空2n+1格．详解

8、从简单情形入手考虑．．①对2X2棋盘黑白染色(如图：20—1)，则易知两黑格及两白格分别对换甲虫即可使棋盘格不空；从而得到2n×2n棋盘可划分为若干块2×2棋盘，棋盘格均不空．②对3×3棋盘黑白染色(如图20—2)，注意到图中有5个黑格，黑格中的甲虫爬行后必进入黑格，且四个角上的黑格内的甲虫必爬入中心黑格，而中心黑格内的甲虫只能爬