Zadanie
Telefonát bol mimoriadne plodný a okrem nových nadávok sa z neho naši astronauti naučili, že na pokusy potrebujú inteligentné formy života. Tie sa vraj vyznačujú tým, že majú ruky. Bez ohľadu na počet nôh, rohov, či očí, im bude ich súčasný Marťan na nič. Potrebujú na ich loď nalákať iného, ideálne na niečo pestrofarebné...
Je dané kladné celé \(n\). Patrick Matthews našiel na lodi veľkú hŕbu kartičiek s tabuľkami \(n\times n\). Začal ich vyfarbovať červenou, žltou, zelenou a modrou (každé políčko práve jednou) farbou tak, aby v každom štvorci \(2\times2\) bola každá farba práve raz. Každú kartičku, ktorú ofarbil, ofarbil inak, pričom ofarbenia líšiace sa iba otočením nepovažujeme za rôzne (ale ofarbenia líšiace sa prevrátením rozlišujeme). Časom ho to omrzelo, lebo sa mu minuli ofarbenia.
Matthew Patricks našiel na lodi rovnakú hŕbu kartičiek. Začal svoje kartičky tiež vyfarbovať červenou, žltou, zelenou a modrou tak, že v hornom riadku zafarbil políčka striedavo dvomi z týchto farieb a potom tie isté farby použil v každom nepárnom riadku zhora, no mohol zmeniť farbu, ktorou začal (čiže v každom riadku mal dve možnosti). Každý párny riadok zhora zafarbil striedavo zvyšnými dvoma farbami, pričom opäť si v každom z riadkov mohol vybrať počiatočnú farbu. Aj jeho to časom omrzelo, lebo sa mu minuli ofarbenia.
Majú naši astronauti rovnaké zbierky farebných kartičiek? Pamätajte, že ofarbenia líšiace sa iba otočením nepovažujeme za rôzne.
Keďže zadanie pred nás postavilo ťažko riešiteľnú úlohu ako prirodzene pomenovať kozmonautov, tak budeme Patricka Matthewsa volať Patrick a Matthewa Patricksa budeme volať Matthew.
Zadanie po nás chce, aby sme ukázali, že dve množiny kartičiek sa rovnajú. To vieme spraviť ukázaním dvoch inklúzií. Prípad \(1\times 1\) je degenerovaný a nebudeme sa ním zaoberať. Riešme pre \(n>1\).
Najprv ukážeme, že každá Matthewova kartička je aj v Patrickovej kope. To je však takmer zjavné. Matthew párne a nepárne riadky zafarbuje inou dvojicou farbičiek, takže ak si v tabuľke zoberieme ľubovoľný štvorec \(2\times 2\), tak horné dve políčka budú mať iné farby ako dolné, keďže sa nachádzajú v riadkoch s inou paritou. Navyše Matthew v každom riadku striedal dvojicu farieb prislúchajúcu danému riadku. Takže aj dvojica horných políčok má vzájomne rozličnú farbu. To isté platí aj pre dvojicu spodných políčok. Zobrali sme si ľubovoľnú Matthewovu kartičku a v nej sme ukázali, že ľubovoľný, takže každý štvorec \(2\times 2\) už obsahuje všetky \(4\) farby. Tzn. túto kartičku nájdeme aj na Patrickovej kope.
Naopak, teraz ukážeme, že každá Patrickova kartička je na Matthewovej kope. Spravme pár pozorovaní:
a. Všimnime si, že v Patrickovej kope neexistuje kartička, na ktorej by niektoré dve susedné políčka mali rovnakú farbu (ani keď susedia len rohom). Inak by štvorec obsahujúci tieto \(2\) políčka nemal všetky \(4\) farby.
b. Všimnime si, že ak na Patrickovej kartičke existuje riadok alebo stĺpec taký, že je celý vyplnený iba dvojicou (podľa a. nutne sa striedajúcich) farieb, tak každý riadok, alebo stĺpec už je dvojfarebný. Tzn. kartička je aj na Matthewovej kope. Prečo? BUNV nech to je riadok, inak si otočíme kartičku. Potom v susednom riadku už nemôže byť políčko s farbou z prvého riadku, inak by v tabuľke bol štvorec obsahujúce toto políčko a dve políčka toho prvého riadku. Tento štvorec by nebol štvorfarebný. Vďaka tomu susedný riadok musí obsahovať iba ostávajúce \(2\) farby. Tie sa podľa a. musia striedať. Rovnaký argument indukciou prevedieme na celú tabuľku. Takže ak existuje riadok obsahujúci iba \(2\) farby, tak už vieme, že daná kartička sa nachádza aj na Matthewovej kope.
c. Ak existuje (BUNV, inak si obrátime tabuľku) riadok ktorý obsahuje tri farby, tak v ňom existuje trojica susedných políčok obsahujúca tieto \(3\) farby. Označme ich \(A,B,C\) a poslednú farbu si označme \(D\). Zelená a modrá farba slúžia iba na označenie políčok.
Všimnime si, že modré políčko rohom susedí s políčkami s farbami \(A,B,C\) takže už musí mať farbu \(D\). Ľahko doplníme farby aj na zelené políčka.
Teraz modré políčko susedí s políčkami s farbami \(C,D,A\) takže už musí mať farbu \(B\). Znovu doplníme farby aj na zelené políčka. Všimnime si, že sme tam, kde sme začali. Indukciou dostávame, že existuje stĺpec v ktorom sa striedajú iba \(2\) farby, takže podľa b. sa príslušná kartička tiež už nachádza na Matthewovej kope.
Ukázali sme, že každá Patricksova kartička je aj na Matthewovej kope, čo dokončuje túto úlohu.
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ť.