5. príklad - Vzorové riešenie
Kategórie:
5
6
7
8
9
Zadanie
Šošo a Adam sa chceli ísť hrať šach, no zistili,že Adam stratil všetky figúrky okrem jednej veže. Zahrali sa teda inú hru. Vežu postavili do pravého horného rohu šachovnice s rozmermi 8\times 8, a mohla sa pohybovať iba doľava a dole o ľubovoľný počet políčok. Kto vyhrá (a ako to spraví), ak začína Adam a
- ten, ktorý už nemôže spraviť ťah prehrá?
- ten, ktorý už nemôže spraviť ťah vyhrá?
Vzorové riešenie
Opravovali: Imro, merlin, zajo
Pre jednoduchosť si označíme políčka ako na šachovnici, pričom veža začína na políčku H8.
Jediné políčko, z ktorého sa ďalej nevieme pohnúť je políčko A1.
Začneme možnosťou A, v ktorej prehrá hráč, ktorý sa už nedokáže pohnúť. Teda prehrá hráč, ktorý začína svoj ťah na políčku A1. Označme si ho teda červenou (je prehrávajúce).
Všetky ostatné políčka v riadku 1 a stĺpci A budú teda víťazné (viem sa z nich pohnúť na prehrávajúce políčko A1). Tieto si označíme zelenou.
Ako si vieme všimnúť vyhrám ak donútim protihráča pohnúť sa na zelené polička. Miesto odkiaľ sa viem dostať len na zelené teda bude prehrávajúce a teda červené.
Ak sa dokážem z políčka dostať na červené potom je políčko zelené.
Všimnime si, že takéto políčko z ktorého sa vieme dostať len na zelené je ľavé dolné nevyfarbené a teda B2(bude červené.)
Situácia sa nám teda zopakovala, že si zafarbím na zeleno stĺpec a riadok, z ktorého sa viem na B2 dostať.
Takýmto spôsobom budem zafarbovať tabuľku.
Vidíme, že červené políčka sú len na uhlopriečke. Takže vyhrám ak sa presuniem na uhlopriečku. Keďže Adam začína na uhlopriečke a nemôže sa hýbať šikmo nemôže sa presunúť na uhlopriečku. Šošo sa na uhlopriečku dostane tak, že ak Adam pôjde o n poličok tak Šošo pôjde o n políčok do druhého smeru (ľavo/ dole).
Teda Šošo má víťaznú stratégiu.
Možnosť B:
Ak sa hráč nevie už pohnúť, tak vyhral. Teda políčko A1 je vyhrávajúce (zafarbíme ho na zeleno).
Teraz existujú 2 políčka, z ktorých sa dokážem pohnúť len na políčko A1, a to B1 a A2. Tie sú teda prehrávajúce a zafarbíme ich na červeno.
Teraz si môžem všetky políčka v riadkoch 1 a 2 a v stĺpcoch A a B (okrem políčok B1 a A2) zafarbiť na zeleno, lebo sa z nich dokážem posunúť na červené políčko.
Tabuľku ďalej budeme ofarbovať pomocou rovnakých pravidiel, ako v možnosti A.
Ako si môžme všimnúť, Adam sa na začiatku môže pohnúť len na zelené políčka, teda Šošo má znova výhernú stratégiu (bude sa stále posúvať na prehrávajúce políčka).
Jediné políčko, z ktorého sa ďalej nevieme pohnúť je políčko A1.
Začneme možnosťou A, v ktorej prehrá hráč, ktorý sa už nedokáže pohnúť. Teda prehrá hráč, ktorý začína svoj ťah na políčku A1. Označme si ho teda červenou (je prehrávajúce).
Všetky ostatné políčka v riadku 1 a stĺpci A budú teda víťazné (viem sa z nich pohnúť na prehrávajúce políčko A1). Tieto si označíme zelenou.
Ako si vieme všimnúť vyhrám ak donútim protihráča pohnúť sa na zelené polička. Miesto odkiaľ sa viem dostať len na zelené teda bude prehrávajúce a teda červené.
Ak sa dokážem z políčka dostať na červené potom je políčko zelené.
Všimnime si, že takéto políčko z ktorého sa vieme dostať len na zelené je ľavé dolné nevyfarbené a teda B2(bude červené.)
Situácia sa nám teda zopakovala, že si zafarbím na zeleno stĺpec a riadok, z ktorého sa viem na B2 dostať.
Takýmto spôsobom budem zafarbovať tabuľku.
Vidíme, že červené políčka sú len na uhlopriečke. Takže vyhrám ak sa presuniem na uhlopriečku. Keďže Adam začína na uhlopriečke a nemôže sa hýbať šikmo nemôže sa presunúť na uhlopriečku. Šošo sa na uhlopriečku dostane tak, že ak Adam pôjde o n poličok tak Šošo pôjde o n políčok do druhého smeru (ľavo/ dole).
Teda Šošo má víťaznú stratégiu.
Postupné ofarbovanie šachovnice (Možnosť A)
Ak sa hráč nevie už pohnúť, tak vyhral. Teda políčko A1 je vyhrávajúce (zafarbíme ho na zeleno).
Teraz existujú 2 políčka, z ktorých sa dokážem pohnúť len na políčko A1, a to B1 a A2. Tie sú teda prehrávajúce a zafarbíme ich na červeno.
Teraz si môžem všetky políčka v riadkoch 1 a 2 a v stĺpcoch A a B (okrem políčok B1 a A2) zafarbiť na zeleno, lebo sa z nich dokážem posunúť na červené políčko.
Tabuľku ďalej budeme ofarbovať pomocou rovnakých pravidiel, ako v možnosti A.
Ako si môžme všimnúť, Adam sa na začiatku môže pohnúť len na zelené políčka, teda Šošo má znova výhernú stratégiu (bude sa stále posúvať na prehrávajúce políčka).
Postupné ofarbovanie šachovnice (Možnosť B)