Gale-Ryser Theorem

We will prove that if $$$\sum \limits_{i=1}^k \min(a_i, k) \ge \sum \limits_{j=1}^k b_j$$$, then after decreasing $$$b_1$$$ maximal positions in $$$a$$$ the inequality would still hold. Case $$$k = 1$$$ is trivial.

Case $$$k \gt 1$$$. Suppose $$$a$$$ is also non-increasing, then after we do the first operation the inequality would look like this:

$$$\sum \limits_{i=1}^{b_1} \min(a_i - 1, k - 1) + \sum \limits_{i=b_1 + 1}^{n} \min(a_i, k - 1) \ge \sum \limits_{j=2}^k b_j$$$

$$$\sum \limits_{i=1}^{b_1} \min(a_i, k) - b_1 + \sum \limits_{i=b_1 + 1}^{n} \min(a_i, k - 1) \ge \sum \limits_{j=2}^k b_j$$$

$$$\sum \limits_{i=1}^{b_1} \min(a_i, k) + \sum \limits_{i=b_1 + 1}^{n} \min(a_i, k - 1) \ge \sum \limits_{j=1}^k b_j$$$

First case — $$$a_{b_1 + 1} \lt k$$$. Then the sum hasn't changed from the initial.

Second case — $$$a_{b_1 + 1} \ge k$$$. Then $$$a_{b_1} \ge k$$$, so $$$\sum \limits_{i=1}^{b_1} \min(k, a_i) = k \cdot b_1 \ge \sum \limits_{j=1}^k b_j$$$ since $$$b_1$$$ is the maximum value.

So after doing the first operation the condition doesn't fail and the induction transition is complete.

We can phrase this task in terms of max-flow problem. We have two parts $$$A$$$ and $$$B$$$. For $$$v \in A$$$ we draw an edge $$$S \rightarrow v$$$ with capacity $$$a_v$$$. For $$$u \in B$$$ we draw an edge $$$u \rightarrow T$$$ with capacity $$$b_u$$$. For $$$v \in A, u \in B$$$ we draw an edge $$$v \rightarrow u$$$ with capacity $$$1$$$.

The max-flow cannot be greater than $$$\sum b$$$, we want to find a sufficient condition for it to be equal to $$$\sum b$$$. By Ford-Fulkerson's theorem max-flow = min-cut. Consider an $$$S \backslash T$$$ cut. Split $$$A$$$ and $$$B$$$ into $$$AS, AT, BS, BT$$$. Then $$$cut = \sum \limits_{v \in AT} a_v + \sum \limits_{u \in BS} b_u + AS \cdot BT$$$. Let's fix the size of $$$BT$$$ and call it $$$k$$$. Among all cuts where $$$|BT| = k$$$ we want to find the minimal and compare it to $$$\sum b$$$. Since all terms that depend on $$$A$$$ don't depend on the choice of $$$BS$$$ and $$$BT$$$ if $$$|BT|$$$ is fixed, we can add$m — k$ minimum elements of $$$b$$$ to $$$BS$$$ and $$$k$$$ maximum elements in $$$BT$$$. Then for each $$$a_i$$$ we can either add it to $$$AT$$$ and add $$$a_i$$$ to mincut or add to $$$AS$$$ and add $$$k$$$ to mincut. So essentialy mincut is increased by $$$\min(k, a_i)$$$.

So, $$$mincut_k = \sum \limits_{v \in A} \min(k, a_i) + \sum \limits_{j=k+1}^{m} b_j$$$. Since we want to show that mincut is at least $$$\sum b$$$, $$$mincut_k \ge \sum b$$$ for $$$\forall k$$$.

$$$\sum \limits_{i=1}^n \min(k, a_i) + \sum \limits_{j=k+1}^{m} b_j \ge \sum \limits_{j=1}^m b_j$$$

$$$\sum \limits_{i=1}^n \min(k, a_i) + \sum \limits_{j=k+1}^{m} b_j \ge \sum \limits_{j=1}^m b_j$$$

$$$\sum \limits_{i=1}^n \min(k, a_i) \ge \sum \limits_{j=1}^k b_j$$$