Sbírka matematických úloh

Barvení čtverce

Úloha číslo: 3745

• Varianta

  Pole mřížky \(21 \times 21\) jsou obarvena tak, že v každém řádku i sloupci se vyskytuje nejvýše 5 různých barev.

  Ukažte, že se některá z barev vyskytuje ve třech řádcích a zároveň i ve třech sloupcích.

• Nápověda

  Dvěma způsoby spočítejte počet dvojic \((p,b)\), kde \(p\) je políčko a \(b\) je barva.

  Rozdělte barvy na dvě skupiny: barvy, které se vyskytují v omezeně mnoha sloupcích, a na zbývající barvy.

• Řešení

  Počet dvojic \((p,b)\) je \(21^2=441\), protože to je celkový počet políček.

  Pro spor předpokládejme, že se každá barva se vyskytuje buď jen ve dvou sloupcích, nebo ve dvou řádcích.

  Z barev, které se vyskytují v nejvýše dvou sloupcích, vytvoříme nanejvýš \(21{\cdot} 5 \cdot 2 = 210 \) dvojic, protože v každém z 21 řádků nalezneme nejvýše 5 různých barev a každá z nich má v tomto řádku nejvýše dva výskyty.

  Ostatní barvy se vyskytují v nejvýše dvou řádcích a podobným způsobem se ukáže, že tvoří také nanejvýš 210 dvojic.

  Uvedenými dvěma způsoby ovšem vytvoříme jen 420 dvojic, což vede ke sporu.

• Varianta

  Šlo by odvodit stejný závěr, pokud by se v každém sloupci i řádku vyskytlo nejvýše 6 různých barev?

• Nápověda

  Dvakrát použijte Dirichletův princip.

• Řešení

  Je možné použít postup z předchozí varianty a navíc argumentovat tím, že každý řádek obsahuje nejvýše 5 "dvousloupcových" barev – kdyby "dvousloupcových" barev bylo 6, šlo by v daném řádku obarvit jen 12 políček z 21, protože jiná barva by už nebyla k dispozici.

  Alternativní postup:

  Opět si barvy rozdělíme na ty, které se vyskytnou v nejvýše dvou řádcích – říkejme jim světlé, a na ty ostatní – říkejme jim tmavé.

  Mřížka má 441 políček, tedy alespoň polovina barev je světlých nebo alespoň polovina tmavých, b.ú.n.o. uvažme, že alespoň 221 políček má světou barvu.

  Podle Dirichletova principu alespoň jeden sloupec \(S\) obsahuje \(\lceil\frac{221}{21}\rceil=11\) světlých políček. Každá z těchto světlých barev má v \(S\) nejvýše dva výskyty. Tedy \(S\) obsahuje alespoň \(\lceil\frac{11}{2}\rceil=6\) světlých barev. Protože každá barva má v každém sloupci nejvýše 6 výskytů, jsou ve sloupci \(S\) jen tyto světlé barvy a žádné tmavé. Tyto světlé barvy mohou v \(S\) obarvit nevýš 12 políček. Zbylá pole by zůstala neobarvená, což je spor.

• Odpověď

  Ano, i zde se některá z barev musí vyskytnout alespoň ve třech řádcích i sloupcích.