= Solution
The <Balister-Bollobas inequality> says that if $r_i$ is the coordinate multiplicity in a multiset $\mathcal A$, and $L_j=\{i:r_i\geq j\}$, then $\sum_jH(X_{L_j})\leq\sum_{A\in\mathcal A}H(X_A)$. More generally, each union-intersection compression decreases the entropy sum, by <entropy submodularity>.
For an exact $k$-cover define $A^-=[\min A-1]$ and $A^+=[\max A-1]\setminus A$. Compressing the family of $A\cup A^-$ gives the nested family of all $A^-$ together with $k$ full sets. Rearranging the resulting bound gives the upper <Madiman-Tetali inequality>. Conversely, compressing the family of all $A^+$ together with $k$ full sets gives the nested family of $A\cup A^+$, yielding the lower bound. In conditional-entropy notation these are
$$
\boxed{\sum_{A\in\mathcal A}H(X_A\mid X_{A^+})\leq kH(X)\leq\sum_{A\in\mathcal A}H(X_A\mid X_{A^-}).}
$$
The coordinate multiplicities agree in each compression, because $\mathcal A$ is an exact $k$-cover. An equivalent proof expands the <chain rule for information entropy> contributions $h_i=H(X_i\mid X_{[i-1]})$ and uses <conditioning reduces entropy>. It also gives the upper inequality for arbitrary fractional covers and the lower inequality for fractional packings.
Back to article page
