Množiny o n-1 prvcích

Úloha číslo: 3766

Pro \(n\ge 2\) buďte \(A_1,\ldots,A_n\) navzájem různé množiny o alespoň \(n-1\) prvcích. Dokažte, že pro množinový systém \((\bigcup_i A_i,\{A_1,\ldots,A_n\})\) existuje systém různých reprezentantů.

  • Řešení

    Sjednocení libovolných nejvýše \(n-1\) množin obsahuje alespoň jednu celou množinu, tedy alespoň \(n-1\) prvků. Ve sjednocení všech \(n\) množin se vyskytují alespoň dvě různé množiny, jejich sjednocení má alespoň \(n\) prvků.

    Hallova podmínka je tedy splněna, a proto existuje i systém různých reprezentantů.

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