2014-06-08
Для каждого значения $n \in \mathbf{N}$ найти наибольшее число $k \in \mathbf{N}$, обладающее следующим свойством: в множестве, состоящем из $n$ элементов, можно выбрать $k$ различных подмножеств, любые два из которых имеют непустое пересечение.
Решение:
Зафиксируем элемент $a_{1}$ множества $X = \{ a_{1}, a_{2}, \cdots, a_{n} \}$ и будем рассматривать только подмножества, содержащие $a_{1}$. Число таких подмножеств равно числу подмножеств множества $\{ a_{2}; \cdots; a_{n} \}$, т.е. числу $2^{n-1}$. Следовательно, $k \geq 2^{n-1}$. С другой стороны, пусть выбрано более чем $2^{n-1}$ подмножеств множества X. Разобьем все возможные подмножества множества X на $2^{n-1}$ пар, объединяя в пару подмножество и его дополнение. Тогда по принципу Дирихле хотя бы два выбранных подмножества обязательно составляют пару и, следовательно, не пересекаются. Таким образом, $k = 2^{n-1}$.