Sudé a liché podmnožiny
Úloha číslo: 3301
Ukažtě, že pro každou neprázdnou konečnou množinu platí, že počet jejích podmnožin sudé velikosti (o sudém počtu prvků) je roven počtu jejích podmnožin liché velikosti.
Řešení
Dokazujeme indukcí podle velikosti nosné množiny. Jednoprvková množina má dvě podmnožiny: prázdnou sudé velkikosti a sebe samu liché velikosti.
Indukční krok \(n \to n+1\): zvolme si libovolný prvek \(a\). Z indukčního předpokladu je počet sudých podmnožin neobsahujících \(a\) stejný jako počet lichých podmnožin neobsahujících \(a\).
Ovšem každá sudá podmnožina obsahující \(a\) se skládá z \(a\) a zbytku o lichém počtu prvků, a obráceně.
Tedy počet všech sudých = počet sudých s \(a\) + počet sudých bez \(a\) = počet lichých bez \(a\) + počet sudých bez \(a\) = počet lichých bez \(a\) + počet lichých s \(a\) = počet všech lichých.