Problem
COM-B1-M04-P024 Seventeen Triples
#24
★★★★★ Level 5 of 5
From a \(10\)-element set, \(17\) three-element subsets are chosen. Prove that two chosen subsets have at least two common elements.
Prove the contrapositive: if any two triples share at most one element, then element-pairs do not repeat.
Assume any two chosen triples share at most one element. Then no pair of elements can occur in two different triples; otherwise those two triples would share that pair, i.e. two common elements. Each triple contains \(3\) pairs, so \(17\) triples would contain \(51\) distinct element-pairs. But a \(10\)-element set has only \(10\cdot9/2=45\) pairs. Contradiction. Hence two triples share at least two elements.
Strong olympiad problem bounding by pairs.