= Solution
Use the <chain lower bound for a submodular set function>. Order $T=\{x_1,\ldots,x_n\}$, set $P_j=\{x_1,\ldots,x_j\}$ with $P_0=\varnothing$, and put $a_j=f(P_j)-f(P_{j-1})$. For each $U\subseteq T$, reveal its elements in this same order. Since $U\cap P_{j-1}\subseteq P_{j-1}$, <diminishing returns> and the <normalised set function> property give
$$
f(U)=\sum_{j:x_j\in U}\Delta_{x_j}f(U\cap P_{j-1})
\geq\sum_{j:x_j\in U}a_j.
$$
Apply this to each $T_i$ and interchange the finite sums. Every element occurs exactly $k$ times, so
$$
\boxed{\sum_{i=1}^t f(T_i)\geq\sum_{j=1}^n k a_j=k\bigl(f(T)-f(\varnothing)\bigr)=k f(T).}
$$
This is the <exact-cover inequality for submodular set functions>. Some $a_j$ can be negative: exact multiplicity, rather than merely at least $k$ occurrences, is what makes the argument valid without monotonicity. In fact the <nonnegative function> hypothesis is unnecessary here. If $T=\varnothing$, every $T_i$ is empty and both sides vanish.
Back to article page
