Задача
COM-B2-M03-P006 Чётных и нечётных поровну
#6
★★★☆☆ Уровень 3 из 5
Докажите, что у \(n\)-элементного множества при \(n\ge1\) число подмножеств чётной мощности равно числу подмножеств нечётной мощности.
Зафиксируйте один элемент и меняйте его присутствие.
Зафиксируем элемент \(a\). Каждому подмножеству \(S\) сопоставим \(S\triangle\{a\}\): если \(a\) был в \(S\), удаляем его, если не был — добавляем. Размер меняется на \(1\), значит чётность размера меняется. Операция обратна сама себе, поэтому это биекция между чётными и нечётными подмножествами.
Отличный пример инволюции.