In a plane $\mathcal{P}$, there are given $100$ points grouped into $10$ subsets. We draw all the lines between the points in a subset (each $3$ points are not collinear). Which repartition of the points in subsets gives the least total number of triangles? (France TST for IMO 1991)
I have tried to reformulate the problem in graph theory language:
Given a not connected graph $G = V \cup E$, with $|V| = 100$, and $\alpha_1, \alpha_2, \dots, \alpha_{10}$ natural numbers. The graph is composed of $10$ independent cliques $K_{\alpha_1}, K_{\alpha_2}, \dots, K_{\alpha_{10}}$. Find the set $(\alpha_1, \alpha_2, \dots, \alpha_{10})$ for which the numbers of $K_3$ structures in the graph is the least possible.
Firstly, I had proved the following lemma:
Lemma (1). In a $K_\ell$ structure, there are $\binom{\ell}{3}$ $K_3$ substructures.
The proof is quite obvious, using the definition of combinations (number of ways to chose a subset of $k$ elements). In our $K_\ell$, we have a set of $\ell$ vertices. Each $3$ of them form a $K_3$, because in the $K_\ell$ all lines are present. Therefore, the number of $K_3$-s is $\binom{\ell}{3}$. $\blacksquare$
Nextly, I have tried the following. (In attempt to formulate a base case for a simple induction)
Lemma (2). For two numbers $a$ and $b$, $a + b = n$, find $\min {\binom{n}{a} + \binom{n}{b}}$.
I didn't manage to prove this, despite I believe that the solution $a = b = \frac{n}{2}$ gives the minima. I have tried Mixing Variables Technique.
Finally, I think that the second lemma may be generalized for $n$ numbers by a sort of induction, to be applied, then, for $10$ in my graph. Thanks for any help with this problem!
We have $\binom{l}{3} = \frac{l(l-1)(l-2)}{6} = \frac{l^3 - 3l^2 + 2l}{6}$.
So the question simplfies to : Given $\sum_{i = 1}^{10} \alpha_i = 100$ and $\alpha_i \geq 1$ forall i, minimize $$\sum_{i = 1}^{10} (\alpha_i^3 - 3\alpha_i^2) $$
Ans: As $f(x) = x^3 - 3x^2$ is convex for $x \geq 1$, using Jensen's inequality:
$$ \sum_{i = 1}^{10} (\alpha_i^3 - 3\alpha_i^2) \ge 10 (10^3 - 3\cdot10^2) = 700\\ $$ Hence the minimum number of triangles is $\frac{700 + 200}{6} = 150$, when all $\alpha_i$ are equal.