Browse · MathNet
PrintRomanian Mathematical Olympiad
Romania counting and probability
Problem
In the plane are given points, such that no three of them are on the same line. The points are arranged in groups, any group containing at least points. Any two points in the same group are joined by a segment.
a) Determine which of the possible arrangements in such groups is the one giving the minimal numbers of triangles.
b) Prove that there exists an arrangement in such groups where each segment can be coloured with one of three given colours and no triangle has all edges of the same colour.
a) Determine which of the possible arrangements in such groups is the one giving the minimal numbers of triangles.
b) Prove that there exists an arrangement in such groups where each segment can be coloured with one of three given colours and no triangle has all edges of the same colour.
Solution
a) If the groups contain respectively points, the number of triangles is We claim this number is minimal when the minimum value being . Indeed, if there exists a group having points, there will exist another group having points. Moving a point from the first group into the second, the number of triangles decreases. This last statement follows from the inequality readily verified by direct computation.
b) Make each group of points each, subdivided into two subgroups of points each. Since the positions of the points are irrelevant, we may suppose all these subgroups of points make up convex pentagons. Colour their sides with colour , their diagonals with colour , and the segments joining points from different subgroups with colour . It is easy to see no monochromatic triangle appears.
b) Make each group of points each, subdivided into two subgroups of points each. Since the positions of the points are irrelevant, we may suppose all these subgroups of points make up convex pentagons. Colour their sides with colour , their diagonals with colour , and the segments joining points from different subgroups with colour . It is easy to see no monochromatic triangle appears.
Final answer
a) The minimal number of triangles is achieved when the ten groups are all of size ten, giving 10 × C(10, 3) = 1200 triangles. b) Such an arrangement exists: in each group of ten, split the points into two convex pentagons; color pentagon sides with one color, pentagon diagonals with a second color, and edges between the two pentagons with a third color, which avoids monochromatic triangles.
Techniques
Coloring schemes, extremal argumentsInduction / smoothing