36_构造与论证(二).doc

组合证明题，在论证中，有时需进行分类讨论，有时则要着眼于极端情形，或从整体把握若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题，这里宜从特殊的点或线着手进行分析各种以染色为内容，或通过染色求解的组合问题，基本的染色方式有相间染色与条形染色1 某学校的学生中，没有一个学生读过学校图书馆的所有图书，又知道图书馆内任何两本书都至少被一个同学都读过问：能否找到两个学生甲、乙和三本书4、B、C，使得甲读过A、B，没读过C，乙读过B、C，没读过A?说明判断过程【分析与解】 首先从读书数最多的学生中找一人甲由题设，甲至少有一本书未读过，记为C 设B是甲读过的书中一本，由题意知，可找到学生乙，乙读过B、C 由于甲是读书数最多的学生之一，乙读书数不能超过甲的读书数，而乙读过C书，甲未读过C书，所以一定可以找出一本书A，使得甲读过而乙未读过，否则乙就比甲至少多读过一本书这样一来，甲读过A、B，未读过C；乙读过B、C未读过A 因此可以找到满足要求的两个学生2甲、乙、丙三个班人数相同，在班级之间举行象棋比赛各班同学都按l，2，3，4，依次编号当两个班比赛时，具有相同编号的同学在同一台对垒在甲、乙两班比赛时，有15台是男、女生对垒；在乙、丙班比赛时，有9台是男、女生对垒试说明在甲、丙班比赛时，男、女生对垒的台数不会超过24并指出在什么情况下，正好是24 ？ 【分析与解】 不妨设甲、乙比赛时，115号是男女对垒，乙、丙比赛时在115号中有a台男女对垒，15号之后有9-a台男女对垒(0a9) 甲、丙比赛时，前15号，男女对垒的台数是15-a(如果1号乙与1号丙是男女对垒，那么1号甲与1号丙就不是男女对垒)，15号之后，有9-a台男女对垒.所以甲、丙比赛时，男女对垒的台数为 15-a+9-a=24-2a24 仅在a=0，即必须乙、丙比赛时男、女对垒的号码，与甲、乙比赛时男、女对垒的号码完全不同，甲、丙比赛时，男、女对垒的台数才等于243. 将59的长方形分成10个边长为整数的长方形证明：无论怎样分法分得的长方形中必有两个是完全相同的 【分析与解】 10个边长为整数的长方形，其面积显然也均是正整数 划分出的长方形按面积从小到大为： 11，12，l3，14，22，15，16，23，17，18，24，19，3325，26，34，27，35，28，44，29，36， 从这些长方形中选出lO个不同的长方形，其面积和最小为： 11+12+13+14+22+15+16+23+17+18=46 而原长方形的面积为59=4546 所以分出的长方形必定有某两个是完全一样的4将1515的正方形方格表的每个格涂上红色、蓝色或绿色证明：至少可以找到两行，这两行中某一种颜色的格数相同 【分析与解】 如果找不到两行的某种颜色数一样，那么就是说所有颜色的列与列之问的数目不同那么红色最少也会占： 0+1+2+14=105个格子 同样蓝色和绿色也是，这样就必须有至少： 3(0+l+2+14)=315个格子 但是，现在只有1515=225个格子，所以和条件违背，假设不成立，结论得证5. 有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三人中任意两人都没有共同语言，与题意矛盾 这表明假设不成立，结论得证6. 4个人聚会，每人各带2件礼品，分赠给其余3个人中的2人试证明：至少有2对人，每对人是互赠过礼品的【分析与解】将这四个人用4个点表示，如果两个人之间送过礼，就在两点之间连一条线 由于每人送出2件礼物，图中共有42=8条线，由于每人礼品都分赠给2个人，所以每两点之间至多有1+1=2条线 四点间，每两点连一条线，一共6条线，现在有8条线，说明必有两点之间连了2条线，还有另外两点(有一点可以与前面的点相同)之间也连了2条线即为所证结论。7. 在平面上有7个点，其中任意3个点都不在同一条直线上如果在这7个点之字连结18条线段，那么这些线段最多能构成多少个三角形 ? 【分析与解】平面上这7个点，任意3点都不在同一条直线上，若任意2点连接，共可连接出=762=21条线段 现在只连接18条线段，有3条没有连出，要使得这18条线段所构成的三角形最多，需使得没连出的这3条线段共同参与的三角形总数最多，故这3条线断共点.对于这3条线段中的任何一条，还与其他5个点本应构成5个三角形，故这3条线段没连出，至少少构成53-3=12个三角形 如上图所示，在图中AD、AE、AF之间未连接，因为其中ADE、AED，ADF、AFD，AEF、AFE被重复计算，所以减去3而平面内任何三点不共线的7个点，若任何2点连线，最多可构成=35个三角形故现在最多可构成三角形35-12=23个8若干台计算机联网，要求： 任意两台之间最多用一条电缆连接； 任意三台之间最多用两条电缆连接； 两台计算机之间如果没有电缆连接，则必须有另一台计算机和它们都连接有电缆若按此要求最少要用79条电缆 问：(1)这些计算机的数量是多少台? (2)这些计算机按要求联网，最多可以连多少条电缆? 【分析与解】将机器当成点，连接电缆当成线，我们就得到一个图，如果从图上一个点出发，可以沿着线跑到图上任一个其它的点，这样的图就称为连通的图，条件表明图是连通图 我们看一看几个点的连通图至少有多少条线可以假定图没有圈(如果有圈，就在圈上去掉一条线)，从一点出发，不能再继续前进，将这一点与连结这点的线去掉考虑剩下的n-1个点的图，它仍然是连通的用同样的办法又可去掉一点及一条线这样继续下去，最后只剩下一个点因此n个点的连通图至少有n-1条线(如果有圈，线的条数就会增加)，并且从一点A向其他n-1个点各连一条线，这样的图恰好有n-1条线 因此，(1)的答案是n=79+1=80，并且将一台计算机与其他79台各用一条线相连，就得到符合要求的联网 下面看看最多连多少条线 在这80个点(80台计算机)中，设从引出的线最多，有k条，与相连的点是,，由于条件，,，之间没有线相连 设与不相连的点是，则m+k=80，而，, 每一点至多引出k条线，图中至多有mk条线，因为 所以mk1600，即连线不超过1600条另一方面，设80个点分为两组：,，；，第一组的每一点与第二组的每一点各用一条线相连，这样的图符合题目要求，共有4040=1600条线9. 在99棋盘的每格中都有一只甲虫，根据信号它们同时沿着对角线各自爬到与原来所在格恰有一个公共顶点的邻格中，这样某些格中有若干只甲虫，而另一些格则空着问空格数最少是多少? 【分析与解】方法一：考虑到甲虫总是斜着爬，我们把棋盘黑白相间染色，发现原来黑色格子里的甲虫都会爬到黑色的格子里面，而白色格子里面的甲虫都会爬到白色格子里面，所以我们只用观察最少能空出多少个黑格子，多少个白格子 因为甲虫每次都从奇数行爬到偶数行，偶数行爬到奇数行，而由奇数行有25个黑格子，偶数行有16个黑格子知，偶数行的16只甲虫爬到奇数行会空出9个黑格子，而奇数行的25只虫子爬到偶数行就可以没有空格 白格子虫子也会从奇数行爬到偶数行，偶数行爬到奇数行，但是奇数行和偶数行都是20个格子，最少的情况下不会出现空格子，所以最少出现9个空格 方法二：对22棋盘如下黑白染色，则易知两黑格及两白格分别对换甲虫即可使棋盘格不空；从而得到2n2n棋盘可划分为若干块22棋盘，棋盘格均不空 对33棋盘如下黑白染色，注意到图中有5个黑格，黑格中的甲虫爬行后必进入黑格，且四个角上的黑格内的甲虫必爬人中心黑格，而中心黑格内的甲虫只能爬人某一格，必至少空3个黑格 对55棋盘黑白染色后，利用、的结论易知至少空5个黑格 依次类推，可知对99棋盘黑白染色后，至少空9个空格下图是甲虫爬行的一种方法10在一个66的方格棋盘中，将若干个11的小方格染成红色如果随意划掉3行3列，在剩下的小方格中必定有一个是红色的那么最少要涂多少个方格? 【分析与解】方法一：显然，我们先在每行、每列均涂一个方格，使之成为红色，如图A所示，但是在图B中，划去3行3列后，剩下的方格没有红色的，于是再将两个方格涂成红色(依据对称性，应将2个方格同时涂成红色)，如图C所示，但是图D的划法，又使剩下的方格没有红色，于是再将两个方格涂成红色(还是由于对称的缘故，将2个方格涂成红色)，得到图E，图E不管怎么划去3行3列，都能使剩下的方格含有红色的 这时共涂了10个方格 方法二：一方面，图F表明无论去掉哪三行哪三列总会留下一个涂红的方格 另一方面，如果只涂9个红色方格，那么红格最多的三行至少有6个红格(否则第三多的行只有1个红格，红格总数5+3=8)，去掉这三行至多还剩3个红格，再去掉三列即可将这三个红格也去掉 综上所述，至少需要将10个方格涂成红色11.如图36-1，把正方体的6个表面剖分成9个相等的正方形现用红、黄、蓝3种颜色去染这些小正方形，要求有公共边的正方形所染的颜色不同那么染成红色的正方形的个数最多是多少个? 【分析与解】 如下图所示，它们的对面也同样的染色，这样就有(5+4+2)2=22(个)方格染色，而且有公共边的正方形颜色不同 所以，用红色染成的正方形的个数最多是22个12. 证明：在666的正方体盒子中最多可放入52个1l4的小长方体，这里每个小长方体的面都要与盒子的侧面平行 【分析与解】 先将6 66的正方体盒子视为实体，那么666的正方体可分成216个小正方体，这216个小正方体可以组成27个棱长为2的正方体我们将这27个棱长为2的正方体按黑白相间染色，如下图所示 其中有14个黑色的，13个白色的，而一个白色的222的正方体可以对应的放人4个每个面都与盒子侧面平行的1l4的小长方体，所以最多可以放入134=52个114的小长方体评注：666的正方体的体积为216，114的小长方体的体积为4，所以可放入的小正方体数目不超过2164=54个13在88的方格表选择8个不相交的22小正方形染色证明：至少存在1个22小正方形与所有染色的小正方形都不相交(这里的相交指包含公共方格) 【分析与解】 考虑到这道题的目标是1个22小正方形，所以选择把88的方格染上9个22的小正方形 可以均匀的染出33=9个22的黑色区域，如下图所示： 如果放8个小正方形进去，每个至多和一个黑色区域相交，所以8个小正方形至多与8个黑色区域相交，所以存在一个黑色区域和这8个正方形都不相交。而这个黑色区域就是一个22的小正方形14用若干个l6和17的小长方形既不重叠，也不留孔隙地拼成一个1112的大长方形，最少要用小长方形多少个? 【分析与解】我们先通过面积计算出最优情况： 1112=132，设用16的小长方形x个，用17的小长方形y个，有解得：（t为可取0的自然数)，共需x+y=19+t个小长方形 (1)当t=0时，即x+y=1+18=19，表示其中的16的小长方形只有1个，剩下的18个小长方形都是l7的 大长方形中无论是1行还是1列，最多都只能存在1个l7的小长方形，所以在大长方形中最多只能无重叠的同时存在16个l7的小长方形 现在却存在18个17的小长方形，显然不满足； (2)当t=l时，即x+y=8+12=20，有如下分割满足，所以最少要用小长方形20个15欲将一张方格表中的每个小方格染为红色或蓝色，使得每个与红色小方格有公共边的小方格中恰有一个蓝色小方格，而每