小学奥数系列：第20讲 组合问题第05讲

奥数精品

第20讲 组合问题第05讲

构造与论证之三

例1 某学校的学生中，没有一个学生读过学校图书馆的所有图书，又知道图书馆内任何两本书都至少被一个同学都读过．问：能否找到两个学生甲、乙和三本书A、B、C，使得 甲读过A、B，没读过C，乙读过B、C，没读过A?说明判断过程． 答案 能．

分析 由题目特征，从极端情形入手，考虑读书最多的同学，从而把所有图书分为此同学读过的和没读过的两部分，再进一步构造． 详解 假设学生甲读书最多，因为没有一个学生读过学校图书馆的所有图书，所以取甲读过的书B，没读过的书C；又因为图书馆内任何两本书都是至少被一个学生都读过，不妨设学生乙同时读过书B、C．由甲读书最多可知甲读过的书中必有一本书A，乙没读过．从而找到两个学生甲、乙和三本书A、B、c，符合题意．

例2 将5×9的长方形分成10个边长为整数的长方形，证明：无论怎样分法，分得的长方形中必有两个是完全相同的．

证明 因为在各种形状的整数边长的长方形中，面积最小的互不相同的一些长方形为：1×1、1×2、1×3、1×4,2×2、1×5、1 X 6、2×3、1×7、1×8、2×4……从中取10个面积最小的互不相同的长方形，面积之和为 1+2+3+4 X 2+5+6×2+7+8=46．

而5×9的长方形面积为45，46>45，所以不管怎样分法，分得的长方形中必有两个是完全相同的．

评注 论证图形必重复出现或数据必重复出现的这类问题，常常先考虑若不重复出现的结论，得出与题设矛盾． 例3 有9位数学家，每人至多能讲3种语言，每3个人中至少有2个人有共通的语言．求证：在这些数学家中至少有3人能用同一样语言交谈． 分析 任取某一人，如果与他有共通语言的人超过3个，则这些人中必可找到某2人都用同_-一种语言与他交谈．则这3人能用同一种语言交谈；如果与他有共通语言的人不超 过3个，则至少有5人都与他没有共通语言，可知5个人中任2个都有共通语言．对这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人中的任2人 与A所组成的这3人，知道这5人中的任2人必有共通语言.不妨考虑E，则E至少与F、G、H、I4人都有共通语言．此情形与①相类似，结论也是肯定的．

综上所述，可以证明：在这些数学家中至少有3人能用同一种语言交谈．

例4 在平面上有7个点，其中任意3个点都不在同一条直线上．如果在这7个点之间连结18条线段，那么这些线段最多能构成多少个三角形? 答案 23个．

2 分析 因为7个点之间任2点连结一条线段，应连成C7=21条．现在只连结18条，少

奥数精品

3条，可从这没连结的3条线段入手考虑．若正面思考18条线段所构成的三角形，情况复杂，无从下手．

详解 平面上这7个点，任意3点都不在同一条直线上，若任意2点连结，共可连结出

7?6=21条段线．现在只连结18条线段，有3条没有连出，要使得这18条线段所构成的2三角形最多，需使得没连出的这3条线段共同参与的三角形总数最多，故这3条线段共点． 对于这3条线段中的任何一条，还与其他5个点本应构成5个三角形，故这3条线段没连出，至少少构成5×3-3=12个三角形．而平面内任何三点不共线的7个点，若任何2点 连线，共可构成c；=35个三角形．故现在最多可构成三角形35-12=23个．

评注 有关平面上的点线问题，常从整体把握．条件中给出的线段较多时，则可转化考虑其反面，即没有连出的线段．再结合整体情况寻找思路．

例5 在9×9棋盘的每格中都有一只甲虫，根据信号它们同时沿着对角线各自爬到与原来所在格恰有一个公共顶点的邻格中，这样某些格中有若干只甲虫，而另一些格空着，问 空格数最少是多少? 答案 9．

分析 此题可先从简单情形入手．对于2×2棋盘，黑白染色后，黑、白格的甲虫沿对角线交换，棋盘格不空；对于3×3棋盘，黑白染色后，角上4个黑格均与中心黑格为邻，故至少出现3个空格．其实，对于2n×2n的棋盘，棋盘格可以不空；而对于(2n+1)×(2n+1)的棋盘，必至少空2n+1格．

详解 从简单情形入手考虑． ．

①对2 X 2棋盘黑白染色(如图：20—1)，则易知两黑格及两白格分别对换甲虫即可使棋盘格不空；从而得到2n×2n棋盘可划分为若干块2×2棋盘，棋盘格均不空．

②对3×3棋盘黑白染色(如图20—2)，注意到图中有5个黑格，黑格中的甲虫爬行后必进入黑格，且四个角上的黑格内的甲虫必爬入中心黑格，而中心黑格内的甲虫只能爬入某 一黑格，必至少空3个黑格．

③对5×5棋盘黑白染色后，利用①、②的结论易知至少空5个黑格． ④依此类推，可知对9×9棋盘黑白染色后，至少空9个黑格．如图20—3是甲虫爬行的一种方法．

例6 如图20—4，把正方体的6个表面分成9个相等的正方形．现用红、黄、蓝3种颜色去染这些小正方形，要求有公共边的正方形所染的颜色不同．那么染成红色的正方形的个数最多是多少个? 答案 22个．

详解 注意到同一顶点处的3个小正方形，必各染红、黄、蓝．再考虑以正方体棱的中段为公共边的2个正方形(非顶点处)，共有12对，每一对至多有一个染红，这样的红正方形至多有12个．再考虑原正方体每个面上中心处的正方形的染色情况． 详解 ①因为用红、黄、蓝3种颜色染正方形且要求有公共边的正方

本文来源：https://www.bwwdw.com/article/mo77.html