2014-06-08
Дано 1978 множеств, каждое из которых имеет по 40 элементов. Известно, что любые два из этих множеств имеют ровно один общий элемент. Доказать, что существует элемент, принадлежащий всем 1978 множествам.
Решение:
Рассмотрим любое множество А из данных 1978 множеств. Оно пересекается с каждым из остальных 1977 множеств, поэтому существует элемент $a \in A$, принадлежащий не менее чем 50 из этих множеств. (Действительно, если каждый из 40 элементов множества А принадлежит не более чем 49 множествам, то всего имеется не более $40 \cdot 49 = 1960$ множеств, отличных от А, что неверно.) Итак, пусть элемент а принадлежит множествам $A, A_{1}, A_{2}, \cdots, A_{50}$. Докажем, что тогда он принадлежит и любому другому множеству В из данных 1978 множеств. Действительно, никакие два из множеств $A, A_{1}, A_{2}, \cdots, A_{50}$ не имеют общих элементов, отличных от $a$ (так как любые два множества пересекаются ровно по одному элементу). Пусть $a \not in B$. Тогда множество В имеет с каждым из множеств $A, A_{1}, A_{2}, \cdots, A_{50}$ общие элементы, которые отличны от $a$, а значит, различны. Поэтому множество В содержит не менее 51 элемента, что невозможно. Следовательно, элемент $a$ принадлежит всем множествам.