liu的小天地 世间百态 水陆空环游

水陆空环游

水陆空环游 : 有17座城市,每两座城市间要么有陆路、要么有水路、要么有飞机航线连接着,而且每两座城市间只有一条线路连接,证明: 必存在三座城市,它们之间的交通路线是一样的。
对实际问题抽象化,我们得到17个城市可以改为17个点,每两点间有一条边相连,每条边染红、黄、蓝色中一色,现要证明存在一个同色三角形。
将17座城市看成17个点,陆路、水路和飞机航线分别用红、黄和蓝三种颜色的边表示,则问题转化为证明存在同色三角形。
取一个点B,则与该点相连的16条边中,由抽屉原理,必有一种颜色的边出现了6次,设这6条边为红色,由它们相连的6个点A1、 A2、 A3、 A4、 A5、 A6
若存在Ai Aj (1≤i<j≤6)为红色,则已有同色三角形B Ai Aj;
若不存在Ai Aj (1≤i<j≤6)为红色,则A1、 A2、 A3、 A4、 A5、 A6之间只有黄色和蓝色边。
而6个点用两种颜色的边连接,取一个点A1,则与其相连的5条线中必有一种颜色出现了3次,设其为黄色。
若存在Ai Aj (2≤i<j≤6)为黄色,则已有同色三角形A1Ai Aj;
若不存在Ai Aj (2≤i<j≤6)为黄色,则A1、 A2、 A3、 A4、 A5、 A6之间只有蓝色边相连,所以必存在同色三角形。
所以,必存在三座城市,它们之间的交通路线是一样的。

上一篇
下一篇
返回顶部