MathDB

4

Part of 2019 China Second Round Olympiad

Problems(2)

Two element subsets of a graph

Source: 2019 China Second Round P4

9/8/2019
Let VV be a set of 20192019 points in space where any of the four points are not on the same plane, and EE be the set of edges connected between them. Find the smallest positive integer nn satisfying the following condition: if EE has at least nn elements, then there exists 908908 two-element subsets of EE such that [*]The two edges in each subset share a common vertice, [*]Any of the two subsets do not intersect.
combinatoricsgraph theory
Coloring problem in 2019 China Second Round(B)

Source: 2019 China Second Round(B) P4

9/8/2019
Each side of a convex 20192019-gon polygon is dyed with red, yellow and blue, and there are exactly 673673 sides of each kind of color. Prove that there exists at least one way to draw 20162016 diagonals to divide the convex 20192019-gon polygon into 20172017 triangles, such that any two of the 20162016 diagonals don't have intersection inside the 20192019-gon polygon,and for any triangle in all the 20172017 triangles, the colors of the three sides of the triangle are all the same, either totally different.
combinatoricsColoring