Всего в множестве $A$, состоящем из $n$ элементов, существует $2^n$
различных подмножеств, считая пустое множество и само множество $A$ (см.
статью Н. Я. Виленкина «Комбинаторика», «Квант» № 1, 1971).
Мы будем обозначать разные подмножества $A$ буквами $B$, $C$, $\ldots$,
пересечение множеств $B$ и $C$, т. е. множество, составленное из общих
элементов $B$ и $C$, принято обозначать так: $B\cap C$; дополнение
подмножества $B$ до всего множества $A$, т. е. множество, составленное из всех тех элементов $A$, которые не входят в $B$, обозначается так:
$\overline B$.
По условию выбрано $2^{n-1}$ подмножеств, т. е. половина всех возможных,
причём каждое из выбранных подмножеств, пересечение любых двух (и даже трёх)
из них не пусто. Следовательно, из каждой пары подмножеств $(B,\overline
B)$, дополняющих друг друга до $A$, выбрано в точности одно. Далее, если $B$
и $C$ выбраны, то $D=B\cap C$ тоже выбрано, поскольку $\overline D$ не может
быть выбрано (все три подмножества $\overline D$, $B$ и $C$ не могут иметь
общих элементов, ведь общие элементы $B$ и $C$ содержатся в $D$). Пользуясь
этим, очевидной индукцией можно доказать, что если $B_1$, $B_2$, $\ldots$, $B_k$
выбраны, то пересечение всех этих подмножеств $B_1\cap B_2\cap\ldots\cap
B_k$ тоже выбрано. Следовательно, пересечение всех
$2^{n-1}$ выбранных подмножеств тоже принадлежит к числу выбранных, значит,
оно не пусто.
Таким образом, мы доказали, что условию задачи удовлетворяет
только такая система подмножеств: фиксируется некоторый элемент $a$
множества $A$ и выбираются все подмножества,
содержащие этот элемент.
