2014-06-08
Множество X состоит из $n$ элементов. Для двух подмножеств $A_{1}, A_{2} \subset X$ сосчитано число элементов множества $A_{1} \bigcap A_{2}$. Доказать, что сумма всех полученных чисел равна $n \cdot 4^{n-1}$.
Решение:
Так как существует всего $2^{n}$ различных подмножеств множества X, то различных упорядоченных пар подмножеств существует $(2^{n})^{2} = 4^{n}$. Разобьем все эти пары на $4^{n-1}$ четверок, включая каждую пару $(A_{1}; A_{2})$ в одну четверку с парами $(\overline{A}_{1}; A_{2}), (A_{1}; \overline{A}_{2}), (\overline{A}_{1}; \overline{A}_{2})$ (здесь через А обозначено дополнение $X \backslash A$ к подмножеству $A \subset X$). В результате получим разбиение множества всех пар на четверки. Действительно, пара $(\overline{A}_{1}; A_{2})$, например, образует четверку $(\overline{A}_{1}; A_{2}), (\overline{\overline{A}}_{1}; A_{2}), (\overline{A}_{1}; \overline{A}_{2}), (\overline{\overline{A}_{1}}; \overline{A_{2}})$, которая совпадает с четверкой, образуемой парой $(A_{1}; A_{2})$, ибо $\overline{\overline{A}} = A$. Аналогично проверяется, что пары $(A_{1}; \overline{A}_{2}), (\overline{A}_{1}; \overline{A}_{2})$ образуют ту же четверку. Далее, поскольку каждый элемент множества X принадлежит либо подмножеству $A$, либо его дополнению $\overline{A}$, то он входит в точности в одно из множеств четверки $A_{1} \bigcap A_{2}, \overline{A}_{1} \bigcap A_{2}, A_{1} \bigcap \overline{A}_{2}, \overline{A}_{1} \bigcap \overline{A}_{2}$. Следовательно, суммарное количество элементов в любой четверке равно $n$. Так как всего четверок $4^{n-1}$, то сумма количеств элементов всех множеств вида $A_{1} \bigcap A_{2}$ равна $n \cdot 4^{n-1}$.