"Equal" Partitions

(Gabriel here.) Today I'll talk about an interesting distribution problem that I solved recently and my thought process when solving it. Here it is:

(India-Iran Friendly Competition Q5) Let $n \geq k$ be positive integers and let $a_1, \dots, a_n$ be a non-increasing list of positive real numbers. Prove that there exists $k$ sets $B_1, \dots, B_k$ which partition the set $\{1, 2, \dots, n\}$ such that $$\min_{1 \le j \le k} \left(\sum_{i \in B_j} a_i \right) \geq \min_{1 \le j \le k} \left(\frac{1}{2k+1-2j} \cdot \sum^n_{i=j} a_i\right).$$ Proposed by Navid Safaei

The inequality looks extremely convoluted, so let's dissect what is happening.

1. We have the numbers $a_1\ge a_2\ge \dots \ge a_n$, and we can freely partition them into $k$ different (possibly non-empty) groups.
2. The expression on the LHS is just the minimum sum of elements across the groups. Because there is no mention of $B_i$ in the RHS, we are simply trying to distribute the elements as evenly as possible.
3. The RHS comprises the following terms: $\frac{a_1+\dots+a_n}{2k-1}$, $\frac{a_2+\dots+a_n}{2k-3}$, $\dots ,\frac{a_k+\dots+a_n}{1}$. The way we should treat the "$\min$" is to think of it as giving us a choice: we only need our partition to beat one of these terms.

---

Now that we have a better idea of what we want, we should try proving some small cases.

Suppose $k=1$, so there is no partition at all. Then, we want to show that $$a_1+a_2+\dots+a_n\ge \frac{a_1+a_2+\dots+a_n}{1},$$which is obvious. At this point, we should probably define $a_1+\dots+a_n=S$.

---

We now try $k=2$.

We want the minimum sum in our partition to beat either $\frac{S}{3}$ or $\frac{a_2+\dots+a_n}{1}$. The latter expression is pretty suggestive. The only way we can beat that is if our partition is $\{a_1\}$ and $\{a_2,\dots,a_n\}$, i.e. if $a_1\ge a_2+\dots+a_n$.

What if $a_1 < a_2+\dots+a_n$ (or equivalently, $a_1 < \frac{S}{2}$)? Remember that we want the groups to be as close as possible. Let's take the smallest $i$ such that $$a_1+a_2+\dots+a_i>a_{i+1}+\dots+a_n.$$This means that $a_1+\dots+a_{i-1}\le \frac{S}{2}$ and $a_1+\dots+a_i>\frac{S}{2}$. We want one of these partitions to work.

What happens if they don't? Then $a_1+\dots+a_{i-1} < \frac{S}{3}$ and $a_{i+1}+\dots+a_n < \frac{S}{3}$, so $a_i>\frac{S}{3}$. However, if $a_i>\frac{S}{3}$, then so is $a_1$, and the partition $\{a_1\}|\{a_2,\dots,a_n\}$ will beat $\frac{S}{3}$, so we are done.

Here I found a pictorial visualisation much more effective:

This case has given us some structural insight:

1. The $\frac{a_2+\dots+a_n}{1}$ is used to catch cases where $a_1$ is disproportionately big.
2. If all elements are "small", then we can beat $\frac{S}{2k-1}$. In this specific case, if all $a_i\le \frac{S}{3}$, then we can beat $\frac{S}{3}$.

---

We now move on to $k=3$.

We now need to beat one of the terms $\frac{S}{5}$, $\frac{S-a_1}{3}$, or $\frac{S-a_1-a_2}{1}$.

As before, we want to eliminate cases where $a_1$ is disproportionately big. In the $k=2$ case, this happens when $a_1\ge \frac{S}{2}$. What happens when $a_1\ge \frac{S}{3}$ here? The key realisation is that this means $a_1$ is greater than the average size of the three groups. This means that even if we group $a_1$ by itself, it won't have the minimum sum.

In other words, it is optimal to put $a_1$ in its own group. After we do that, it suffices to show we can put $a_2,\dots,a_n$ into two groups so that they beat $\frac{S}{5}$, $\frac{a_2+\dots+a_n}{3}$ or $\frac{a_3+\dots+a_n}{1}$. Does that look familiar? That is exactly the question we solved in the previous case! This hints at an induction proof for the general case.

Next, let's address the other situation, where all $a_i$ are less than $\frac{S}{3}$. As before, we want to use a greedy argument to produce the three groups that beat $\frac{S}{5}$.

Obviously, elements between $\frac{S}{5}$ and $\frac{S}{3}$ should stay in their own group. For everything else that is less than $\frac{S}{5}$, we can partition them into groups of between $\frac{S}{5}$ and $\frac{2S}{5}$, with possibly some leftovers. Since each complete group is $\le \frac{2S}{5}$, we will have at least $\frac{S}{5}$ leftover, and we are done!

---

Now, we are ready to tackle the original problem.

If $a_1\ge \frac{S}{k}$, then we can put it in its own group. We now have to partition $a_2,\dots,a_n$ into $k-1$ groups to beat one of $\frac{a_2+\dots+a_n}{2k-3},\dots,\frac{a_k+\dots+a_n}{1}$, which is exactly the case $(n-1,k-1)$.

Else, all elements are $ < \frac{S}{k}$. We show we can beat $\frac{S}{2k-1}$. First, put all elements between $\frac{S}{2k-1}$ and $\frac{S}{k}$ by themselves. For the rest, arbitrarily group them together and stop once the group size is $\ge \frac{S}{2k-1}$.

Any complete group have size $\le \frac{2S}{2k-1}$, and so there are at least $k-1$ of them. Finally, the last group will have size $\ge \frac{S}{2k-1}$, so we are done. (This may remind you of questions such as IMOSL 2013 C1.)

---

I hope this write-up is a good illustration of how to use small cases to gain deeper insights into the structure of the question and to eventually lead to a solution.