五年级奥数 第十三讲 染色中的抽屉原则.doc

第十三讲染色中的抽屉原理
根据抽屉原理可以解决许多有趣的问题,,。
例1 平面上有A、B、C、D、E、F六个点,其中没有三点共线,每两点之间任意选用红线或蓝线连接,求证:不管怎样连接,至少存在一个三边同色的三角形。
分析与解答连彩线的方式很多,如果一一画图验证结论,,就不是难事了。
我们用虚线表示红色,,、D、E、,所以根据抽屉原理,、AD、AE三线同红色(如右图).如果B、D、
E这三点之间所连的三条线段中有一条是红色的,,,,不管如何连彩线,总可以找到一个三边同色的三角形。
如果我们把上面例题中的点换***,把红蓝两种颜色连线换***与人之间的关系,:证明在任意的6个人之间,或者有3个人互相认识,或者有3人互相都不认识。
我们只需把互相认识的两人用红线连接,互相不认识用蓝线连接,那么所要证明的结论就变成证明存在一个红色或蓝色的三角形了。
例2 从同一个小学毕业的同学之间的关系可以分为三个等级:关系密切、一般关系、,他们之间的关系是同一个等级的。
分析与解答把17人看成平面上17个点;用红、蓝、:证明用红、蓝、白三种颜色的线段连接平面上的17个点(没有三点共线),一定存在一个同色的三角形。
因为一个点要与其他16个点连线,只有三种颜色,所以根据抽屉原理,、C、D、E、F、、C、D、E、F、G这六点之间有一条白线连线,,这六个点只能用红、,这六个点之间必有一个红色边或蓝色边的三角形存在。
从例2的证明看出,它的论证方法与例1是相似的,只不过比例1多用了一次抽屉原理。
例3 用黑、白两种颜色把一个2×5(即2行5列):必有两列,它们的涂色方式完全相同。
分析与解答因为每列只有两格,而这两格的染法只有(右图)四种,将这4种染色方式当作4个抽屉,题中所有的方格共有5列,根据抽屉原理,至少有两列的染色方式完全相同。
例4 如果有一个3×n的方格阵列,每一列的三个方格都任意用红、黄、蓝、绿四色之三染成三种不同颜色,问n至少是多少时,才能保证至少有3列的染色方式完全相同。
分析与解答每一列都从4种颜色中选出三种分别染上这列中的三个小格,染色的方式共有4×3×2=24(种).若要保证至少有3列的染色方式完全相同,那么n至少是24×2+1=49。
下面研究另一类长方形阵列小格的染色的问题。
例5 对一块3行7列的长方形阵列中的小方格的每一格任意染成黑色或白色,求