haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

小学奥数构造与论证第二讲

发布时间:2014-05-06 13:58:57  

构造与论证第二讲

内容概述

组合证明题,在论证中,有时需进行分类讨论,有时则要着眼于极端情形,或从整体把握.若干点及连接它们的一些线段组成图,与此相关的题目称为图论问题,这里宜从特殊的点或线着手进行分析.各种以染色为内容,或通过染色求解的组合问题,基本的染色方式有相间染色与条形染色.

典型问题

2.甲、乙、丙三个班人数相同,在班级之间举行象棋比赛.各班同学都按l,2,3,4,…依次编号.当两个班比赛时,具有相同编号的同学在同一台对垒.在甲、乙两班比赛时,有15台是男、女生对垒;在乙、丙班比赛时,有9台是男、女生对垒.试说明在甲、丙班比赛时,男、女生对垒的台数不会超过

24.并指出在什么情况下,正好是24 ?

【分析与解】 不妨设甲、乙比赛时,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.

4.将15×15的正方形方格表的每个格涂上红色、蓝色或绿色.证明:至少可以找到两行,这两行中某一种颜色的格数相同.

【分析与解】 如果找不到两行的某种颜色数一样,那么就是说所有颜色的列与列之问的数目不同.那么红色最少也会占:

0+1+2+…+14=105个格子.

同样蓝色和绿色也是,这样就必须有至少:

3×(0+l+2+…+14)=315个格子.

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

6. 4个人聚会,每人各带2件礼品,分赠给其余3个人中的2人.试证明:至少有2对人,每对人是互赠过礼品的.

【分析与解】将这四个人用4个点表示,如果两个人之间送过礼,就在两点之间连一条线. 由于每人送出2件礼物,图中共有4×2=8条线,由于每人礼品都分赠给2个人,所以每两点之间至多有1+1=2条线.

四点间,每两点连一条线,一共6条线,现在有8条线,说明必有两点之间连了2条线,还有另外两点(有一点可以与前面的点相同)之间也连了2条线.

即为所证结论。

8.若干台计算机联网,要求:

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

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

③两台计算机之间如果没有电缆连接,则必须有另一台计算机和它们都连接有电缆.若按此要求最少要用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,…,Bk由于条件,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条线.

10.在一个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个方格涂成红色.

12. 证明:在6×6×6的正方体盒子中最多可放入52个1×l×4的小长方体,这里每个小长方体的面都要与盒子的侧面平行.

【分析与解】 先将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个.

14.用若干个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个.

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com