Zadanie

Jožo nedávno objavil Japonský šach (šógi). Šógi sa hrá na šachovnici \(9 \times 9\) políčok. Figúrka povýšený strelec ohrozuje políčka, ktoré sa nachádzajú v rovnakej uhlopriečke (ako strelec v bežnom šachu) a navyše aj políčka, ktoré majú spoločnú hranu s políčkom, na ktorom povýšený strelec stojí. Koľko najviac povýšených strelcov môže Jožo umiestniť na šachovnicu tak, aby sa žiadni dvaja neohrozovali?

Pri tomto type úloh začneme väčšinou skúšaním. V našom prípade sa snažíme uložiť na šachovnicu čo najviac strelcov. Vyskúšame napríklad na začiatok každej druhej uhlopriečky položiť strelca (aby spolu nesusedili) a následne pokračujeme po obvode a položíme strelcov na koniec každej, ešte neohrozenej, uhlopriečky. Metódou pokus-omyl skôr či neskôr zistíme, že viac ako \(15\) strelcov sa nám nepodarí uložiť. Teraz prichádza čas zamyslieť sa nad tým, koľko najviac strelcov vieme umiestniť na šachovnicu.

Pozrime sa na uhlopriečky v jednom smere, napríklad zľava doprava (viď obrázok). Je ich tam \(17\). Ak položíme strelca na niektorú uhlopriečku, je ohrozená celá a už na ňu nemôžeme položiť ďalšieho. Z toho môžeme usúdiť, že viac ako \(17\) strelcov určite umiestniť nevieme. Avšak naši strelci sa ohrozujú nie len na uhlopriečkach, ale aj na susedných políčkach. To je problém napríklad v ľavom dolnom rohu. Ak dáme strelca na políčko v rohu, tak ohrozuje obe políčka susednej uhlopriečky, a teda na ňu nevieme položiť strelca. Ak miesto toho dáme strelca na druhú uhlopriečku, bude ohrozovať políčko v rohu a nebudeme môcť naň položiť ďalšieho. Na tieto dve rohové uhlopriečky vieme teda položiť iba jedného strelca, nie dvoch. Celkový počet strelcov sa nám zníži na \(16\). Keďže tento problém je aj v opačnom rohu, bude to len \(15\). Rozloženie \(15\) strelcov na šachovnici sme našli už na začiatku, takže sme úlohu vyriešili.

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ť.