Почему у непустого 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