Question

Множество А содержит 101 элемент. Докажите, что количество его подмножеств, которые содержат парное количество элементов, равно количеству подмножеств, которые содержат непарное количество элементов.

Answer 1

Сопоставим каждому подмножеству B, состоящему из четного числа элементов, подмножество C, полученное выкидыванием из A элементов, принадлежащих B. Поскольку в A нечетное число элементов, а в B четное число элементов, в С будет нечетное число элементов. В результате все подмножества разобьются на подобные пары подмножеств. Поэтому подмножеств, состоящих из четного числа элементов столько же, сколько подмножеств, состоящих из нечетного числа элементов.

Для тех, кому мое рассуждение показалось сложным, рассмотрю пример с меньшим числом элементов. Пусть, скажем, в A 5 элементов: A={a, b, c, d, e}. Подмножеству {a, b} соответствует подмножество {c, d, e}, подмножеству {a, c} соответствует подмножество {b, d, e}, подмножеству {a, b, c, d} соответствует подмножество {e}, и так далее. Пустому подмножеству (в нем ноль элементов) соответствует само множество A.

Разобьем все подмножества на пары (B,C), где B пробегает подмножества, состоящие из четного числа элементов, а C -- это подмножество, состоящее из тех элементов, которые не попали в B. Поскольку в A нечетное число элементов, в C будет нечетное число элементов.

Answer 2

Для доказательства данного утверждения воспользуемся комбинаторным подходом.

Пусть у нас есть множество А с 101 элементом. Тогда каждый элемент может присутствовать или отсутствовать в подмножестве. Таким образом, для каждого элемента у нас есть две возможности: он может присутствовать или быть отсутствовать в подмножестве.

Теперь рассмотрим, сколько всего существует подмножеств для множества А. Для каждого элемента мы можем сделать два выбора: включить его в подмножество или исключить из него. Так как элементов в множестве А 101, то всего возможных подмножеств будет 2^101.

Теперь давайте рассмотрим, сколько существует подмножеств с парным количеством элементов. Это возможно только если мы выберем четное количество элементов из множества А. Пусть k - количество элементов, которые мы выберем в подмножестве. k может быть равно 0, 2, 4, ..., 100. Для каждого четного k количество способов выбрать k элементов из 101 элемента равно:

C(101, k) = 101! / (k! * (101 - k)!),

где C(n, k) - число сочетаний из n по k (число способов выбрать k элементов из n).

Теперь мы хотим найти сумму всех C(101, k) для всех четных k. Известно комбинаторное равенство:

C(n, 0) + C(n, 1) + C(n, 2) + ... + C(n, n) = 2^n.

Подставим n = 101:

C(101, 0) + C(101, 1) + C(101, 2) + ... + C(101, 100) = 2^101.

Таким образом, количество подмножеств с четным количеством элементов равно 2^101.

Аналогично, количество подмножеств с непарным количеством элементов также равно 2^101, так как для каждого четного k существует соответствующее непарное k (например, для k = 2, есть k = 99; для k = 4, есть k = 97, и т.д.).

Таким образом, количество подмножеств, которые содержат парное количество элементов, равно количеству подмножеств, которые содержат непарное количество элементов, что и требовалось доказать.