Разделы 
Дополнительно
Задача по математике - 1891
2019-01-21 
Часть подмножеств некоторого конечного множества выделена. Каждое выделенное подмножество состоит в точности из $2k$ элементов ($k$ - фиксированное натуральное число). Известно, что в каждом подмножестве, состоящем не более чем из $(k + 1)^2$ элементов, либо не содержится ни одного выделенного подмножества, либо все в нем содержащиеся выделенные подмножества имеют общий элемент. Докажите, что все выделенные подмножества имеют общий элемент.
Решение:
Предположим противное. Тогда найдется такое $n (n > 1)$, что любой набор из $n - 1$ выделенного подмножества имеет общий элемент и существует $n$ выделенных подмножеств $A_1, A_2, \cdots A_n$, не имеющих общего элемента. Исключим из набора $A_1, A_2, \cdots, A_n$ множество $A_i$. Оставшиеся имеют общий элемент, который мы обозначим через $x_i$. Заметим, что $x_i \neq x_j$ при $i \neq j$. Каждое из множеств $A_i$ содержит все элементы множества ${x_1, x_2, \cdots, x_n}$, кроме $x_i$, поэтому, если из множеств $A_i$ исключить элементы множества ${x_1, x_2, \cdots, x_n}$, то в каждом из них останется $2k - n +1$ элемент (в частности, $n \leq 2k +1$). Следовательно, объединение множеств $A_1, A_2,\cdots, A_n$ состоит не более чем из $n + n(2k - n + 1) = n(2k + 2 - n)$ элементов. Максимальное значение выражения $n(2k + 2 - n)$ равно $(k +1)^2$. Но тогда, по условию задачи, все $A_i$ должны иметь общий элемент. Противоречие.
Часть подмножеств некоторого конечного множества выделена. Каждое выделенное подмножество состоит в точности из $2k$ элементов ($k$ - фиксированное натуральное число). Известно, что в каждом подмножестве, состоящем не более чем из $(k + 1)^2$ элементов, либо не содержится ни одного выделенного подмножества, либо все в нем содержащиеся выделенные подмножества имеют общий элемент. Докажите, что все выделенные подмножества имеют общий элемент.
Решение:
Предположим противное. Тогда найдется такое $n (n > 1)$, что любой набор из $n - 1$ выделенного подмножества имеет общий элемент и существует $n$ выделенных подмножеств $A_1, A_2, \cdots A_n$, не имеющих общего элемента. Исключим из набора $A_1, A_2, \cdots, A_n$ множество $A_i$. Оставшиеся имеют общий элемент, который мы обозначим через $x_i$. Заметим, что $x_i \neq x_j$ при $i \neq j$. Каждое из множеств $A_i$ содержит все элементы множества ${x_1, x_2, \cdots, x_n}$, кроме $x_i$, поэтому, если из множеств $A_i$ исключить элементы множества ${x_1, x_2, \cdots, x_n}$, то в каждом из них останется $2k - n +1$ элемент (в частности, $n \leq 2k +1$). Следовательно, объединение множеств $A_1, A_2,\cdots, A_n$ состоит не более чем из $n + n(2k - n + 1) = n(2k + 2 - n)$ элементов. Максимальное значение выражения $n(2k + 2 - n)$ равно $(k +1)^2$. Но тогда, по условию задачи, все $A_i$ должны иметь общий элемент. Противоречие.
