Номер 3.18, страница 23 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 1. Множества и операции над ними. Параграф 3. Формула включения-исключения. Взаимно однозначное соответствие - номер 3.18, страница 23.

Условие.

3.18. Множество $A$ содержит 100 элементов. Докажите, что количество его подмножеств, содержащих чётное количество элементов, равно количеству подмножеств, содержащих нечётное количество элементов.

Решение.

Пусть множество $A$ содержит $n$ элементов, в данном случае $n=100$. Количество подмножеств множества $A$, содержащих ровно $k$ элементов, равно биномиальному коэффициенту $C_n^k = \binom{n}{k}$.

Количество подмножеств с чётным числом элементов, обозначим $N_{чёт}$. Это сумма количеств подмножеств с 0, 2, 4, ... элементами:$N_{чёт} = \binom{100}{0} + \binom{100}{2} + \binom{100}{4} + \dots + \binom{100}{100}$

Количество подмножеств с нечётным числом элементов, обозначим $N_{нечёт}$. Это сумма количеств подмножеств с 1, 3, 5, ... элементами:$N_{нечёт} = \binom{100}{1} + \binom{100}{3} + \binom{100}{5} + \dots + \binom{100}{99}$

Необходимо доказать, что $N_{чёт} = N_{нечёт}$. Приведём два способа доказательства.

Способ 1: С использованием бинома Ньютона

Рассмотрим разложение бинома Ньютона для $(1+x)^n$:$(1+x)^n = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \binom{n}{3}x^3 + \dots + \binom{n}{n}x^n$

Подставим в эту формулу $n=100$.

1. При $x=1$ получаем:$(1+1)^{100} = 2^{100} = \binom{100}{0} + \binom{100}{1} + \binom{100}{2} + \dots + \binom{100}{100}$Сумма справа представляет собой общее количество всех подмножеств множества $A$, что равно $N_{чёт} + N_{нечёт}$. Таким образом, $N_{чёт} + N_{нечёт} = 2^{100}$.

2. При $x=-1$ получаем:$(1-1)^{100} = 0^{100} = 0 = \binom{100}{0} - \binom{100}{1} + \binom{100}{2} - \binom{100}{3} + \dots + \binom{100}{100}$Сгруппируем слагаемые с положительными и отрицательными знаками:$0 = (\binom{100}{0} + \binom{100}{2} + \dots + \binom{100}{100}) - (\binom{100}{1} + \binom{100}{3} + \dots + \binom{100}{99})$Это выражение можно записать как $0 = N_{чёт} - N_{нечёт}$.

Из последнего равенства следует, что $N_{чёт} = N_{нечёт}$. Что и требовалось доказать.

Способ 2: Комбинаторное доказательство (построение биекции)

Пусть $A$ — это множество из 100 элементов. Выберем и зафиксируем один любой элемент из этого множества, назовём его $a$.

Теперь разделим все подмножества множества $A$ на два типа: те, которые содержат элемент $a$, и те, которые его не содержат.

Построим соответствие (отображение) $f$ между подмножествами $A$. Для любого подмножества $S \subseteq A$ определим $f(S)$ следующим образом:

• Если элемент $a$ принадлежит $S$ (т.е. $a \in S$), то $f(S) = S \setminus \{a\}$ (удаляем элемент $a$ из $S$).
• Если элемент $a$ не принадлежит $S$ (т.е. $a \notin S$), то $f(S) = S \cup \{a\}$ (добавляем элемент $a$ в $S$).

Рассмотрим, как это отображение меняет чётность количества элементов в подмножестве:

• Если в подмножестве $S$ было чётное число элементов, то после добавления или удаления одного элемента $a$ в подмножестве $f(S)$ станет нечётное число элементов.
• Если в подмножестве $S$ было нечётное число элементов, то после добавления или удаления одного элемента $a$ в подмножестве $f(S)$ станет чётное число элементов.

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

Это отображение является взаимно-однозначным (биекцией), так как если применить его дважды, мы вернёмся к исходному множеству: $f(f(S)) = S$. Это означает, что для каждого подмножества с чётным числом элементов есть ровно одно соответствующее ему подмножество с нечётным числом элементов.

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

Оба способа доказывают, что для множества из 100 элементов (и, в общем, для любого непустого конечного множества) количество подмножеств с чётным числом элементов равно количеству подмножеств с нечётным числом элементов.

Ответ: Утверждение доказано. Из $N_{чёт} + N_{нечёт} = 2^{100}$ и $N_{чёт} = N_{нечёт}$ следует, что количество подмножеств с чётным числом элементов равно $2^{100} / 2 = 2^{99}$, и количество подмножеств с нечётным числом элементов также равно $2^{99}$.