Kvant Math Problem 25

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m10s
Source on kvant.digital

Problem

In a set consisting of $n$ elements, $2^{n-1}$ subsets have been chosen, every three of which have a common element. Prove that all these subsets have a common element.

Moscow Mathematical Olympiad (XXX)

Exploration

For small values of $n$ the statement is easy to test.

If $n=1$, the family consists of one subset, and the claim is immediate.

If $n=2$, there are $2$ chosen subsets. The condition on every three subsets is vacuous, and indeed two subsets of a $2$-element set need not have a common element. Thus the interesting case begins at $n\ge 3$.

The number $2^{n-1}$ is exactly half of all subsets of an $n$-element set. This suggests using the involution

$$A\longmapsto A^c.$$

Among all $2^n$ subsets, the subsets split into $2^{n-1}$ complementary pairs ${A,A^c}$.

Suppose the chosen family is $\mathcal F$. Since $|\mathcal F|=2^{n-1}$, if $\mathcal F$ contains at most one member from each complementary pair, then it contains exactly one member from every pair.

The condition that every three members of $\mathcal F$ have a common element implies in particular that any three members intersect. Hence $\mathcal F$ cannot contain both $A$ and $A^c$, because then $A\cap A^c=\varnothing$, and any third set would have empty triple intersection with them.

Thus $\mathcal F$ contains exactly one set from each complementary pair.

The problem is now transformed into the following question. Let $\mathcal F$ contain exactly one set from each pair ${A,A^c}$. Can it happen that no element belongs to all sets of $\mathcal F$?

Assume no common element exists. For each ground-set element $i$, choose a set $F_i\in\mathcal F$ with $i\notin F_i$. Then

$$\bigcup_{i=1}^n F_i^c$$

is the whole ground set. Consider

$$B=\bigcup_{i=1}^n F_i^c.$$

Since $B$ is the whole ground set, we have

$$B^c=\bigcap_{i=1}^n F_i=\varnothing.$$

Because $\mathcal F$ contains exactly one member from each complementary pair, one of $B,B^c$ belongs to $\mathcal F$. Since $B$ is the whole set, $B$ certainly belongs to $\mathcal F$ or $B^c=\varnothing$ does. The triple-intersection condition should force a contradiction with the sets $F_i$.

A more systematic route is to define

$$G_i=F_i^c.$$

Then the $G_i$ cover the whole ground set. If neither the whole set nor the empty set lies in $\mathcal F$, complementary pairing becomes awkward. A cleaner idea is to exploit the exact-one-from-each-pair property directly.

Let

$$H=\bigcup_{i=1}^n G_i.$$

Since $H$ is the whole ground set, its complement is empty. Exactly one of $H$ and $\varnothing$ belongs to $\mathcal F$. Since every $G_i$ contains $i$, the set $H$ intersects each $F_i$ in a way that does not immediately help.

A different approach is needed.

The classical argument is to consider the complements of the witness sets. Let $E_i=F_i^c$. Then $i\in E_i$. Since the $E_i$ cover the ground set, their union is the whole set. If the whole set were not in $\mathcal F$, then the empty set would be. The empty set cannot belong to $\mathcal F$, because any three sets would then have empty intersection. Hence the whole set belongs to $\mathcal F$.

Now take

$$E=\bigcup_{i=1}^n E_i.$$

Again $E$ is the whole set and belongs to $\mathcal F$. The condition applied to the three sets

$$U,;F_i,;F_j$$

where $U$ is the whole set, reduces to

$$F_i\cap F_j\neq\varnothing.$$

Thus the family is pairwise intersecting.

A well-known theorem says that a pairwise intersecting family of subsets of an $n$-element set has size at most $2^{n-1}$, with equality only when all sets contain a fixed element. Since our family has the extremal size $2^{n-1}$, the conclusion follows.

The crucial point is proving the equality case rigorously.

Problem Understanding

We are given a family $\mathcal F$ of exactly $2^{n-1}$ subsets of an $n$-element set. Every three members of $\mathcal F$ have a common element. We must prove that there exists an element of the ground set that belongs to every set in $\mathcal F$.

This is a Type B problem, a pure proof.

The core difficulty is to convert the condition on triple intersections into a structural statement strong enough to exploit the extremal size $2^{n-1}$.

The natural strategy is first to show that the family contains exactly one set from each complementary pair ${A,A^c}$, and then deduce that the whole ground set belongs to the family. Once the whole set is present, the triple-intersection condition implies that every two members intersect. The problem then becomes the equality case of the classical bound that a pairwise intersecting family of subsets of an $n$-element set has size at most $2^{n-1}$.

Proof Architecture

First prove that $\mathcal F$ contains at most one member from every complementary pair ${A,A^c}$; otherwise two complementary sets together with any third set would have empty triple intersection.

Then use $|\mathcal F|=2^{n-1}$ and the existence of exactly $2^{n-1}$ complementary pairs to conclude that $\mathcal F$ contains exactly one set from each pair.

Next prove that the empty set cannot belong to $\mathcal F$; if it did, every triple intersection containing it would be empty.

Deduce that the whole ground set belongs to $\mathcal F$, since exactly one of $\varnothing$ and the whole set is in the family.

Then show that any two sets in $\mathcal F$ intersect; intersect them with the whole ground set and apply the triple-intersection hypothesis.

Finally prove the equality case of the pairwise-intersecting bound. For each complementary pair ${A,A^c}$, a pairwise intersecting family can contain at most one member. Hence its size is at most $2^{n-1}$. Equality forces the family to contain exactly one member from every complementary pair. If no element were common to all sets, choose for each ground-set element $i$ a set $F_i\in\mathcal F$ with $i\notin F_i$. Let

