К содержанию
Quantoros

Почему у непустого n-элементного множества ровно 2^(n-1) подмножеств чётного размера, включая пустое?

Quant ResearchУровень: ПрактикаParity bijection

Почему у непустого n-элементного множества ровно 2^(n-1) подмножеств чётного размера, включая пустое?

Подсказки
  • Найдите операцию смены чётности.
  • Она должна быть обратимой.

Ответ

Выберите один элемент и меняйте его наличие. Это обратимое сопоставление чётных и нечётных подмножеств. Всего их 2^n, поэтому каждого вида половина.

Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros

Похожие вопросы