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

题库 教师版 3 1. 掌握最佳安排和选择方案的组合问题 . 2. 利用 基本染色 去解决相关图论 问题 知识点说明 各种探讨给定要求能否实现，在论证中，有时需进行分类讨论，有时则要着眼于极端情形，或从整体把握设计最佳安排和选择方案的组合问题，这里的最佳通常指某个量达到最大或最小解题时，既要构造出取得最值的具体实例，又要对此方案的最优性进行论证论证中的常用 手段包括抽屉原则、整除性分析和不等式估计 组合证明题，在论证中，有时需进行分类讨论，有时则需要着眼于极端情况，或从整体把握。若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题。若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题，这里宜从特殊的点或线着手进行分析各种以染色为内容，或通过染色求解的组合问题，基本的染色方式有相间染色与条形染色 板块一、 最佳安排和选择方案 【例 1】 一个盒子里有 400枚棋子，其中黑色和白色的棋子各 200枚 下面我们对这些棋子做如下操作：每次拿出 2 枚棋子，如果颜色相同，就补 1 枚黑色棋子回去；如果颜色不同，就补 1 枚白色的棋子回去这样的操作，实际上就是每次都少了 1 枚棋子，那么，经过 399 次操作后，最后剩下的棋子是 颜色 (填“黑”或者“白” ) 【解析】 在每一次操作中，若拿出的两枚棋子同色，则补黑子 1 枚，所以拿出的白子可能为 0 枚或 2 枚；若拿出的 两枚棋子异色，则补白子 1 枚， “两枚棋子异色 ”说明其中一黑一白，那么此时拿出的白子数为 0 枚可见每次操作中拿出的白子都是偶数枚，而由于起初白子有 200 枚，是偶数枚，所以每 次操作后剩下的白子都是偶数枚，因此最后 1 枚不可能是白子，只能是黑子 【巩固】 在黑板上写上 1 、 2 、 3 、 4 、 、 2008 ，按下列规定进行 “操怍 ”：每次擦去其中的任意两个数 a 和 b ，然后写上它们的差 (大数减小数 )，直到黑板上剩下一个数为止问黑板上剩下的数是奇数还是偶数？为什么？ 【解析】 根据等差数列求和公式，可知开始时黑板上所有数的和为 1 2 3 2 0 0 8 2 0 0 9 1 0 0 4 L 是一个偶数，而每一次 “操作 ”，将 a 、 b 两个数变成了 ()，它们的和减少了 2b ，即减少了一 个偶数那么从整体上看，总和减少了一个偶数，其奇偶性不变，还是一个偶数 所以每次操作后黑板上剩下的数的和都是偶数，那么最后黑板上剩下一个数时，这个数是个偶数 【例 2】 5 卷本百科全书按从第 1 卷到第 5 卷的递增序号排列，今要将它们变为反序排列，即从第 5 卷知识点拨 知识点拨 教学目标 8造与论证 题库 教师版 3 到第 1卷如果每次只能调换相邻的两卷，那么最少要调换多少次 ? 【解析】 因为必须是调换相邻的两卷，将第 5卷调至原来第 1卷的位置最少需 4次，得到的顺序为 51234； 现在将第 4卷调至此时第 次，得到的顺序为 54123； 现在将第 3卷调至此时第 次 ，得到的顺序为 54312； 最后将第 卷对调即可 所以，共需调换 4+3+2+1=10 次 【巩固】 在 1997 1997 的正方形棋盘上的每格都装有一盏灯和一个按钮按钮每按一次，与它同一行和同一列方格中的灯泡都改变一次状态，即由亮变为不亮，或由不亮变为亮如果原来每盏灯都是不亮的，请说明最少需要按多少次按钮才可以使灯全部变亮 ? 【解析】 最少要 1997 次，将第一列中的每一格都按一次，则除第一列外，每格的灯都只改变一次状态，由不亮变成亮而第一列每格的灯都改变 1997 次状态，由不亮变亮如果少于 1997次，则至少有一 列和至少有一行没有被按过，位于这一列和这一行相交处的灯保持原状，即不亮的状态 【例 3】 有 3 堆小石子，每次允许进行如下操作：从每堆中取走同样数目的小石子， 或是将其中的某一石子数是偶数的堆中的一半石子移入另外的一堆开始时，第一堆有 1989 块石子，第二堆有989块石子，第三堆有 89块石子问能否做到： 、 (1)某 2堆石子全部取光 ? (2)3堆中的所有石子都被取走 ? 【解析】 (1)可以，如 (1989， 989， 89) (1900， 900， 0) (950， 900， 950) (50， 0， 50) (25， 25，50) (O， 0， 25) (2)因为操作就两种，每堆取走同样数目的小石子，将有偶数堆石子堆中一半移至另一堆，所 以每次操作石子总数要么减少 3的倍数，要么不变 现在共有 1989+989+89=3067，不是 3的倍数，所以不能将 3堆中所有石子都取走 【巩固】 在 2009 张卡片上分别写着数字 1、 2、 3、 4、 、 2009，现在将卡片的顺序打乱，让空白面朝上，并在空白面上又分别写上 1、 2、 3、 4、 、 2009然后将每一张卡片正反两个面上的数字相加，再将这 2009 个和相乘，所得的积能否确定是奇数还是偶数？ 【解析】 从整体进行考虑所得的 2009 个和相加，便等于 1 2009 的所有数的总和的 2 倍，是个偶数 2009个数的和是偶数，说明这 2009 个数中必有偶数，那么这 2009 个数的乘积是偶数 本题也可以考虑其中的奇数由于 1 2009 中有 1005 个奇数，那么正反两面共有 2010 个奇数，而只有 2009 张卡片，根据抽屉原理，其中必有 2 个奇数在同一张卡片上，那么这张卡片上的数字的和是偶数，从而所有 2009 个和的乘积也是偶数 【例 4】 在某市举行的一次乒乓球邀请赛上，有 3名专业选手与 3名业余选手参 加 是说每两名选手都要比赛一场为公平起见，用以下方法记分：开赛前每位选手各有10分作为底分，每赛一场，胜者加分，负者 扣分，每胜专业选手一场加 2 分，每胜业余选手一场加 1 分；专业选手每负一场扣 2 分，业余选手每负一场扣 1 分问：一位业余选手最少要胜几场，才能确保他的 得分比某位专业选手高 ? 【解析】 当一位业余选手胜 2场时，如果只胜了另两位业余选手，那么他得 10+2(分 )此时，如果专业选手间的比赛均为一胜一负，而专业选手与业余选手比赛全胜，那么每位专业选手的得分都是10+2=13(分 )所以，一位业余选手胜 2场，不能确保他的得分比某位专业选手高 当一位业余选手胜 3 场时，得分最少时是胜两位业余选手，胜一位专业选手，得10+2+22(分 )此时，三位专业选手最多共得 30+0+4=34(分 )，其中专业选手之间的三场比赛共得 0分，专业选手与业余选手的比赛最多共得 4分 4分， 34 3=1113，推知，必有人得分不超过 11 分 . 也就是说，一位业余选手胜 3场，能确保他的得分比某位专业选手高 . 【例 5】 赛采用单循环制，即每对均与其他各队比赛一场 分，平一场得 1分，负一场得 0分 且所有各队的积分都不相同，问： 题库 教师版 3 （ 1） n=4是否可能？ （ 2） n=5是否可能？ 【解析】 （ 1）我们知道 4个队共进行了 24每场比 赛有 2分产生，所以 4个队的得分总和为 24C 2=以得分最低的队至少得 2分，又要求每个队的得分都不相同，所以 4个队得分最少 2+3+4+5=14 12，不满足 .即 n=4不可能。 （ 2）我们知道 5 个队共进行 25每场比赛有 2分产生，所以 4个队的得分总和为 25C2=以得分最低的队至少得 2 分，又要求每个 队的得分都不相同，所以 5个队得分最少为 2+3+4+5+6=20，满足 .即 n=5有可能 如下所示， 分， 分， 分， 分， 分 A B”表示 A、 胜 B；“ 示 B、 ，余下类推 . 【例 6】 如 图 35 1， 2， 3， 4， 5， 6， 7， 8， 9， 10这 10 个数分别填入图中的 10个圆圈内，使任意连续相邻的 5 个圆圈内的各数之和均不大于某个整数 的最小值并完成你的填图 . 【解析】 要 使 要尽量平均的填写，因为如果有的连续 5个圆圈内的数特别小，有的特别大，那么 能达到尽量小的目的 因为每个圆圈内的数都用了 5次，所以 10次的和为 5 (1+2+3+ +10)=275 每次和都小于等于朋，所以 75，整数 8 下面来验证 M=28时是否成立，注意到圆圈内全部数的总和是 55，所以肯定是一边五个的和是 28， 一边是 27因为数字都不一样，所以和 28肯定是相间排列，和 27也是相问排列，也就是说数 组每隔 4个差值为 l，这样从 1填起，容易排出适当的填图 . 【例 7】 （ 2009年清华附中入学测试题）如图，在时钟的表盘上任意作 9 个 120 的扇形，使得每一个扇形都恰好覆盖 4 个数，且每两个扇形覆盖的数不全相同，求证：一定可以找到 3 个扇形，恰好覆盖整个表盘上的数并举一个反例说明，作 8 个扇形将不能保证上述结论成立 11109876 5432112【解析】 要 在表盘上共可作出 12 个不同的扇形，且 1 12 中的每个数恰好被 4 个扇形覆盖将这 12 个扇形分为 4 组，使得每一组的 3 个扇形恰好盖住整个表盘那么，根据抽屉原理，从中选择 9 个扇 题库 教师版 3 形，必有 9 134个扇形属于同一组，那么这一组的 3 个扇形可以覆盖整个表盘 另一方面，作 8 个扇形相当于从全部的 12 个扇形中去掉 4 个，则可以去掉盖住同一个数的 4 个扇形，这样这个数就没有被剩下的 8 个扇形盖住，那么这 8 个扇形不能盖住整个表盘 【巩固】 （ 2008 年台湾小学数学竞赛选拔赛）将 1、 2、 3、 4、 5、 6 写在一个圆周上，然后把圆周上连续三个数之和写下来，则可以得到六个数1a、2a、3a、4a、5a、6a，将这六个数中最大的记为 A 请问在所有填写方式中， A 的最小值是什么？ 632541【解析】 要 由 于 每 个 写 在 圆 周 上 的 数 都 被 用 了 三 次 ， 则1 2 3 4 5 6 3 ( 1 2 3 4 5 6 ) 6 3a a a a a a ，即写出来的这 6 个数的平均数为 因此 A 至少为 11由上图的排列方式可知 A 为 11 的情形存在，故 A 的最小值为 11 【例 8】 1998 名运动员的号码依次为 1 至 1998 的自然数现在要从中选出若干 名运动员参加仪仗队，使得剩下的运动员中没有一个人的号码等于另外两人的号码的乘积那么，选为仪仗队的运动员最少有多少人 ? 【解析】 我 们很自然的想到把用得比较多的乘数去掉，因为它们参与的乘式比较多，把它们去掉有助于使剩下的构不成乘式，比较小的数肯定是用得最多的，因为它们的倍数最多，所以考虑先把它们去掉，但关键是除到何处 ? 考虑到 44 的平方为 1936，所以去到 44 就够了，因为如果剩下的构成了乘式，那么乘式中最小的数一定小于等于 44，所以可以保证剩下的构不成乘式因为对结果没有影响，所以可以将 1保留，于是去掉 2， 3， 4， 44这 43个数 但是，是不是去掉 43个数为最小的方法呢 ?构造 2 97， 3 96， 4 95， 44 45，发现这 43组数全不相同而且结果都比 1998小，所以要去掉这些乘式就至少要去掉 43个数，所以 43 位最小值，即为所求 . 【例 9】 一 组互不相同的自然数，其中最小的数是 l，最大的数是 25，除 1 之外，这组数中的任一个数或者等于这组数中某一个数的 2倍，或者等于这组数中某两个数之和 组数之和的最小值是多少 ?当取到最小值时 ，这组数是怎样构成的 ? 【解析】 首先把这组数从小到大排列起来，那么最小的肯定为 1， 1后面只能是 1的 2倍即 2， 2后面可以是 3或 4， 3的后面可以是 4， 5， 6； 4的后面可以是 5， 6， 8最大的为 25下面将所有的可能情况列出： l， 2， 3， 4， 25 所有的和是 35； l， 2， 3， 5， 25 所有的和是 36； 1， 2， 3， 6， 25 所有的和是 37； 1， 2， 4， 5， 25 所有的和是 37； 1， 2， 4， 6， 25 所有的和是 38； 1， 2， 4， 8， 25 所有的和是 40. 25 是奇数，只能是一个偶数加上一个奇数在中间 省略的数中不能只有 1 个数，所以至少还要添加两个数，而且这两个数的和不能小于 25，否则就无法得到 25这个数要求求出最小值，先看这两个数的和是 25 的情况，因为省略的两个数不同于前面的数，所以从 20+5开始 25=20+5=19+6=18+7=17+8=16+9=15+10=14+11=13+12 题库 教师版 3 这些数中 20， 19， 18， 17太大，无法产生，所以看： 16+9=15+10=14+11=13+12 看这些谁能出现和最小的 l， 2， 3， 4， 25 中，检验发现没有可以满足的： 再看 l， 2， 3， 5， 25，发现 1， 2， 3， 5， 10， 15， 25 满足，所以： 1+2+3+5+10+15+25=36+25=61 【例 10】 2004 枚棋子，每次可以取 1、 3、 4、 7 枚，最后取的获胜。甲、乙轮流取，如果甲先取，如何才能保证赢？ 【解析】 先从简单的情况看起，看看棋子数量较少时，在什么情况下先取者胜，什么情况下后取者胜 可以列表如下： 棋子数量 先取者胜 后取者胜 1 枚 2 枚 3 枚 4 枚 5 枚 ( 3 1 1) 6 枚 ( 4 1 1) 7 枚 8 枚 9 枚 ( 1 8) 10 枚 11 枚 ( 3 8) 12 枚 ( 4 8) 13 枚 ( 3 10) 14 枚 ( 4 10) 15 枚 ( 7 8) 16 枚 17 枚 ( 1 16) 18 枚 19 枚 ( 3 16) 20 枚 ( 4 16) 棋子数是 1 8 时比较容易看得出来是先取者胜还是后取者胜，可以看出只有棋子数是 2 枚和 8枚时是后取者胜，其他情况下都是先取者胜 当棋子数大于 8 时，可以先取若干枚棋子，使得剩下的棋子数变成前面已有的棋子数 先取者为了取胜，第一次取后，应该使剩下的棋子数是后取者胜的情况，比如变成剩下 2 枚或 8 枚 这样推下去，可以发现只有当棋子数是 8 的倍数或者除以 8 余 2 时，是后取者胜，其他情况下是先取者胜 题目中有 2004 枚棋子，除以 8 余 4，所以先取者肯定可以取胜 不过取胜的策略比较灵活，不能明确地说每次后取者取多少枚先取者就相应地取多少枚，应该从除以 8 的余数来考虑： 先取者第一次可以先取 4 枚，这样还剩下 2000 枚， 2000 除以 8 的余数是 0； 先取者为了保证获胜，在每一次后取者取了之后，先取者再取的时候，应该使得自己取后剩下的棋子数是 8 的倍数或者除以 8 余 2； 后取者每次可以取 1， 3， 4， 7 枚，每次先取者取后 剩下的棋子数除以 8 的余数是 0 或 2，所以每次后取者取后剩下的棋子数除以 8 的余数是 7， 5， 4， 1 或 1， 7， 6， 3. 所以接下来先取者可以对应地取 7， 3， 4， 1 或 1， 7， 4， 3 枚棋子，这样剩下的剩下的棋子数除以 8 的余数为 0， 2， 0， 0 或 0， 0， 2， 0. 这样就保证了第 点 每次先取者取后剩下的棋子数除以 8 的余数是 0 或 2，那么最后一枚棋子肯定是先取者取得，所以先取者获胜 题库 教师版 3 【巩固】 桌子上放着 55 根火柴，甲、乙二人轮流每次取走 1 3 根，规定谁取走最后一根火柴谁获胜如果双方都采用最佳方法，甲先取，那么谁将获胜？ 【解析】 采用逆 推法分析获胜方在最后一次取走最后一根；往前逆推，在倒数第二次取时，必须留给对方 4 根，此时无论对方取 1、 2 或 3 根，获胜方都可以取走最后一根；再往前逆推，获胜方要想留给对方 4 根，在倒数第三次取时，必须留给对方 8 根由此可知，获胜方只要每次留给对方的都是 4 的倍数根，则必胜现在桌上有 55 根火柴， 55 4 13 3L ，所以只要甲第一次取走 3根，以后每一次，乙取几根，甲就取 4 减几根，使得每次甲取后剩下的火柴根数都是 4 的倍数，这样甲必胜 为什么一定要留给对方 4 的倍 数根火柴，而不是 5 的倍数根或者其它数的倍数根呢？关键在于规定每次只能取 1 3 根， 1 3 4 ，这样乙每次取 a 根，而甲取 4 a 根，能保证 4 a 也在 1 3 的范围内 【巩固】 有 3 堆小石子，每次允许进行如下操作：从每堆中取走同样数目的小石子，或是将其中的某一石子数是偶数的堆中的一半石子移入另外的一堆 开始时，第一堆有 1989 块石子， 第二堆有 989块石子，第三堆有 89 块石子 问，能否做到：某 2 堆石子全部取光？ 3 堆中的所有石子都被取走？ 【解析】 要使得某两堆石子全部取光，只需使得其中有两堆的石子数目一样多，那么如果我们把最少的一堆先取光，只要剩下的两堆中有一堆数目是偶数，再平分一下就可以实现了 而题中数字正好能满足要求 所以，全部取光两堆是可以的 对于第二个问题，要取走全部 3 堆，则必须 3 堆石子的总数是 3 的倍数才有可能，但 1989、 989、89 之和并非 3 的倍数，所以是不可能的 可以取光其中的两堆石子 如进行如下的操作： 第 1 堆 第二堆 第三堆 1989 989 89 1900 900 0 (第一步：三堆各取走 89 块 ) 1900 450 450 (第二步：第二堆 900 是偶数，将其一半移入第三堆 ) 1450 0 0 (第三步：三堆各取走 450 块 ) 不能将三堆全部取光 因为每一次取走石子是从三堆中同时取走相同数目的石子，那么每次取走的石子数都是 3 的倍数，则不论怎么取，取走的石子总数是 3 的倍数， 而 1 9 8 9 9 8 9 8 9 3 0 6 7 ， 3067 被 3 除余 1，不是 3 的整数倍 ，所以不能将三堆石子全部取光 【例 11】 在 1019 方格表的每个方格内，写上 0或 1，然后算出每行及每列的各 数之和问最多能得到多少个不同的和数 ? 【解析】 首 先每列的和最少为 0，最多是 10，每行的和最少是 0，最多是 19，所以不同的和最多也就是 0，1， 2， 3， 4， 18， 19这 20个 下面我们说明如果 0出现，那么必然有另外一个数字不能出现 如果 0 出现在行的和中，说明有 1 行全是 0，意味着列的和中至多出现 0 到 9，加上行的和至多出现 10 个数字，所以少了一种可能 如果 0 出现在列的和中，说明在行的和中 19 不可能出现，所以 0 出现就意味着另一个数字不能出现，所以至多是 19，下面给出一种排出方法 . 题库 教师版 3 【例 12】 在 8 8的国际象棋盘上最多能够放置多少枚棋子，使得棋 盘上每行、每列及每条斜线上都有偶数枚棋子 ? 【解析】 因为 8 8的国际象棋盘上的每行、每列都正好有偶数格，若某行 (某列 )有空格，必空偶数格而斜线上的格子数有奇也有偶，不妨从左上角的斜线看起：第一条斜线只有 1格，必空；第三条有3 格，必至少空 1 格；第五、七条分别有 5、 7 格，每条线上至少空 1 格由对称性易知共有 16条斜线上有奇数格，且这 16 条斜线没有共用的格子，故至少必空出 16 格其实，空出两条主对角线上的 16 个格子就合题意此时，最多可放置 48枚棋子，放在除这两条主对角线外的其余格子中，如下图所示 【例 13】 在 下 图中有 16 个黑点，它们排成了一个 44 的方阵用线段连接 其中 4 点，就可以画出各种不同的正方形现在要去掉某些点，使得其中任意 4 点都不能连成正方形，那么最少要去掉多少个点 ? 【解析】 至 少要除去 6个点，如下所示为几种方法： 【例 14】 三个边长为 1的正方形并排放在一起，成为 13 的长方形 1 2 3 9 0 o. 【解析】 仔细分析，要证 1 2 3 9 0 o， 由于 3 45o ，所以，只需证 明 1 2 45 o 就可以了！于是想到能否把 2 （ 1 ）移动位 置，与 1 （ 2 ）拼合在一起，恰成一个 45o 的角呢？于是想到：如图 1所示，再拼上一个单位正方形 三角形 45o ，又直角三角形 题库 教师版 3 以 2 . 因此， 1 2 1 4 5K C F K C A o. 有了拼合 2 与 1 的思想，学生往往产生不同的拼合方式，沿着拼合全等的思路发散开来，又可以找到许多拼法 . 如图 2三角形 45o ， 2 , 1 G B A P 所以 1 2 4 5B A P H A G H A P o. 如图 3三角形 45o ， 2, 12 1 4 5Q C P o. 如图 4三角形 等腰直角三角形 , 4 5 , 1 ,W D B C D B o ， 2 . 所以1 2 4 5C D B W D H W D B o. 如图 5三角形 4 5 , 1 ,Z H A Z H Y o 因此12 2 4 5Z H Y Z H A o. 其他的沿着“拼合全等”的思路的证法就不例举了 . 如果利用相似三角形的知识，如图 5所示，又 1 , 2 , 2 ,F H F A F C 所以， 12 ,22F H F F C ，因此 ， 2,F H A F A C 但1 ， 1 2 4 5C A B F A C E A B o. 用相似三角形法不用添设辅助线，简洁明了 用三角法证明如下： 2 与 1 都是小于 45o 的锐角，可知 1 + 2 是锐角 . 又1 3 ， 1ta n 2 2 . 1 1 5t a n 1 t a n 2 3 2 6t a n 1 2 11 1 11 t a n 1 t a n 2 113 2 6 ，所以 1 2 45 o . 题库 教师版 3 板块二、染色 与 赋值 问题 【例 15】 某学校的学生中，没有一个学生读过学校图书馆的所有图书，又知道图书馆内任何两本书都至少被一个同学都读过问：能否找到两个学生甲、乙和三本书 4、 B、 C，使得甲读过 A、 B，没读过 C，乙读过 B、 C，没读过 A?说明判断过程 【解析】 首先从读书数最多的学生中找一人甲由题设，甲至少有一本书未读过，记为 C设 B 是甲读过的书中一本，由题意知，可找到学生乙，乙读过 B、 C由于甲是读书数最多的学生之一，乙读书数不能超过甲的读书数，而乙读过 C 书，甲未读过 C 书，所以一定可以找出一本书 A，使得甲读过而乙未读过，否则乙就比甲至少多 读过一本书这样一来，甲读过 A、 B，未读过 C；乙读过 B、 【例 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 人能用同一种语言交谈。 【解析】 假设任意三位数学家都没有共同会的语言，这表明每种语言至多有两人会说 B、 C、 D、 E、 F、 G、 I由于一位数学家最多会三种语言，而每种语言至多有两人会说，所以一位数学家至多能和另外三人通话，即至少与五人语言不通不妨设 、 C、 D、 E、 同理， 此在 C、 D、 E、 语言不通，设为 、 B、题意矛盾这表明假设不成立，结论得证 【例 18】 在 10001000 的方格表中任意选取 存在 3个红色 方格，它们的中心构成一个直角三角形的顶点求 【解析】 首 先确定 1998不行反例如下： 其次 1999可能是可以的，因为首先从行看， 1999个红点分布在 1000行中， 肯定有一些行含有 2个或者以上的红点，因为含有 0或 1个红点的行最多 999个，所以其他行含有红点肯定大于等于 1999000，如果是大于 1000，那 么根据抽屉原理，肯定有两个这样红点在一列，那么就会出现红 色三角形； 如果是等于 1000而没有这样的 2个红点在一列，说明有 999行只含有 1个 红点，而剩下的一行全是红点，那也肯定已经出现直角三角形了，所以 999 【例 19】 甲 、乙、丙三个班人数相同，在班级之间举行象棋比赛各班同学都按 l， 2， 3， 4， 依次编号当两个班比赛时，具有相同编号的同学在同一台对垒在 甲、乙两班比赛时，有 15台是男、女生对垒；在乙、丙班比赛时，有 9 台是男、 女生对垒试说明在甲、丙班比赛时，男、女生对垒的台数不会超过 24并 指出在什 么情况下，正好是 24 ？ 题库 教师版 0 3 【解析】 不妨设甲、乙比赛时， 1 15 号是男女对垒，乙、丙比赛时在 1 15 号中有 a 台男女对垒， 15号之后有 90 a 9) 甲、丙比赛时，前 15号，男女对垒的台数是 15果 1号乙与 1号丙是男女对垒，那么 1号甲与 1号丙就不是男女对垒 )， 15 号之后，有 9男女对垒 比赛时，男女对垒的台数为 15424 仅在 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，从这些长方形中选出 不同的长方形，其面积和最小为： 1 1+1 2+1 3+1 4+2 2+1 5+1 6+2 3+1 7+1 8=46而原长方形的面积为 5 9=4546所以分出的长方形必定有某两个是完全一样的 【例 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 点连接，共可连接出 27C 27C=7 62=21条线段现在只连接 18条线段，有 3条没有连出，要使得这 18条线段所构成的三角形最多，需使得没连出的这 3 条线段 共同参与的三角形总数最多，故这 3 条线断共点 条线段中的任何一条，还与其他 5个点本应构成 5个三角形，故这 3条线段没连出，至少少构成 5 32个三角形 . 如上图所示，在图中 为其中 以减去 3而平面内任何三点不共线的 7个点，若任何 2点连线，最多可构成 37C =35个三角形故现在最多可构成三角形 353个 【例 23】 在 9 9棋盘的每格中都有一只甲虫，根据信号它们同时 沿着对角线各自爬到与原来所在格恰有一个公共顶点的邻格中，这样某些格中有若干只甲虫，而另一些格则空着问空格数最少是多少 ? 【解析】 方法一：考虑到甲虫总是斜着爬，我们把棋盘黑白相间染色，发现原来黑色格子里的甲虫都会爬 题库 教师版 1 3 到黑色的格子里面，而白色格子里面的甲虫都会爬到白色格子里面，所以我们只用观察最少能空出多少个黑格子，多少个白格子 因为甲虫每次都从奇数行爬到偶数行，偶数行爬到奇数行，而由奇数行有 25 个黑格子，偶数行有 16 个黑格子知，偶数行的 16 只甲虫爬到奇数行会空出 9 个黑格子，而奇数行的 25 只虫子爬到偶数行就可以没有空 格白格子虫子也会从奇数行爬到偶数行，偶数行爬到奇数行，但是奇数行和偶数行都是 20个格子，最少的情况下不会出现空格子，所以最少出现 9个空格 方法二： 对 2 2棋盘如下黑白染色，则易知两黑格及两白格分别对换甲虫即可使棋盘格不空；从而得到 2n 2 2棋盘，棋盘格均不空 对 3 3棋盘如下黑白染色，注意到图中有 5个黑格，黑格中的甲虫爬行后必进入黑格，且四个角上的黑格内的甲虫必爬人中心黑格，而中心黑格内的甲虫只能爬人某一格，必至少空 3个黑格 对 5 5棋盘黑白染色后，利用、的结论 易知至少空 5个黑格 依次类推，可知对 9 9棋盘黑白染色后，至少空 9个空格下图是甲虫爬行的一种方法 【例 24】 若 干台计算机联网，要求： 任意两台之间最多用一条电缆连接； 任意三台之间最多用两条电缆连接； 两台计算机之间如果没有电缆连接，则必须有另一台计算机和它们都连 接有电缆若按此要求最少要用 79条电缆 问： (1)这些计算机的数量是多少台 ? (2)这些计算机按要求联网，最多可以连多少条电缆 ? 【解析】 将机器当成点，连接电缆当成线 ，我们就得到一个图，如果从图上一个点出发，可以沿着线跑到图上任一个其它的点，这样的图就称为连通的图，条件表明图是连通图 我们看一看几个点的连通图至少有多少条线可以假定图没有圈 (如果有圈，就在圈上去掉一条线 )，从一点出发，不能再继续前进，将这一点与连结这点的线去掉考虑剩下的 仍然是连通的用同样的办法又可去掉一点及一条线这样继续下去，最后只剩下一个点因此 n 个点的连通图至少有 如果有圈，线的条数就会增加 )，并且从一点 样的图恰好 有 因此， (1)的答案是 n=79+1=80，并且将一台计算机与其他 79 台各用一条线相连，就得到符合要求的联网 下面看看最多连多少条线 在这 80 个点 (80台计算机 )中，设从1 1B，题库 教师版 2 3 由于条件，1B,2B， 设与1A， m+k=80，而2A，3A , 中至多有 线，因为40B 24 ( )m k m k 2( ) 6 4 0 0 所以 m k 1600，即