2020 CHKMO #2

Let $S={1,2,\ldots,100}$. Consider a partition of $S$ into $S_1,S_2,\ldots,S_n$ for some $n$, i.e. $S_i$ are nonempty, pairwise disjoint and $\displaystyle S=\bigcup_{i=1}^n S_i$. Let $a_i$ be the average of elements of the set $S_i$. Define the score of this partition by

\[\dfrac{a_1+a_2+\ldots+a_n}{n}.\]

Among all $n$ and partitions of $S$, determine the minimum possible score.

The answer is $\boxed{10}$, achieved when $S_i = \{ i\}$ for $i < 10$ and $S_{10} = \{10, 11, \dots, 100 \}.$ The key insight is the following:

Claim: Fix $n$ for the moment. Then the minimum score is obtained when $S_i = \{ i \}$ for $i < n$ and $S_n = \{n, n+1, \dots, 100 \}$.

The idea is that we can perform swaps that decrease the score until we reach that partition. Suppose we have another distinct partition. Let $f(i)$ denote the size of the $S_j$ which contains $i$. Let $k$ be the minimal integer such that $f(k) > 1$. Then suppose $k$ belongs to a set of the form $\{ k \} \cup A $. Because $A \neq \{ k+1, \dots 100 \}$, there must exist another set $B$ among the $S_i$ such that every element of $B$ is at least $k$. Then we claim that isolating $\{k \}$ and combining $A$ and $B$ into a single set decreases the score. This is a simple computation. Denote the score after this swap by $S'$. Let $\Sigma{T}$ denote the sum of elements of an arbitrary set $T$. Then

$$n(S - S') = \frac{ k + \sum(A)}{|A| + 1} + \frac{\sum(B)}{|B|} - k - \frac{\sum (A) + \sum (B)}{|A| + |B|}$$

$$= \frac{\sum(A) |B| (|B|-1) + \sum(B) |A|(|A| + 1) - k |A| |B| (|A|+|B|)}{(|A|+1)|B|(|A|+|B|)}$$

By the minimality of $k$, we have $\sum(A) > k|A|$ and likewise $\sum(B) > k|B|. $ Thus

\[ n(S - S') > \frac{ k|A||B|(|B|-1 + |A| + 1|) - k|A||B|(|A|+|B|)}{(|A|+1)|B|(|A|+|B|)} > 0 . \]Hence we may perform swaps that decrease the score unless our partition is of the aforementioned form. This proves the claim.

Thus we are left with optimizing a function of $n$. For fixed $n$, the minimal partition has score

\[ \frac{1 + 2 + \dots + n-1 + \frac{100+n}{2}}{n} = \frac{n^2 + 100}{2n} = \frac{n}{2} + \frac{50}{n}. \]By AM-GM this is at most $10$, as desired. $\square$