We can draw a graph to represent the problem.
Vertex: town. Edge: transportation. (Red: car,yellow: train, blue: plane)
We can not have a triangle of the same color, or a vertex that has three kinds of outgoing edges First, we have the following claim:www.ddhw.com For each vertex, at most two outgoing edges are of the same color. Proof:If the edges from vertex A to B, C and D are of the same color, say red, then since the edges between any two of B, C, D must be blue or yellow (or we get a red triangle) , but since we can not have a vertex that has three kinds of outgoing edges, for B, C and D, there is only one choice beside red for the color of outgoing edges, we must get a triangle BCD of the same color. www.ddhw.com Because of the claim, 6 or above is not OK. Now prove 5 is not OK. The following is what I think is the simplest. Because of the claim, if 5 is OK, then for each vertex, there are exactly two kinds of outgoing edges, say two red, two yellow. The we have a few cycles of edges with the edges in each cycle of the same color. There are at least three cycles, and each cycle has a length of at least 4, then we will have at least 12 edges. But we only have 10 www.ddhw.com
| 
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2005-2-26 21:05:29
收藏
分享
支持
反对
置顶卡
千斤顶
楼主