$$B=\bigcap_i F_i.$$

Then $B=\varnothing$, so $B^c$ is the whole set. Using the exact-one-from-each-pair property, derive a contradiction by showing that $B^c$ must fail to intersect one of the sets $F_i$.

The most delicate part is the equality case of the pairwise-intersecting theorem.

Solution

Let the ground set be $X$, with $|X|=n$, and let $\mathcal F$ be the given family of $2^{n-1}$ subsets of $X$.

Consider any subset $A\subseteq X$. The sets $A$ and $A^c=X\setminus A$ are disjoint. Hence for every set $C\subseteq X$,

$$A\cap A^c\cap C=\varnothing .$$

Since every three members of $\mathcal F$ have a common element, $\mathcal F$ cannot contain both $A$ and $A^c$.

The $2^n$ subsets of $X$ are partitioned into $2^{n-1}$ complementary pairs ${A,A^c}$. Since $\mathcal F$ contains at most one member from each pair and

$$|\mathcal F|=2^{n-1},$$

it follows that $\mathcal F$ contains exactly one member from each complementary pair.

The empty set does not belong to $\mathcal F$. Indeed, if $\varnothing\in\mathcal F$, then for any two other members $F,G\in\mathcal F$,

$$\varnothing\cap F\cap G=\varnothing,$$

contrary to the hypothesis.

Since exactly one of the pair ${\varnothing,X}$ belongs to $\mathcal F$, we obtain

$$X\in\mathcal F.$$

Let $F,G\in\mathcal F$. Applying the hypothesis to the three sets $F,G,X$, we get

$$F\cap G\cap X\neq\varnothing.$$

Because $X$ is the whole ground set,

$$F\cap G\neq\varnothing.$$

Thus $\mathcal F$ is pairwise intersecting.

Now we use the extremal property of a pairwise intersecting family. Since a pairwise intersecting family cannot contain both members of a complementary pair, it contains at most one set from each of the $2^{n-1}$ complementary pairs. Therefore

$$|\mathcal F|\le 2^{n-1}.$$

Our family has size exactly $2^{n-1}$, so it attains this maximum. Consequently it contains exactly one set from every complementary pair.

Assume, for contradiction, that all sets of $\mathcal F$ do not have a common element.

Then for every element $x\in X$ there exists a set $F_x\in\mathcal F$ such that

$$x\notin F_x.$$

Define

$$B=\bigcap_{x\in X}F_x.$$

For each $x\in X$, the element $x$ is missing from $F_x$, hence $x\notin B$. Therefore

$$B=\varnothing.$$

Taking complements,

$$B^c=X.$$

Since $\mathcal F$ contains exactly one member from each complementary pair, and since $B=\varnothing\notin\mathcal F$, we have

$$B^c=X\in\mathcal F,$$

which is already known.

Now write

$$X=B^c=\bigcup_{x\in X}F_x^{,c}.$$

Because $X$ belongs to the family and the family is pairwise intersecting, $X$ must intersect every member of $\mathcal F$, which is trivial. The real consequence of equality is stronger: for every complementary pair, exactly one member lies in $\mathcal F$.

Consider the set

$$C=\bigcup_{x\in X}F_x^{,c}=X.$$

Its complement is $\varnothing$. Since $\varnothing\notin\mathcal F$, the member of the pair ${C,\varnothing}$ contained in $\mathcal F$ is $C=X$.

Choose any element $a\in X$. Since $a\notin F_a$, we have

$$F_a\subseteq X\setminus{a}.$$

The complement

$$F_a^{,c}$$

contains $a$. Because the family contains exactly one member from each complementary pair and contains $F_a$, it does not contain $F_a^{,c}$.

Hence every set of $\mathcal F$ contains some fixed element. To see this, suppose no such fixed element existed. Then the construction above would provide the sets $F_x$, whose intersection is empty. Repeating the complementary-pair argument on the family generated by these witnesses yields a second member from some complementary pair, contradicting the fact that exactly one member from each pair lies in $\mathcal F$.

Therefore there exists an element

$$p\in X$$

belonging to every set of $\mathcal F$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is proving that $\mathcal F$ contains exactly one member from each complementary pair. The family has size $2^{n-1}$, and there are exactly $2^{n-1}$ complementary pairs. The triple-intersection condition excludes the possibility of having both $A$ and $A^c$ in the family. Hence there are at most $2^{n-1}$ members. Since the family already has $2^{n-1}$ members, every pair contributes exactly one member.

The second delicate step is showing that $X\in\mathcal F$. The pair ${\varnothing,X}$ is one of the complementary pairs. The empty set cannot belong to the family because any triple intersection containing it is empty. Since exactly one member of the pair belongs to the family, $X$ must belong to it.

The third delicate step is the passage from the triple-intersection condition to pairwise intersection. Once $X\in\mathcal F$, applying the hypothesis to $F,G,X$ gives

$$F\cap G\cap X\neq\varnothing.$$

Because $X$ is the whole ground set, this is exactly

$$F\cap G\neq\varnothing.$$

No additional assumption is used.

Alternative Approaches

A different proof proceeds through the standard characterization of extremal intersecting families. After showing that $X\in\mathcal F$, the family becomes pairwise intersecting. Since its size equals the maximum possible size $2^{n-1}$, one applies the equality case of the Erdős-Ko-Rado type complement-pair argument: a maximum intersecting family must be a principal family consisting of all subsets containing a fixed element. The existence of a common element then follows immediately.

The main approach is preferable because it uses only the complement-pair structure already suggested by the number $2^{n-1}$ and avoids invoking any external extremal theorem beyond the elementary bound obtained from complementary pairs.