kms - fórum o príkladoch

1. príklad 3. zimnej série 2013/2014

Zadanie:
Počas putovania si Monty so Sinetuom vždy pred spaním vytiahli z plecniaka nekonečnú štvorčekovú sieť a ceruzku a zahrali sa nasledujúcu hru. Monty najskôr vyfarbil jeden zo štvorčekov. Potom si Sinetu vybral iný štvorček a tiež ho vyfarbil. Takto sa striedali, až kým nebolo vyfarbených šesť štvorčekov. Štvorčeky, ktoré pridávali, si však nemohli vyberať len tak ledabolo. Štvorček, ktorý pridali, musel spĺňať nasledujúce podmienky:

nový štvorček musí susediť hranou s aspoň jedným už vyfarbeným štvorčekom (toto sa nevzťahuje na úplne prvý štvorček, ktorý vyfarbil Monty);

nový štvorček nesmie spolu s nejakou trojicou už vyfarbených štvorčekov vytvoriť štvorec $2\times 2$ (týmto sa nemusia trápiť, kým sú vyfarbené menej ako tri štvorčeky).

Nakoniec si útvar zložený z vyfarbených štvorčekov vystrihli. V prípade, že tento útvar tvoril plášť kocky,¹ tak hru vyhral Sinetu, v opačnom prípade vyhral Monty. Dokážte, že pre Sinetua existuje víťazná stratégia (t.j., že vie vyhrať, nech hrá Monty akokoľvek) a aj ju popíšte.

¹Útvar zo šiestich štvorčekov tvorí plášť kocky, ak sa doňho dá obaliť kocka s veľkosťou steny jeden štvorček, tak, že každý štvorček z útvaru pokrýva práve jednu stenu kocky.

Naspäť na príklady | Napíš príspevok