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}\).

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