Vyplnění matice
Úloha číslo: 3744
V matici \(10 \times 10\) jsou čísla \(\{1{,}2,\ldots,10\}\) zapsána tak, že každé číslo má deset výskytů. Ukažte, že pak v některém sloupci nebo řádku nalezneme alespoň čtyři různá čísla.
Obecně, když se v matici \(n \times n\) každé číslo vyskytuje přesně \(n\)-krát, potom nějaký řádek či sloupec má aspoň \(\sqrt{n}\) různých čísel. Pokud je \(\sqrt{n}\) celé číslo, je ten odhad těsný.
Řešení
Označme si řádky indexy \(1,…,10\) a sloupce \(11,…,20\).
Pro spor předpokládejme, že každě číslo (symbol) má v každém řádku či sloupci nejvýše tři výskyty.
Dvěma způsoby odhadneme počet dvojic \((i,s)\), kde \(i\) je index řádku nebo sloupce a \(s\) je symbol, který se v příslušném řádku nebo sloupci vyskytuje.
\(\#(i,s)\le 20{\cdot} 3\), protože v každém z dvaceti řádků či sloupcu nalezneme nejvýše tři různé symboly.
Rozborem případů si všimneme, že počet dvojic \((i,s)\) s pevně zvoleným \(s\) je alespoň 7: Bez újmy na obecnosti můžeme předpokládat, že \(s\) se vyskytuje ve více sloupcích než řádcích. Je-li všech 10 symbolů \(s\) v jednom řádku, máme 11 dvojic \((i,s)\); jsou-li ve dvou řádcích, je těch dvojic alespoň 7; a stejně tak, jsou-li ve třech řádcích.
Odtud \(\#(i,s)\ge 10{\cdot} 7\), což už vede ke sporu.
Pozn., v obecném případě je třeba dokázat, že počet dvojic s pevným \(s\) je alespoň \(2\sqrt{n}\).