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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze