Riešky výlet - Ahojte Rieškari, jar je v plnom prúde, vonku je pekne a my sa chystáme na výlet! Zoberte batohy, hry, frisbee, kamarátov a hlavne dobrú náladu a poďte sa s nami … Prejsť na článok
×10. príklad - Vzorové riešenie
Zadanie
Hra sa hrá v jednom rade políčok veľkosti 2024\times1. Dvaja hráči - vedúci spoločne a Matej sa striedajú v ťahoch. Začínajú vedúci. V každom ťahu hráč umiestni do voľného políčka S alebo U. Hráč, ktorý vytvorí tri políčka po sebe, v ktorých je nápis SUS vyhráva. Ak sa minú všetky políčka a žiaden hráč nevyhrá, tak nastáva remíza. Určite, ktorý hráč má výhernú stratégiu, prípadne dokážte, že si obaja hráči môžu vynútiť remízu.
Vzorové riešenie
Pod znakom "\_" si budeme predstavovať voľné políčko. Dokážeme, že Matej vie vyhrať bez ohľadu na to, ako hrajú vedúci.
Predstavme si, že nastane situácia:
S \_ \ \_ \ S
Ak niektorý z hráčov zahrá do niektorého z týchto dvoch voľných políčok S, tak druhý hráč môže zahrať do druhého políčka U a vyhrať. Podobne ak niektorý z hráčov zahrá do niektorého z týchto políčok U, tak druhý hráč môže zahrať do druhého políčka S a vyhrať.
Keďže tabuľka má rozmer 2024, tak Matej vie vo svojom prvom ťahu umiestniť S tak, aby bolo aspoň 500 políčok od kraja a od políčka zaplneného vedúcimi. Potom bez ohľadu na to, čo zahrajú vedúci, Matej vie umiestniť S tak, aby vzniklo S \_ \ \_ S. Takže od tohto momentu už hra nebude vedieť skončiť remízou. Takže nám už len stačí ukázať, že Matej vie hrať tak, aby neprehral.
Ak sa stane, že je Matej na ťahu a vie dokončiť SUS, tak ho dokončí a vyhrá. Teraz predpokladajme, že taký ťah neexistuje. Dokážeme, že Matej vie zahrať taký ťah, aby takáto situácia nevznikla. Keďže je Matej druhý hráč, keď je na ťahu, tak je nevyplnených nepárny počet políčok. To znamená, že existuje voľné políčko, ktoré má dvoch voľných, alebo dvoch zaplnených susedov. V oboch prípadoch umiestnením U do tohto voľného políčka nemôže vytvoriť situáciu, kde stačí jeden ťah na vytvorenie SUS.
Dokázali sme, že Matej vie zaručiť, aby hra mala víťaza a navyše sme ukázali, že Matej vo svojom ťahu buď vyhrá, alebo si zaručí, že ďalší ťah nie je pre vedúcich výherný. Keďže sa hra niekedy skončí, tak Matej musí byť jej víťazom.
Odpoveď: Matej si vie zaručiť výhru bez ohľadu na to, aké ťahy hrajú vedúci.