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.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze