8-6-1构造与论证 题库教师版 - 图文

板块二、染色与赋值问题

【例 15】 某学校的学生中，没有一个学生读过学校图书馆的所有图书，又知道图书馆内任何两本书都至

少被一个同学都读过．问：能否找到两个学生甲、乙和三本书4、B、C，使得甲读过A、B，没读过C，乙读过B、C，没读过A?说明判断过程．

【解析】 首先从读书数最多的学生中找一人甲．由题设，甲至少有一本书未读过，记为C．设B是甲读过

的书中一本，由题意知，可找到学生乙，乙读过B、C．由于甲是读书数最多的学生之一，乙读书数不能超过甲的读书数，而乙读过C书，甲未读过C书，所以一定可以找出一本书A，使得甲读过而乙未读过，否则乙就比甲至少多读过一本书．这样一来，甲读过A、B，未读过C；乙读过B、C未读过A.因此可以找到满足要求的两个学生．

【例 16】 4个人聚会，每人各带2件礼品，分赠给其余3个人中的2人．试证明：至少有2对人，每对

人是互赠过礼品的．

【解析】 将这四个人用4个点表示，如果两个人之间送过礼，就在两点之间连一条线．

由于每人送出2件礼物，图中共有4×2=8条线，由于每人礼品都分赠给2个人，所以每两点之间至多有1+1=2条线。四点间，每两点连一条线，一共6条线，现在有8条线，说明必有两点之间连了2条线，还有另外两点(有一点可以与前面的点相同)之间也连了2条线． 即为所证结论。

【例 17】 有9位数学家，每人至多能讲3种语言，每3个人中至少有2个人有共通的语言.求证：在这些

数学家中至少有3人能用同一种语言交谈。

【解析】 假设任意三位数学家都没有共同会的语言，这表明每种语言至多有两人会说.即这九位数学家为

A、B、C、D、E、F、G、I．由于一位数学家最多会三种语言，而每种语言至多有两人会说，所以一位数学家至多能和另外三人通话，即至少与五人语言不通．不妨设A不能与B、C、D、E、F通话．

同理，B也至多能和三人通话，因此在C、D、E、F中至少有一人与B语言不通，设为C.则A、B、C三人中任意两人都没有共同语言，与题意矛盾．这表明假设不成立，结论得证．

【例 18】 在1000×1000的方格表中任意选取n个方格染为红色，都存在3个红色方格，它们的中心构成

一个直角三角形的顶点．求n的最小值．

【解析】 首先确定1998不行．反例如下：

其次1999可能是可以的，因为首先从行看，1999个红点分布在1000行中， 肯定有一些行含有2个或者以上的红点，因为含有0或1个红点的行最多

999个，所以其他行含有红点肯定大于等于1999-999=1000，如果是大于

1000，那么根据抽屉原理，肯定有两个这样红点在一列，那么就会出现红 色三角形；

如果是等于1000而没有这样的2个红点在一列，说明有999行只含有1个

红点，而剩下的一行全是红点，那也肯定已经出现直角三角形了，所以n的最小值为1999．

【例 19】 甲、乙、丙三个班人数相同，在班级之间举行象棋比赛．各班同学都按l，2，3，4，?依次编

号．当两个班比赛时，具有相同编号的同学在同一台对垒．在甲、乙两班比赛时，有15台是男、女生对垒；在乙、丙班比赛时，有9台是男、女生对垒．试说明在甲、丙班比赛时，男、女生对垒的台数不会超过24．并指出在什么情况下，正好是24 ？

8-6.构造与论证.题库 教师版 page 9 of 13 【解析】 不妨设甲、乙比赛时，1～15号是男女对垒，乙、丙比赛时．在1～15号中有a台男女对垒，15

号之后有9-a台男女对垒(0≤a≤9)

甲、丙比赛时，前15号，男女对垒的台数是15-a(如果1号乙与1号丙是男女对垒，那么1号甲

与1号丙就不是男女对垒)，15号之后，有9-a台男女对垒.所以甲、丙比赛时，男女对垒的台数为

15-a+9-a=24-2a≤24．

仅在a=0，即必须乙、丙比赛时男、女对垒的号码，与甲、乙比赛时男、女对垒的号码完全不同，

甲、丙比赛时，男、女对垒的台数才等于24．

【例 20】 将5×9的长方形分成10个边长为整数的长方形．证明：无论怎样分法．分得的长方形中必有

两个是完全相同的．

【解析】 10个边长为整数的长方形，其面积显然也均是正整数．划分出的长方形按面积从小到大为：1×1，

1×2，l×3，1×4，2×2，1×5，1×6，2×3，1×7，1×8，2×4，1×9，3×3．2×5，2×6，3×4，2×7，3×5，2×8，4×4，2×9，3×6，……从这些长方形中选出lO个不同的长方形，其面积和最小为：1×1+1×2+1×3+1×4+2×2+1×5+1×6+2×3+1×7+1×8=46．而原长方形的面积为5×9=45<46．所以分出的长方形必定有某两个是完全一样的．

【例 21】 将15×15的正方形方格表的每个格涂上红色、蓝色或绿色．证明：至少可以找到两行，这两行

中某一种颜色的格数相同．

【解析】 如果找不到两行的某种颜色数一样，那么就是说所有颜色的列与列之问的数目不同．那么红色最

少也会占0+1+2+…+14=105个格子．

同样蓝色和绿色也是，这样就必须有至少： 3×(0+l+2+…+14)=315个格子．

但是，现在只有15×15=225个格子，所以和条件违背，假设不成立，结论得证．

【例 22】 在平面上有7个点，其中任意3个点都不在同一条直线上．如果在这7个点之字连结18条线段，

那么这些线段最多能构成多少个三角形 ？

【解析】 平面上这7个点，任意3点都不在同一条直线上，若任意2点连接，共可连接出C72C72=7×6÷

2=21条线段．现在只连接18条线段，有3条没有连出，要使得这18条线段所构成的三角形最多，需使得没连出的这3条线段共同参与的三角形总数最多，故这3条线断共点.对于这3条线段中的任何一条，还与其他5个点本应构成5个三角形，故这3条线段没连出，至少少构成5×3-3=12个三角形.

如上图所示，在图中AD、AE、AF之间未连接，因为其中ADE、AED，ADF、AFD，AEF、AFE被重复

3C7计算，所以减去3．而平面内任何三点不共线的7个点，若任何2点连线，最多可构成=35个

三角形．故现在最多可构成三角形35-12=23个．

【例 23】 在9×9棋盘的每格中都有一只甲虫，根据信号它们同时沿着对角线各自爬到与原来所在格恰有

一个公共顶点的邻格中，这样某些格中有若干只甲虫，而另一些格则空着．问空格数最少是多少?

【解析】 方法一：考虑到甲虫总是斜着爬，我们把棋盘黑白相间染色，发现原来黑色格子里的甲虫都会爬

8-6.构造与论证.题库 教师版 page 10 of 13 到黑色的格子里面，而白色格子里面的甲虫都会爬到白色格子里面，所以我们只用观察最少能空出多少个黑格子，多少个白格子．

因为甲虫每次都从奇数行爬到偶数行，偶数行爬到奇数行，而由奇数行有25个黑格子，偶数行有16个黑格子知，偶数行的16只甲虫爬到奇数行会空出9个黑格子，而奇数行的25只虫子爬到偶数行就可以没有空格．白格子虫子也会从奇数行爬到偶数行，偶数行爬到奇数行，但是奇数行和偶数行都是20个格子，最少的情况下不会出现空格子，所以最少出现9个空格． 方法二：

① 对2×2棋盘如下黑白染色，则易知两黑格及两白格分别对换甲虫即可使棋盘格不空；从而得

到2n×2n棋盘可划分为若干块2×2棋盘，棋盘格均不空．

② 对3×3棋盘如下黑白染色，注意到图中有5个黑格，黑格中的甲虫爬行后必进入黑格，且四

个角上的黑格内的甲虫必爬人中心黑格，而中心黑格内的甲虫只能爬人某一格，必至少空3个黑格．

③ 对5×5棋盘黑白染色后，利用①、②的结论易知至少空5个黑格．

④ 依次类推，可知对9×9棋盘黑白染色后，至少空9个空格．下图是甲虫爬行的一种方法．

【例 24】 若干台计算机联网，要求：

①任意两台之间最多用一条电缆连接； ②任意三台之间最多用两条电缆连接；

③两台计算机之间如果没有电缆连接，则必须有另一台计算机和它们都连接有电缆．若按此要求

最少要用79条电缆．

问：(1)这些计算机的数量是多少台?

(2)这些计算机按要求联网，最多可以连多少条电缆? 【解析】 将机器当成点，连接电缆当成线，我们就得到一个图，如果从图上一个点出发，可以沿着线跑到

图上任一个其它的点，这样的图就称为连通的图，条件③表明图是连通图．

