2014-06-08
Множество X разбито на попарно непересекающиеся подмножества $A_{1}, \cdots, A_{n}$, а также разбито на попарно непересекающиеся подмножества $B_{1}, \cdots, B_{n}$. Известно, что объединение $A_{i} \bigcup B_{j}$ любых непересекающихся подмножеств $A_{i}, B_{j}(1 \leq i \leq n, 1 \leq j \leq n$) содержит не менее $n$ элементов. Доказать, что число элементов множества X не меньше $n^{2}/2$. Может ли оно быть равным $n^{2}/2$?
Решение:
Пусть $k$ - число элементов в том из множеств $A_{1}, \cdots, A_{n}, B_{1}, \cdots, B_{n}$, в котором оно наименьшее. Для определенности считаем, что множество $A_{1}$ содержит $k$ элементов. Множества $B_{1}, \cdots, B_{n}$ между собой не пересекаются. Поэтому условие $A_{1} \bigcap B_{j} \neq \varnothing$ выполнено не более чем для $k$ из множеств $B_{1}, \cdots, B_{n}$. Пусть, например, это условие выполнено для множеств $B_{1}, \cdots, B_{m}$, где $m \leq k$. Число элементов в каждом из множеств $B_{1}, \cdots, B_{m}$ не меньше $k$ (согласно выбору числа $k$), следовательно, их объединение содержит не менее $mk$ элементов. Число же элементов в каждом из множеств $B_{m+}, \cdots, B_{n}$ не меньше $n – k$ (по условию, так как $A_{1} \bigcap B_{j} = \varnothing$ при $j = m + 1, \cdots, n$), а число таких множеств равно $n – m$. Поэтому всего в множестве $X = B_{1} \bigcup \cdots \bigcup B_{n}$ не менее чем $l = km + (n - k)(n - m)$ элементов. Если $k \geq n/2$, то каждое из множеств $A_{1}, \cdots, A_{n}$ содержит не менее $n/2$ элементов, а всего элементов не менее $n \cdot (n/2) = n^{2}/2$. Если же $k < n/2$ (напомним, что $m \leq k$), то
$l = n(n-k) – m(n-2k) \geq n(n-k) – k(n-2k) = 2 \left ( \frac{n}{2} \right )^{2} + 2 \left ( \frac{n}{2} - k \right )^{2} \geq \frac{n^{2}}{2}$.
Теперь приведем пример, когда множество $X$ содержит ровно $n^{2}/2$ элементов. Пусть $n$ - четное число и $X = A_{1} \bigcup \cdots \bigcup A_{n}$ - разбиение множества $X$ на $n$ подмножеств (попарно не пересекающихся), каждое из которых содержит ровно $n/2$ элементов. Положим $B_{1} = A_{1}, \cdots, B_{n} = A_{n}$, тогда вес условия задачи будут выполнены.