2001-gre-vs-practice.pdf/Q41

Вопрос: Q41-e5724f

Задача зарезервирована: илья52 11:05, 21 декабря 2024 (UTC)

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

Ответы

• определенной формулы нет

Объяснение

Исходники — вопрос 41 на 34 странице книги «2001-gre-vs-practice.pdf» Количество подмножеств, какого - либо конечного множества равно , где мощность множества. Докажем данную формулу. Упорядочим каким - либо образом все элементы множества . Сопоставим последовательность нулей и единиц каждому подмножеству следующим образом: если j-ый элемент множества содержится в подмножестве , то в последовательности из нулей и единиц будет стоять 1, в противном случае 0. Таким образом, получено взаимно однозначное соответствие между битовыми последовательностями и подмножествами. Битовых последовательностей .

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

Пусть четное. Установим биекцию между четными и нечетными подмножествами.

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

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

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