Zadanie
Zatiaľ, čo Turci pri Moháči márne hľadali svojho sultána, uhorskí generáli domýšľali novú vojenskú taktiku, ktorou by získali prevahu nad nepriateľom. Šlo o štvorcovú formáciu s krycím názvom „Korytnačka“, v ktorej by podľa istých pravidiel spolu bojovalo niekoľko šermiarov s bielymi a čiernymi štítmi ako jeden celok. Žiaden generál však nevedel predpovedať, či táto formácia môže byť dostatočne veľká na to, aby porazila Turkov. A to i napriek tomu, že sa im podarilo daný problém zúžiť na nasledovnú úlohu:
Majme štvorcovú tabuľku zloženú z \(n \times n\) menších štvorčekov. Každý štvorček je zafarbený buď nabielo, alebo načierno. Pre každú dvojicu stĺpcov a každú dvojicu riadkov platí, že štyri štvorčeky ich prieniku nesmú byť jednej farby. Aké najväčšie môže byť \(n\)?
Najväčšie možné \(n\) je \(4\). Dokážeme, že pre tabuľku \(4 \times 4\) sa nám podarí nájsť vhodné zafarbenie a pre \(n\) väčšie ako \(4\) také zafarbenie sa nedá nájsť.
Pre \(n = 4\), takéto vhodné zafarbenie vieme nájsť, stačí skontrolovať, že všetky štvorice štvorčekov, ktoré sú prieniky dvoch riadkov a dvoch stĺpcov (Akoby tvoria rohy obdĺžniky) majú aspoň jeden štvorček z každej farby.
Pre \(n\) väčšie ako \(4\), vždy môžeme nájsť tabuľku veľkosti \(5 \times 5\) v tabuľke \(n \times n\). Ak dokážeme, že nemôžeme nájsť vhodné zafarbenie pre \(n = 5\), tak nebudeme môcť nájsť ani vhodné zafarbenie pre \(n > 5\).
V tabuľke \(5 \times 5\) má každý riadok a stĺpec \(5\) štvorčekov. Teda v každom riadku a stĺpci budú aspoň \(3\) čierne štvorčeky alebo aspoň \(3\) biele štvorčeky. Povieme, že stĺpec alebo riadok má dominantnú čiernu alebo bielu farbu.
Keďže máme \(5\) stĺpcov, tak aspoň tri z nich budú mať rovnakú dominantnú farbu. Môžeme predpokladať že táto dominantná farba je čierna a prvé \(3\) stĺpce majú čiernu dominantnú.
Keď nakreslíme prvé dva stĺpce, tak najviac jeden riadok môže mať dva čierne štvorčeky, inak by sme mali prienik ktorý má \(4\) štvorčeky rovnakej farby. Vždy tam bude riadok s dvomi čiernymi štvorčekmi, takže to musí vyzerať ako na našom obrázku, len riadky môžu byť poprehadzované.
Keď chceme pridať \(3\) čierne štvorčeky do tretieho stĺpca, nemôžeme dať čierny štvorček do toho istého riadku, kde už sú dva čierne štvorčeky. Keby štvorček \(x\) bol čierny, tak ostatné \(4\) štvorčeky v tomto stĺpci by museli byť biele. Ale predpokladali sme, že v tomto stĺpci sú \(3\) čierne štvorčeky. Teda štvorček označený \(x\) bude určite biely.
Teda \(3\) zo \(4\) štvorčekov \(y\) budú čierne. A teda buď \(1.\) a \(4.\) riadok alebo \(2.\) a \(3.\) riadok budú mať čierne štvorčeky v treťom stĺpci a vznikne v tých dvoch riadkoch prienik z dvoma stĺpcami tej istej farby. Teda pre \(n\) väčšie ako \(4\), nemôžeme nájsť také zafarbenie, kde ani jeden prienik pozostávajúci zo štyroch štvorčekov nie je jednofarebný.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.