Problem
COM-B2-M08-P009 Robust Choice
#9
★★★☆☆ Level 3 of 5
For a family of sets \(A_1,\ldots,A_n\), the union of any \(k\) of them contains at least \(k+1\) elements. Prove that after deleting any one element, an SDR can still be chosen.
After deleting one element, the union of any \(k\) sets loses at most one element.
Delete an arbitrary element \(x\). Take any \(k\) sets. Before deletion, their union had size at least \(k+1\). After deleting \(x\), the union size decreases by at most \(1\), so at least \(k\) elements remain.
Hall's condition holds for the new family, so an SDR exists.
Shows slack in Hall's condition.