我们看一看几个点的连通图至少有多少条线．可以假定图没有圈(如果有圈，就在圈上去掉一条

线)，从一点出发，不能再继续前进，将这一点与连结这点的线去掉．考虑剩下的n-1个点的图，它仍然是连通的．用同样的办法又可去掉一点及一条线．这样继续下去，最后只剩下一个点．因此n个点的连通图至少有n-1条线(如果有圈，线的条数就会增加)，并且从一点A向其他n-1个点各连一条线，这样的图恰好有n-1条线．

因此，(1)的答案是n=79+1=80，并且将一台计算机与其他79台各用一条线相连，就得到符合要

求的联网．

下面看看最多连多少条线．

在这80个点(80台计算机)中，设从A1引出的线最多，有k条，与A1相连的点是B1,B2，…，Bk8-6.构造与论证.题库 教师版 page 11 of 13

由于条件，B1,B2…，Bk之间没有线相连．

设与A1不相连的点是A2，A3…，Am，则m+k=80，而A2，A3…, Am每一点至多引出k条线，图

中至多有mk条线，因为B404?m?k?(m?k)2≤(m?k)2?6400

所以m×k≤1600，即连线不超过1600条．

另一方面，设80个点分为两组：A1,A2…，A40；B1，B2…，B40第一组的每一点与第二组的每一点各用一条线相连，这样的图符合题目要求，共有40×40=1600条线

【例 25】 在一个6×6的方格棋盘中，将若干个1×1的小方格染成红色．如果随意划掉3行3列，在剩

下的小方格中必定有一个是红色的．那么最少要涂多少个方格?

【解析】 方法一：显然，我们先在每行、每列均涂一个方格，使之成为红色，如图A所示，但是在图B中，

划去3行3列后，剩下的方格没有红色的，于是再将两个方格涂成红色(依据对称性，应将2个方格同时涂成红色)，如图C所示，但是图D的划法，又使剩下的方格没有红色，于是再将两个方格涂成红色(还是由于对称的缘故，将2个方格涂成红色)，得到图E，图E不管怎么划去3行3列，都能使剩下的方格含有红色的．

这时共涂了10个方格．

方法二：一方面，图F表明无论去掉哪三行哪三列总会留下一个涂红的方格．

另一方面，如果只涂9个红色方格，那么红格最多的三行至少有6个红格(否则第三多的行只有1

个红格，红格总数≤5+3=8)，去掉这三行至多还剩3个红格，再去掉三列即可将这三个红格也去掉．综上所述，至少需要将10个方格涂成红色．

【例 26】 如图，把正方体的6个表面剖分成9个相等的正方形．现用红、黄、蓝3种颜色去染这些小正

方形，要求有公共边的正方形所染的颜色不同．那么染成红色的正方形的个数最多是多少个?

【解析】 如上面右图所示，它们的对面也同样的染色，这样就有(5+4+2)×2=22(个)方格染色，而且有公

共边的正方形颜色不同．所以，用红色染成的正方形的个数最多是22个．

【例 27】 证明：在6×6×6的正方体盒子中最多可放入52个1×l×4的小长方体，这里每个小长方体的

面都要与盒子的侧面平行．

8-6.构造与论证.题库 教师版 page 12 of 13 【解析】 先将6× 6×6的正方体盒子视为实体，那么6×6×6的正方体可分成216个小正方体，这216

个小正方体可以组成27个棱长为2的正方体．我们将这27个棱长为2的正方体按黑白相间染色，如下图所示．

其中有14个黑色的，13个白色的，而一个白色的2×2×2的正方体可以对应的放人4个每个面

都与盒子侧面平行的1×l×4的小长方体，所以最多可以放入13×4=52个1×1×4的小长方体． 注：6×6×6的正方体的体积为216，1×1×4的小长方体的体积为4，所以可放入的小正方体数目不超过216÷4=54个．

【例 28】 用若干个l×6和1×7的小长方形既不重叠，也不留孔隙地拼成一个11×12的大长方形，最少

要用小长方形多少个?

【解析】 我们先通过面积计算出最优情况：

11×12=132，设用1×6的小长方形x个，用1×7的小长方形y个，有6x?7x?132．

?x?1?7t解得：?（t为可取0的自然数)，共需x+y=19+t个小长方形．

y?18?6t? (1)当t=0时，即x+y=1+18=19，表示其中的1×6的小长方形只有1个，剩下的18个小长方形都

是

l×7的．

大长方形中无论是1行还是1列，最多都只能存在1个l×7的小长方形，所以在大长方形中最

多只能无重叠的同时存在16个l×7的小长方形．

现在却存在18个1×7的小长方形，显然不满足；

(2)当t=l时，即x+y=8+12=20，有如下分割满足，所以最少要用小长方形20个．

8-6.构造与论证.题库 教师版 page 13 of 13