Maths Olympiad Prep

Library / /332 of 462

Combinatorics Difficulty 6.4 National Olympiad Prove it Ireland

2021 points are given, no three of them are collinear. Divide these points into 20 groups with different numbers of points in each group. Count the number of triangles with vertices in different groups. In order to get the maximum number of such triangles, how should you divide those point?

Solution

For any division of the 2021 points into 20 groups M1,M2,,M20M_1, M_2, \dots, M_{20} of different size we let nkn_k be the number of points in the group MkM_k and we suppose that n1<n2<n3<<n20n_1 < n_2 < n_3 < \dots < n_{20}. The number g=n20n119g = n_{20} - n_1 - 19 is then equal to the number of integers between n1n_1 and n20n_{20} which are not equal to any nkn_k.

The main observation is that when g2g \ge 2 it is possible to increase the number of triangles by moving one point to another group. To see this, let ni<njn_i < n_j be such that ni+1<nj1n_i + 1 < n_j - 1 and the two numbers ni+1n_i + 1 and nj1n_j - 1 are not among the nkn_k. Such i,ji, j always exist when g2g \ge 2, because we can pick two of the missing integers to be ni+1n_i + 1 and nj1n_j - 1.

When we move a point PP from MjM_j to the group MiM_i, we gain triangles with one vertex PP and another vertex in Mj{P}M_j \setminus \{P\}. If r=2021ninjr = 2021 - n_i - n_j is the number of point in the 18 unaffected groups, then the number of triangles gained is equal to r(nj1)r(n_j - 1). But we also lose all the triangles that had PP as one vertex and another vertex in MiM_i. The number of lost triangles is equal to rnirn_i. Hence, the net gain when we move PP from MjM_j to MiM_i is
r(nj1)rni=r(njni1)>0. r(n_j - 1) - rn_i = r(n_j - n_i - 1) > 0.
Because the number of triangles is bounded above by (20213)\binom{2021}{3}, we cannot increase the number of triangles indefinitely. Hence, starting with any division of the 2021 points into 20 groups of different size and moving points between groups in the way described above, we will reach a situation at which an increase of the number of triangles is not possible. In such a situation we must have g=0g = 0 or g=1g = 1. This means that the numbers n1,n2,,n20n_1, n_2, \dots, n_{20} are obtained by removing one number from a list of 21 consecutive numbers. If the smallest or largest number is removed from the list we have g=0g = 0, and g=1g = 1 otherwise.

Let n1n_1 be the smallest number of this list of 21 consecutive numbers and let n1+kn_1 + k be the missing number, where 1k201 \le k \le 20. We then have
2021=i=120ni=i=020(n1+i)(n1+k)=20n1+210k. 2021 = \sum_{i=1}^{20} n_i = \sum_{i=0}^{20} (n_1 + i) - (n_1 + k) = 20n_1 + 210 - k.
This gives 1811=20n1k1811 = 20n_1 - k and so k=9k = 9 and n1=91n_1 = 91. Therefore, g=1g = 1 and the numbers n1,n2,,n20n_1, n_2, \dots, n_{20} are the integers from 91 to 111, except 100. If these are the sizes of the groups, the maximum number of triangles is achieved. In any other case, the number of triangles is below the maximum.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.