Zadanie
Plavba bola pohodlná a my sme rýchlo zaspali. Keď však z oblohy zostúpil Stefan-Boltzmannov zákon a namiesto neho sa tam vyhupli Fresnelove rovnice, Jubilár opatrne vstal a špľach! do vody. Preplával na breh Červenej rieky, kde ho čakal zástup Legendrových polynómov vyzbrojených kušami, a ukázal im prstom na našu bezbrannú plť. Polynómy sa zaškerili (teda asi, ja som práve spal, čiže som ich nevidel) a vypustili smrtiacu salvu šípov. Keďže však chcú šetriť muníciou, nakreslili si najskôr plánik toho úseku rieky a zamierili iba na také miesta, aby si boli isté, že našu plť trafia.
Máme prázdnu tabuľku veľkosti \(7 \times 7\) štvorčekov. Koľko najmenej políčok musíme vyfarbiť na čierno, aby v tabuľke nebolo \(5\) prázdnych políčok, ktoré tvoria diagonály štvorca \(3 \times 3\) (ako na obrázku)?
Pre ľahšie vysvetľovanie pomenujme útvar zo zadania ako krížik.
Na to, aby sme mohli povedať, že máme riešenie s najnižším počtom políčok, potrebujeme spraviť dve veci. Jednak sa musíme uistiť, že pre počet vyfarbených štvorčekov platí podmienka zo zadania, a dvak, že ak by sme mali štvorčekov menej, určite by sa dal v tabuľke nájsť biely krížik.
Prvá časť sa dá vyriešiť vcelku jednoducho. Budeme skúšať všakovaké zafarbenia políčok tabuľky \(7 \times 7\), ktoré spĺňajú zadanie. Skvelá pomoc v tomto prípade je fakt, že krížik má šírku aj výšku \(3\) políčka. Rovnako tak zaberá všetky rohy štvorca \(3 \times 3\). Vidíme teda, že sa nevlezie celý do dvoch krajných vrstiev políčok a bez ohľadu na to, ako ho umiestnime, určite bude zaberať aspoň jedno z prostredných \(9\) políčok. Po ich zafarbení tak máme istotu, že žiadna pätica prázdnych políčok nebude tvoriť krížik. Ľahko si všimneme, že dokonca nemusíme začierniť prostredné a stále bude táto podmienka platiť. Otázka teraz znie, či nestačí aj menej ako \(8\) políčok.
Jedna z vecí, ktorú si môžeme uvedomiť pri našom ofarbení, je fakt, že nevieme len tak prefarbiť políčko z čierneho na biele bez toho, aby vznikol biely krížik. Avšak rôznych ofarbení \(8\) políčok môže existovať viac a hľadať ich, aby sme otestovali všetky, môže byť dosť pracné. Lepšie pozorovanie je fakt, že ak nejaké dva krížiky nemajú spoločné políčko, zafarbením len \(1\) políčka zostane jeden krížik celý biely. Podobne, ak by sme mali viac krížikov, z ktorých žiadne dva nemajú spoločné políčko, museli by sme zafarbiť po jednom políčku z každého z nich. V našom prípade nám teda stačí v štvorci \(7 \times 7\) nájsť \(8\) takých krížikov, že žiadna dvojica nemá spoločné políčko. Potom budeme vedieť, že menej ako \(8\) začiernených políčok nestačí. Príklad takýchto osem krížikov môžeme vidieť na obrázku.
Ukázali sme teda, že \(8\) štvorčekov nám stačí vyfarbiť, a rovnako aj, že menej ako \(8\) nestačí, takže máme správne riešenie.
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ť.