Zadanie

Veronika a Aňa sadia kvetinky v záhrade s rozmermi $7 \times 8$. Záhrada je rozdelená na štvorčekové políčka $1 \times 1$. Veronika sadí fialové kvetinky a Aňa sadí ružové kvetinky. Dievčatá sa striedajú v sadení a tá, ktorá zasadí poslednú kvetinku, prehrá. Dievča, ktoré je na ťahu, rozdelí pole na dve časti čiarou rovnobežnou so stranou poľa. Potom si vyberie jednu časť poľa, ktorá obsahuje aspoň jedno voľné políčko, a na všetky voľné políčka tej časti vysadí svoje kvetinky. Ak začína Aňa, ktoré z dievčat má víťaznú stratégiu?1

  1. Hráč má víťaznú stratégiu, ak si vie svojimi ťahmi zaručiť výhru bez ohľadu na to, ako hrá jeho súper.↩

Aňa a Veronika sadia kvetinky. Poďme sa na to ich sadenie pozrieť odzadu. Zo zadania vieme, že komu zostane len jedno voľné políčko \(1\times1\), prehráva. Dievča, ktorému zostane len jeden rad veľkosti \(1 \times n_1\), kde \(n_1 \in \{2, ..., 8\}\), vyhráva, keď rozdelí rad na dve časti: na políčka \(1\times(n_1-1)\) vysadí kvetinky a políčko \(1\times1\) nechá voľné pre druhé dievča. Pri veľkosti záhradky \(2 \times n_2\), kde \(n_2 \in \{3, ..., 8\}\), vyhráva dievča, ktoré je na ťahu, lebo vysadí kvietky na všetky políčka okrem štvorca \(2\times2\). Druhému dievčaťu teda zostal štvorec \(2\times2\) a musí zasadiť kvietky jediným spôsobom, a to tak, že zostane rad veľkosti \(1\times2\) (čo je pre ňu prehrávajúca situácia).

Pri veľkosti záhradky \(3 \times n_3\), kde \(n_3 \in \{4, ..., 8\}\), znovu vyhráva dievča, ktoré je na ťahu. Dievča vysadí kvietky na všetkých políčkach okrem štvorca \(3\times3\). Druhé dievča musí skrátiť pole na buď \(2\times3\), čím prvé dievča môže skrátiť pole na \(2\times2\) a táto situácia je pre druhé dievča prehrávajúca, alebo \(1\times3\), čím prvé dievča skráti pole na \(1\times1\) a druhé dievča opäť prehráva. Analogicky sa to dá ukázať aj pre ďalšie veľkosti záhradky \(4 \times n_4\), kde \(n_4 \in \{5, ..., 8\}\), až \(7 \times n_7\), kde \(n_7 \in \{8\}\). Všimnime si, že dievča, ktoré je na ťahu a má pred sebou štvorcovú plochu prehrá. Môže teda Aňa vyhrať? Áno. Stačí, ak bude Veronike od začiatku nechávať štvorce \(n \times n\), pre vhodné \(n \in\{1, ..., 7\}\).

Aňa začne svoj prvý ťah tak, že vysadí kvietky v ôsmom rade, čím nechá \(7\times7\) políčok pre Veroniku. Nezáleží na tom kam Veronika teraz vysadí kvietky, Aňa ju vždy bude vedieť „dorovnať do štvorca“. Veronika bude musieť sadiť stále v menšom a menšom štvorci, až kým bude sadiť v štvorci \(1\times1\), čím prehrá. Aňa má víťaznú stratégiu a keďže začína na poli \(7\times8\), vie vždy vyhrať.

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