2014-06-08
Пусть в конечном множестве X выбрано 50 подмножеств $A_{1}, \cdots, A_{50}$, каждое из которых содержит больше половины элементов множества X. Доказать, что можно найти подмножество $B \subset X$, содержащее не более 5 элементов и имеющее хотя бы один элемент, общий с каждым из множеств $A_{1}, \cdots, A_{50}$.
Решение:
Пусть количество элементов в множестве X равно $n$. Каждое из выбранных подмножеств $A_{1}, \cdots, A_{50}$ содержит более чем $n/2$ элементов, а значит, сумма количеств элементов всех этих множеств превышает $50 \cdot (n/2) = 25n$. По принципу Дирихле существует элемент множества X, принадлежащий не менее чем 26 выбранным подмножествам. Аналогично доказывается, что при любом значении $k < 50$ среди множеств $A_{i_{1}}, \cdots, A_{i_{k}}$ можно выбрать не менее $[k/2] + 1$ множеств, содержащих общий элемент. Возьмем элемент множества Х, который принадлежит не менее чем 26 множествам (этот элемент будет одним из пяти элементов множества В). Выбросим из рассмотрения какие-либо 26 множеств из числа тех, которым он принадлежит. Тогда найдется элемент, принадлежащий по крайней мере 13 из 24 оставшихся множеств. Выбросим из рассмотрения и эти 13 множеств. Тогда для оставшихся 11 множеств найдется элемент, принадлежащий по крайней мере шести из этих множеств. Для остальных пяти множеств существует элемент, принадлежащий по крайней мере трем из них. И, наконец, существует элемент, принадлежащий последним двум множествам. Таким образом, найдено не более пяти элементов множества X (возможно, менее пяти, так как некоторые из выбранных элементов могут совпадать), которые составляют множество В. При этом любое из множеств $A_{1}, \cdots, A_{50}$ содержит хотя бы один из этих элементов.