17个科学家

来自计算思维百科
跳转至: 导航搜索
17个科学家1.jpg

有17个科学家,他们中的每一个都和其他的科学家通信,在他们的通信中仅仅讨论三个问题,每对科学家互相通信时,仅仅讨论一个问题。请你证明至少有三个科学家关于同一个题目互相通信。

解决方案-染色法

对于比较抽象的问题,我们可以用图来表达。我们用17个点表示17个科学家,科学家之间通信用“双向箭头”表示。根据题目意思,每一个科学家与其他16个科学家之间都有一条双向箭头。“箭头的颜色”表示两个科学家通信中讨论的问题,颜色不同表示讨论的问题不同,因此,箭头的颜色最多三种,我们用“红黄蓝”来标明。那么,这个问题就转化成:有一个图,具有17个结点,任意两个结点之间都有一条双向边,用3种颜色给边涂色,3种颜色都要用到,证明,图中存在一个环,这个环至少有3个结点且结点之间的边颜色相同。这是数学中的染色问题,通常我们用“抽屉原理”来解决它。

“抽屉原理”是组合数学一个非常重要的概念。用一个简单得例子来解释抽屉原理:有5个苹果,要放到四个抽屉里,那么至少有一个抽屉里面至少放两个苹果。

在17个点任选一个点,比如点A,向其他16个点作线段,用三种颜色对线段涂色,这里16条线段就相当于苹果,3种颜色就相当于抽屉,由抽屉原理可知至少有6条线段同色,假设是AB、AC、AD、AE、AF、AG均为红色。

如图:

17个科学家2.png

1. 若B、C、D、E、F、G这六个点中有两点连接为红线,设这两点为B、C,则三角形ABC为一个三边同为红色的三角环,即证:图中存在ABC环,有3个结点且结点之间的边颜色都为红色。

17个科学家3.png

ABC为三边红色的三角环

2. 若B、C、D、E、F、G这六个点中任两点没有红色,则BC、BD、BE、BF、BG这5条线段的颜色也只能是两种,这里五条线段是苹果,两种颜色是抽屉,由抽屉原理必有三条线段同色,设BC、BD、BE均为黄色,再研究三角形CDE三边的颜色,它只有两种情况,要么同为蓝色,则三角形CDE是一个三边同色的三角形;要么至少有一边为黄色,设这条边为CD,则三角形BCD是一个三边同为黄色的三角形,所以至少有三个科学家关于同一个问题进行互相通信。

17个科学家4.png

CDE为三边蓝色的三角形

17个科学家5.png

BCD为三边黄色的三角形

运用的计算思维

我们首先将具体的问题抽象成一个图问题,将问题转化成图的边染色问题。之后用“抽屉原理”解决,整个解题过程运用了抽象和转化的计算思维。

参考文献

http://www.kantiku.com/math3-2553134.htm