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ů.