XXI OM - II - Problem 6

If $ A $ is a subset of set $ X $, then we define $ A^1 = A $, $ A^{-1} = X - A $. Subsets $ A_1, A_2, \ldots, A_k $ are called mutually independent if the product $ A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \ldots A_k^{\varepsilon_k} $ is non-empty for every system of numbers $ \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k $, such that $ |\varepsilon_i| = 1 $ for $ i = 1, 2, \ldots, k $.
What is the maximum number of mutually independent subsets of a $ 2^n $-element set?
Since the number of all $n$-term sequences with values $-1$ and $1$ is $2^n$ (see preparatory problem D of series III), we can assume that the elements of the $2^n$-element set $X$ under consideration are such sequences.
Let $A_i$ for $i = 1, 2, \ldots, n$ denote the set of all sequences in $X$ whose $i$-th term is $1$. We will show that the subsets $A_1, A_2, \ldots, A_n$ are mutually independent.
A sequence $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$, where $|\varepsilon_j| = 1$, belongs to each of the sets $A_i^{\varepsilon_i}$ for $i = 1, 2, \ldots, n$. If $\varepsilon_i = 1$, then the considered sequence has its $i$-th term equal to $1$, and thus belongs to $A_i^{\varepsilon_i} = A_i^1$; if, on the other hand, $\varepsilon_i = -1$, then the considered sequence has its $i$-th term equal to $-1$, and thus belongs to $X - A_i = A_i^{-1}$. Therefore, the set $A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \cap \ldots \cap A_n^{\varepsilon_n}$ contains the sequence $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$, and thus is non-empty.
We will now show that if $r > n$ and $B_1, B_2, \ldots, B_r$ are some subsets of the set $X$, then they are not mutually independent. If the sequences $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_r)$ and $(\varepsilon$ with values $-1$ and $1$ are different, then the sets

are disjoint. Specifically, if, for example, $\varepsilon_i = 1$, then we have $B \subset B_i^{\varepsilon_i} = B_i$ and $B \subset X - B_i$, and the sets $B_i$ and $X - B_i$ are obviously disjoint.
Thus, if the sets $B_1, B_2, \ldots, B_r$ were mutually independent, then all sets of the form $B_1^{\varepsilon_1} \cap B_2^{\varepsilon_2} \cap \ldots \cap B_r^{\varepsilon_r}$ would be non-empty and pairwise disjoint. There are $2^r > 2^n$ such sets. This is impossible, since the set $X$ contains only $2^n$ elements.
We have thus proved that $n$ is the maximum number of mutually independent subsets of a $2^n$-element set.