Browse · MathNet
PrintChinese Mathematical Olympiad
China counting and probability
Problem
Find all integers such that we can color all the edges and the diagonals of a convex -polygon by given colors satisfying the following conditions; (1) Each of the edges or the diagonals is colored by only one color; (2) For any three distinct colors, there exists a triangle whose vertices are vertices of the -polygon and three edges are colored by these three colors.
Solution
Answer: Any odd number .
First of all, there are ways to choose three among colors, and ways to choose three vertices to form a triangle, so if the question's condition is fulfilled, all the triangles should have a different color combination (a 1-1 correspondence).
Note that any two segments of the same color cannot have a common endpoint.
As each color combination is used in exactly one triangle, for each color there should be exactly triangles which have one side in this color, and so there should be exactly lines of this color. Therefore, is odd.
Now we give a construction method for any odd .
As the orientation of the vertices does not really matter, we may assume that the polygon is a regular -polygon. First, color the sides of the polygon in the distinct colors. Then, for each side, color those diagonals that are parallel to this side into the same color.
In this way, for each color, there are diagonals colored in this color, and notice that each of these diagonals is of a different length.
Besides, for any two triangles with all vertices in, we shall prove that they should have different color combinations.
Suppose that, on the contrary, they have exactly the same three colors as their sides. Because of that all the sides with the same line are parallel, and the two triangles must be similar. For their vertices to be in the same circle, they must be the same, but this is a contradiction of . This completes the proof.
First of all, there are ways to choose three among colors, and ways to choose three vertices to form a triangle, so if the question's condition is fulfilled, all the triangles should have a different color combination (a 1-1 correspondence).
Note that any two segments of the same color cannot have a common endpoint.
As each color combination is used in exactly one triangle, for each color there should be exactly triangles which have one side in this color, and so there should be exactly lines of this color. Therefore, is odd.
Now we give a construction method for any odd .
As the orientation of the vertices does not really matter, we may assume that the polygon is a regular -polygon. First, color the sides of the polygon in the distinct colors. Then, for each side, color those diagonals that are parallel to this side into the same color.
In this way, for each color, there are diagonals colored in this color, and notice that each of these diagonals is of a different length.
Besides, for any two triangles with all vertices in, we shall prove that they should have different color combinations.
Suppose that, on the contrary, they have exactly the same three colors as their sides. Because of that all the sides with the same line are parallel, and the two triangles must be similar. For their vertices to be in the same circle, they must be the same, but this is a contradiction of . This completes the proof.
Final answer
All odd integers greater than 1
Techniques
Counting two waysColoring schemes, extremal argumentsMatchings, Marriage Lemma, Tutte's theorem