2001-gre-vs-practice.pdf/Q41

Ссылки сюда (1) →

Вопрос: Q41-e5724f

Пусть A — конечное множество мощности n.

Чему равно количество подмножеств нечетной мощности (т.е. число количества элементов множества S нечетное)?

Ответы

• Правильный ответ:
• определенной формулы нет

Объяснение

Исходники — вопрос 41 на 34 странице книги «2001-gre-vs-practice.pdf»

Количество подмножеств, какого-либо конечного множества равно , где n мощность множества.

Докажем данную формулу.

Упорядочим каким — либо образом все элементы множества A.

Сопоставим последовательность нулей и единиц каждому подмножеству следующим образом: если j-ый элемент множества содержится в подмножестве , то в последовательности из нулей и единиц будет стоять 1, в противном случае 0. Таким образом, получено взаимно однозначное соответствие между битовыми последовательностями и подмножествами. Битовых последовательностей .

Докажем, что четных и нечетных множеств одинаковое количество.

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

StasFomin 22:36, 27 декабря 2024 (UTC): Гм. Так же из четных будут получаться тоже четные. A = {1, 2}, S = {} → f(S) → {1, 2}…

Пусть нечетное. Построим разбиение для .

Выберем произвольный элемент . Тогда подмножеств содержащих столько же сколько и не содержащих: (вспоминаем битовую последовательность описанную выше). Тогда можно по тому же правилу как и с четным описать биекцию между подмножествами, то есть из содержащих в несодержащие, и наоборот. Таким образом вне зависимости от четности получаем ответ .

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.