Mřížové body

Úloha číslo: 3791

Mřížové body v rovině jsou obarveny 2015 barvami. Ukažte, že lze zvolit 2014 řádků a 2016 sloupců tak, že všechny jejich průsečíky mají stejnou barvu.

(Mřížové body jsou body, které mají obě souřadnice celočíselné. Řádek je tvořen body se stejnou souřadnicí \(y\), a podobně sloupec pro souřadnici \(x\).)

  • Nápověda

    Uvažujte \(n\) řádků pro \(n\) dostatečně velké. Každému sloupci přiřaďte \(n\)-tici barev odpovídající průnikům se zvolenými řádky. A najděte sloupce se stejnými \(n\)-ticemi.

  • Řešení

    Vybereme-li \(n=2015*2013+1\) řádků, potom se v každém sloupci bude podle Dirichletova principu alespoň jedna z 2015 barev vyskytovat 2014-krát.

    Nyní stačí vzít \(m=2015^n\cdot2015+1\) sloupců. Každý sloupec určuje uspořádanou \(n\)-tici použitých barev. Při zvoleném počtu sloupců se opět podle Dirichletova principu dá určit 2016 sloupců se stejnými \(n\)-ticemi barev.

    Podle příslušné \(n\)-tice barev je již snadné vybrat potřebných 2014 řádků.

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