某个县下属的每两个区都恰好由汽车，火车，飞机三种交通方式中的一种直接联系。已知在全县中三种交通方式全有，但没有一个区三种方式全有，并且没有三个区中两两联系的方式完全相同。试问这个县至少有几个区？
I just have some rough idea, maybe I did not get the problem. |
4 is possible, 5 is not possible. |
We can draw a graph to represent the problem.
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: 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. 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 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |