In an n-element set X, 2n-1 subsets have been selected with the property that every three of them have a nonempty intersection. Prove that all 2n-1 of them have a nonempty intersection.
Solution 1
First, let's denote the given set of subsets U and its complement in 2X: V = 2X - U. We combine several useful facts in the following
Lemma
A, B, ... will denote generic subsets of X.
A ∈ U iff Ac ∈ V and vice versa, Ac being the complement of A.
If a ∈ X and {a} ∈ U, then a ∈ A, for every A ∈ U.
If A, B ∈ U then A∩B ∈ U.
Proof
The first claim follows from the observation that A∩Ac = Ø, while no two members of U may have an empty intersection. The second claim follows from the fact that the intersection of any set with {a} is either empty or {a}.
For the third statement, assume A, B ∈ U, while A∩B ∈ V. Then, by 1., (A∩B)c ∈ U, implying
A ∩ B ∩ (A∩B)c = (A∩B) ∩ (A∩B)c = Ø,
contrary to the premises of the problem.
According to 2., if there is a ∈ X such that {a} ∈ U, then a is common to all members of U such that their intersection includes {a} ≠ Ø. In this case the problem is solved.
Assume then that all 1-element subsets of X are in V. By 2., all subsets of X that lack just 1 element are in V. We shall prove that then all nonempty (proper) subsets of X are in U which is impossible, because, in particular, then there will be subsets and their complements contained in U.
Pairwise intersections of distinct subsets that lack a single element lack 2 elements. According to 3., all such subsets are in U.
If A = X - {a} and B = X - {b}, a ≠ b, then A∩B = X - {a, b}. Thus subsets that lack 2 elements also belong to U. Clearly we may continue in this manner until 1-element subsets come up. But these cannot belong simultaneously to U and to V!
Solution 2
This solution is by induction based on property 3. The intersection of any two subsets from U is nonempty and belongs to U. Order anyhow all members of U: A1, A2, ..., A2n-1. Now,
A1∩A2∩...∩Ak∩Ak+1 = (A1∩A2∩...∩Ak)∩Ak+1
Thus if we assume A1∩A2∩...∩Ak nonempty and belonging to U the same will hold for A1∩A2∩...∩Ak+1 and thus for the intersection of all members of U.
