Maths Olympiad Prep

Library / /45 of 45

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Romania

In the plane are given 100100 points, such that no three of them are on the same line. The points are arranged in 1010 groups, any group containing at least 33 points. Any two points in the same group are joined by a segment.

a) Determine which of the possible arrangements in 1010 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 a1,a2,,a10a_1, a_2, \dots, a_{10} points, the number of triangles is
N=(a13)+(a23)++(a103). N = \binom{a_1}{3} + \binom{a_2}{3} + \dots + \binom{a_{10}}{3}.
We claim this number is minimal when
a1=a2==a10=10, a_1 = a_2 = \dots = a_{10} = 10,
the minimum value being 10(103)10\binom{10}{3}. Indeed, if there exists a group having m11m \ge 11 points, there will exist another group having n9n \le 9 points. Moving a point from the first group into the second, the number of triangles decreases. This last statement follows from the inequality
(m3)+(n3)>(m13)+(n+13), \binom{m}{3} + \binom{n}{3} > \binom{m-1}{3} + \binom{n+1}{3},
readily verified by direct computation.

b) Make each group of 1010 points each, subdivided into two subgroups of 55 points each. Since the positions of the points are irrelevant, we may suppose all these subgroups of 55 points make up convex pentagons. Colour their sides with colour c1c_1, their diagonals with colour c2c_2, and the segments joining points from different subgroups with colour c3c_3. It is easy to see no monochromatic triangle appears.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.