Zobecněné latinské čtverce
Úloha číslo: 3771
Mějme čtverec \(n\times n\) a pro každý sloupec seznam \(n\) ne nutně různých symbolů. Sjednocení seznamů obsahuje tedy \(n^2\) symbolů, přičemž se v tomto sjednocení vyskytuje právě \(n\) různých symbolů a každý z nich právě \(n\)-krát.
Ukažte, že symboly lze rozmístit na pole čtverce tak, že každý sloupec obsahuje symboly z předepsaného seznamu, a přitom se v žádném řádku se žádné dva symboly neopakují.
(Pozn. pokud by měl každý sloupec předepsán seznam všech \(n\) symbolů, dostali bychom latinský čtverec.)
Řešení
Postupně vyplňujeme řádky. Po vyplnění \(i\) řádků platí, že aktuální seznamy obsahují \(n-i\) doposud nepoužitých symbolů a že každému symbolu zbývá \(n-i\) výskytů.
Vytvoříme množinový systém na množině symbolů, kde \(S_j\) je množina symbolů použitelných na doplnění \(j\)-tého sloupce (tedy vznikne z aktuálního seznamu pro \(j\)-tý sloupec odstraněním duplicit).
Ověříme Hallovu podmínku: pro každé \(J\subseteq [n]\) musí \(\bigcup_{j\in J} S_j\) obsahovat alespoň \(|J|\) různých symbolů – sjednocení příslušných seznamů má \(|J|(n-i)\) prvků a každý symbol může mít nejvýše \(n-i\) výskytů.
Tedy pro systém \((S_j)_{j\in [n]}\) existuje systém různých reprezentantů a tento systém různých reprezentantů odpovídá vyplnění \((i+1)\)-ho řádku.