Problem
COM-B2-M01-P018 Generalisation to \((t+1)\)-Subsets
#18
★★★★★ Level 5 of 5
Suppose \(m\) subsets of size \(k\) are chosen in an \(n\)-element set. Any two chosen subsets have at most \(t\) common elements. Prove that \(m\binom{k}{t+1}\le\binom{n}{t+1}\).
Count \((t+1)\)-element subsets lying inside the chosen sets.
Each chosen \(k\)-element set contains \(\binom{k}{t+1}\) subsets of size \(t+1\), giving \(m\binom{k}{t+1}\) occurrences. But the same \((t+1)\)-element subset cannot lie in two chosen sets; otherwise those two sets would have at least \(t+1\) common elements, which is forbidden. The ground set has \(\binom{n}{t+1}\) such subsets in total. The inequality follows.
This is a strong form of the previous problems and a good final template.