Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf
súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil(a) chyby, prípadne ti poradí, ako vieš svoje riešenia zlepšiť.
Miško a Lucka sa hrajú hru. Majú plánik, na ktorom je v rade za sebou niekoľko políčok. Na prvom políčku stojí figúrka. Na každom políčku je napísané číslo, ktoré hovorí, ako ďaleko je toto políčko od cieľa (teda v cieli je 0).
Miško a Lucka sa striedajú v ťahoch, Lucka začína. Hráč na ťahu musí pohnúť figúrku o nejaký počet políčok dopredu. Keď hráč na ťahu nemôže spraviť ťah, tak prehrá, teda ten druhý hráč vyhrá.
Miško a Lucka sa dohodnú, na akom plániku idú hrať (koľko má políčok), a aké ťahy majú povolené robiť.
Nás teraz bude zaujímať, kto vyhrá. To samozrejme závisí od toho, ako budú obaja hráči hrať, ale pre každého hráča by bolo najlepšie, keby mal víťaznú stratégiu. To znamená, že vie určite vyhrať, bez ohľadu na to, ako (dobre alebo aj zle) hrá jeho súper.
Predstavme si napríklad, že Miško a Lucka hrajú na plániku so 4 políčkami a hráč na ťahu sa môže hýbať o $1$ alebo $2$ políčka dopredu. Figúrka teda na začiatku stojí na políčku s číslom $3$. Lucka ju potom môže pohnúť na políčko $1$ alebo $2$, ale v oboch prípadoch ju potom Miško vie dať rovno do cieľa. Tam už Lucka nemôže spraviť žiadny ťah. V tomto prípade má teda víťaznú stratégiu Miško.
(20 bodov) Teraz sa Miško a Lucka hrajú takú verziu hry, že figúrka začína na políčku s číslom $10$ a hráč na ťahu môže pohnúť figúrku o $1$ alebo $2$ políčka dopredu. Kto má víťaznú stratégiu a ako má hrať tak, aby určite vyhral?
(20 bodov) Teraz sa dohodli, že môžu posunúť figúrku o $2$, $3$, alebo $5$ políčok dopredu. Ešte si ale nevybrali, na akom plániku budú hrať. Ako by si zistil(a), kto má víťaznú stratégiu, keby ti povedali, koľko políčok má ich plánik?
(30 bodov) Teraz sa dohodli, že v jednom ťahu môžu posunúť figúrku o $1$, $2$, $3$, alebo $5$ políčok dopredu. Navyše nemôžu figúrku posunúť o presne toľko políčok, ako bola posunutá v minulom (súperovom) ťahu. Na začiatku bola figúrka na políčku s číslom $18$, a Lucka ju v prvom ťahu posunula (o $3$ políčka) na políčko s číslom $15$. Kto má teraz víťaznú stratégiu?
(30 bodov) V tomto prípade sa Miško s Luckou ešte nedohodli, aké ťahy môžu robiť. Stále však nemôžu figúrku posunúť o presne toľko políčok, ako bola posunutá v minulom (súperovom) ťahu. Vymysli, ako vieme zistiť, kto má víťaznú stratégiu, na základe počiatočnej pozície figúrky (podľa dĺžky plániku) a toho, aké ťahy sú dovolené.