"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. 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. 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. T