# Subsets and Intersections

Here is a problem (Kvant, n 5, 1970, M25):

In an n-element set X, 2^{n-1} subsets have been selected with the property that every three of them have a nonempty intersection. Prove that all 2^{n-1} of them have a nonempty intersection.

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

In an n-element set X, 2^{n-1} subsets have been selected with the property that every three of them have a nonempty intersection. Prove that all 2^{n-1} of them have a nonempty intersection.

### Solution 1

First, let's denote the given set of subsets U and its complement in 2^{X}: ^{X} - U.

### Lemma

A, B, ... will denote generic subsets of X.

A ∈ U iff A

^{c}∈ V and vice versa, A^{c}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∩A^{c} = Ø, 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

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: A_{1}, A_{2}, ..., A_{2n-1}. Now,

A_{1}∩A_{2}∩...∩A_{k}∩A_{k+1} = (A_{1}∩A_{2}∩...∩A_{k})∩A_{k+1}

Thus if we assume A_{1}∩A_{2}∩...∩A_{k} nonempty and belonging to U the same will hold for A_{1}∩A_{2}∩...∩A_{k+1} and thus for the intersection of all members of U.

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

61191547 |