染色中的抽屉原理
5页1、染色中的抽屉原理根据抽屉原理可以解决许多有趣的问题,关键在于根据不同的问题制造抽屉.如研究整除问题时常用剩余类当作抽屉,研究长度和面积时用图形制造抽屉等等.在这一讲中将研究如何用颜色当作抽屉来解决一些问题。 例 1 平面上有 A、B、C、D、E、F 六个点,其中没有三点共线,每两点之间任意选用红线或蓝线连接,求证:不管怎样连接,至少存在一个三边同色的三角形。 分析与解答 连彩线的方式很多,如果一一画图验证结论,显然是不可取的.这个问题如果利用抽屉原理去解决,就不是难事了。 我们用虚线表示红色,用实线表示蓝色.从任意一点比如点 A 出发,要向B.C、D、E、F 连 5 条线段.因为只有两种颜色,所以根据抽屉原理,至少有 3 条线段同色.不妨设 AB、AD、AE 三线同红色(如右图).如果 B、D、 E 这三点之间所连的三条线段中有一条是红色的,则出现一个三边为红色的三角形.如果这三点之间所连线段都不是红色,那么就都是蓝色的.这样,三角形 BDE 就是一个蓝色的三角形.因此,不管如何连彩线,总可以找到一个三边同色的三角形。 如果我们把上面例题中的点换成人,把红蓝两种颜色连线换成人与人之间的
2、关系,又可以解决某些实际问题.如:证明在任意的 6 个人之间,或者有 3 个人互相认识,或者有 3人互相都不认识。 我们只需把互相认识的两人用红线连接,互相不认识用蓝线连接,那么所要证明的结论就变成证明存在一个红色或蓝色的三角形了。 例 2 从同一个小学毕业的同学之间的关系可以分为三个等级:关系密切、一般关系、毫无关系.请你证明在这个学校的 17 名校友中.至少有三个人,他们之间的关系是同一个等级的。分析与解答 把 17 人看成平面上 17 个点;用红、蓝、白三种颜色的连线表示同学之间三种不同等级关系.那么这个实际问题就转化为:证明用红、蓝、白三种颜色的线段连接平面上的 17 个点(没有三点共线),一定存在一个同色的三角形。 因为一个点要与其他 16 个点连线,只有三种颜色,所以根据抽屉原理,从一点至少引出 6 条同色的线段.不妨设点 A 与 B、C、D、E、F、G 六点是用白色线段连接的.如果B、C、D、E、F、G 这六点之间有一条白线连线,那么就会出现一个三边为白色的三角形.否则,这六个点只能用红、蓝两种颜色连接了.根据例 1 的证明可得,这六个点之间必有一个红色边或蓝色边的三角形
《染色中的抽屉原理》由会员mg****85分享,可在线阅读,更多相关《染色中的抽屉原理》请在金锄头文库上搜索。
高中数学配套课件:第1部分 第二章 2.2 2.2.1 用样本的频率分布估计总体分布
高中数学必修2红对勾答案1-1-2-2
高中数学全程复习方略第二章 圆锥曲线与方程 章末总结 阶段复习课(共57张ppt)
高三文科数学一轮复习数列5--5
高一数学对数函数课件
马克思主义政党是工人阶级的先锋队
青岛版数学六年级上册第八单元百分数的整理和复习1
阿拉伯糖操纵子
逻辑基本规律1
选修4《化学反应速率和化学平衡》 第3节 化学平衡(5) 有关化学平衡常数及转化率的计算
辅修用 辅助费用分配
软件无线电 第3章 多模式调制解调
跳槽员工与辞退员工管理技巧及典型案例解析(ppt 40)
费用组成(工管、辅修、专升本)
财政学公共支出课件
苏教版数学四年级上册《平行和相交(一)》课件
船舶推进第2章 螺旋桨几何特征
自考第3章4调和函数
自动控制课件 第4章
育新小学 魏秀珍
2023-07-10 7页
2023-11-21 9页
2023-04-23 79页
2022-09-24 2页
2023-04-21 17页
2023-06-27 6页
2023-10-14 6页
2023-07-08 6页
2023-03-03 5页
2023-07-04 20页