4. príklad - Vzorové riešenie
Zadanie
Parkovisko má tvar tabuľky 2023 \times 2023, pričom každý jej štvorček 1 \times 1 svieti buď na červeno, alebo na zeleno. Platí, že práve v 1012 riadkoch je väčšina štvorčekov červených a práve 1012 stĺpcov má väčšinu štvorčekov zelených. Nájdite najväčšiu možnú stranu jednofarebného štvorca, ktorý sa skalá z niekoľkých štvorčekov tabuľky.
Vzorové riešenie
Experimentovaním s menšími tabuľkami (napríklad 5,7) môžeme dostať nápad, že pre tabuľku so stranou dĺžky 2n+1 je odpoveď n.
Túto úlohu môžeme vyriešiť tak, že ukážeme pre aké rozmery najväčšieho štvorca už úloha vyriešiť nejde. A potom nájdeme také riešnie, ktoré má štvorec len o 1 menší.
Ako prvé ukážeme, že v tabuľke nemôže byť jednofarebný štvorec so stranou dĺžky väčšiou ako 1012.
Ak by existoval červený štvorec so stranou dĺžky aspoň 1012, tak by muselo byť aspoň 1012 stĺpcov, v ktorých je 1012 červených štvorčekov čo je väčšina. Potom by bolo najviac 2023-1012 = 1011 stĺpcov v ktorých je väčšina štvorčekov zelených, čo podľa zadania nemôže.
Ak by existoval zelený štvorec so stranou dĺžky aspoň 1012, tak by muselo byť aspoň 1012 riadkov, v ktorých je väčšina štvorčekov zelených. Potom by bolo najviac 1011 riadkov v ktorých je väčšina štvorčekov červených, čo tiež podľa zadania byť nemôže.
Teraz ukážeme, že jednofarebný štvorec s dĺžkou strany 1011 môže existovať. Nájdeme také ofarbenie, že v tabuľke existuje jednofarebný štvorec s dĺžkou strany 1011.
Každému štvorčeku priradíme unikátnu dvojicu čísel i,j, pričom i označuje číslo stĺpca (číslujeme zľava do prava) a j označuje číslo riadku (číslujeme zhora dole). Na zeleno ofarbíme práve tie políčka, pre ktoré platí jedno z nasledujúcich:
- i aj j sú 1012
- i aj j sú menšie ako 1012
- j je väčšie ako 1012
Takto dosiahneme, že v ľavom hornom rohu máme štvorec so stranou 1011, ktorý je celý zelený. Zároveň je v prvých 1011 riadkoch 1012 červených políčok a v strednom riadku 2022 červených políčok, takže pravidlo s riadkami sme splnili. A zas v prvých 1011 stĺpcoch máme 2022 zelených políčok a v prostrednom stĺpci máme 1012 zelených políčok, takže aj pravidlo so stĺpcami sme splnili.
Kedže tabuľka 2023 \cdot 2023 je príliš veľká aby sme ju vedeli dať do vzorového riešenia, tak na nasledujúcom obrázku je riešenie pre tabuľku so stranou 11. Veľmi ľaho si potom môžete predstaviť, že riešenie pre stranu 2023 bude vyzerať rovnako ale každý zo štvorcov v rohoch bude mať veľkost strany 1011 a stredný riadok a stĺpec budú vyzerať rovnako.
Odpoveď: Najväčšia možná strana jednofarebného štvorca má dĺžku 1011.