Problem
COM-B1-M03-P024 Seven Subsets of a Four-Element Set
#24
★★★★★ Level 5 of 5
Prove that among any \(7\) subsets of \(\{1,2,3,4\}\), there are two such that one contains the other.
Split all \(16\) subsets into \(6\) inclusion chains.
It is enough to split all subsets into \(6\) chains, because then \(7\) chosen subsets hit one chain twice by the pigeonhole principle. For example, take the chains \(\varnothing\subset\{1\}\subset\{1,2\}\subset\{1,2,3\}\subset\{1,2,3,4\}\); \(\{2\}\subset\{2,3\}\subset\{2,3,4\}\); \(\{3\}\subset\{1,3\}\subset\{1,3,4\}\); \(\{4\}\subset\{1,4\}\subset\{1,2,4\}\); and the singleton chains \(\{2,4\}\), \(\{3,4\}\). Any two sets in one chain are comparable by inclusion.
Challenge preview of antichains and pigeonhole.