Zadanie
Počas prehliadky hradu zvnútra sa Kubko trochu nechal strhnúť krásou fresiek na stenách a pútavými slovami sprievodkyne. Najviac ho však zaujalo, keď sprievodkyňa začala rozprávať o japonskom šachu, ktorý hrávali japonskí Šogúni a Daimjóvia.
V japonskej verzii šachu existuje figúrka strieborného generála, ktorá vie byť otočená jedným zo štyroch základných smerov. Strieborný generál ohrozuje políčka, ktoré s ním susedia diagonálne a jedno políčko pred sebou (podľa toho, ktorým smerom je otočený). Koľko najviac figúrok Strieborných generálov je možné umiestniť na šachovnicu \(8 \times 8\) tak, aby žiadna figúrka strieborného generála neohrozovala inú figúrku?
Dobrým začiatkom pri riešení takýchto úloh je skúsiť koľko najviac figúrok vieme na hraciu plochu dostať. V tomto prípade to ide pomerne ľahko – vyberieme si nejaký riadok (alebo stĺpec) a keď otočíme všetkých generálov tak, aby sa pozerali na políčka mimo daného riadku, môžeme ho zaplniť celý. Oba riadky susediace s tým, ktorý sme práve zaplnili, sú ohrozené, ale ostatné riadky môžeme ďalej zapĺňať. Takouto taktikou vieme zaplniť generálmi každý druhý riadok, a žiadni z nich sa nebudú ohrozovať. Príklad ako to môže vyzerať je na obrázku nižšie.
Umiestnili sme \(32\) generálov, čo je celkom dosť. Teraz potrebujeme dokázať, že viac ich tam umiestniť nejde (ak by sa nám to nepodarilo, naznačovalo by to, že ich tam ide umiestniť viac a mali by sme sa viac snažiť). Aby sme to dokázali, úlohu si najprv zjednodušíme. Šachovnicu \(8 \times 8\) si zmenšíme na šachovničku \(2 \times 2\) a zamyslíme sa, koľko najviac generálov sa zmestí na ňu. Či už krátkou úvahou, alebo vyskúšaním všetkých možností zistíme, že na šachovničke \(2 \times 2\) je možné umiestniť najviac dvoch generálov tak, aby sa neohrozovali.
Teraz sa vrátime k veľkej šachovnici \(8 \times 8\). Môžeme si všimnúť, že sa skladá z \(16\) menších šachovničiek \(2 \times 2\) (štvorcov so stranou dĺžky \(2\)). Vieme, že v každom z nich môžu byť najviac dvaja generáli, čo znamená, že na celej veľkej šachovnici môže byť najviac \(2 \cdot 16 = 32\) generálov. Toľko sa nám tam aj podarilo umiestniť, čiže je to naozaj najväčší možný počet.
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ť.