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 of different size we let be the number of points in the group and we suppose that . The number is then equal to the number of integers between and which are not equal to any .
The main observation is that when it is possible to increase the number of triangles by moving one point to another group. To see this, let be such that and the two numbers and are not among the . Such always exist when , because we can pick two of the missing integers to be and .
When we move a point from to the group , we gain triangles with one vertex and another vertex in . If is the number of point in the 18 unaffected groups, then the number of triangles gained is equal to . But we also lose all the triangles that had as one vertex and another vertex in . The number of lost triangles is equal to . Hence, the net gain when we move from to is
Because the number of triangles is bounded above by , 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 or . This means that the numbers 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 , and otherwise.
Let be the smallest number of this list of 21 consecutive numbers and let be the missing number, where . We then have
This gives and so and . Therefore, and the numbers 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.