Odporúčaný článok

Zadania 2. zimného kola - Ahojte, Rieškari! Prvé zimné kolo máme úspešne za sebou. Čaká nás teda druhé kolo a s ním aj pokračovanie príbehu! Úlohy môžete nájsť tu a máte na ne čas do … Prejsť na článok

×
Kategórie:
5
6
7
8
9

Zadanie

Viktorov útek si predstavme ako hru na doske s 2012 riadkami a k>2 stĺpcami.

Viktor začína niekde v ľavom stĺpci. Dvaja hráči sa striedajú v ťahoch. V každom ťahu posunú Viktora o jedno políčko doprava, hore alebo dole, pričom nesmú vstúpiť na políčko, na ktorom už Viktor bol.

Hra sa skončí vo chvíli, keď Viktor vstúpi do pravého stĺpca.

Hráči spočiatku nevedia, či hráč, ktorý vstúpi do pravého stĺpca, vyhrá alebo prehrá. Dozvedia sa to až vo chvíli, keď Viktor prvýkrát vstúpi do predposledného stĺpca.

Pre ktoré začiatočné políčka má niektorý hráč stratégiu, ktorá mu zaručí výhru? Ak ju má, povedzte ktorý a dokážte, že funguje.

Vzorové riešenie

Opravovali: AlenaChladna, Danko, JakubLaffers

Najskôr sa pozrime na to, čo sa môže stať, keď jeden z hráčov posunie Viktora do predposledného stĺpca.


Ak zistia, že vyhrá ten, čo posunie Viktora do posledného stĺpca, tak ho tam hráč na ťahu hneď a vyhráva. Ak sa ale naopak v poslednom stĺpci prehráva, hráči sa snažia zvoliť taktiku, aby do posledného stĺpca vstúpiť nemuseli. Poďme sa pozrieť, či vie hráč, ktorý je na ťahu hneď po vstúpení do predposledného stĺpca, donútiť toho druhého pohnúť Viktora do posledného stĺpca.


Viktor vstúpi do predposledného stĺpca na niektoré z 2012 políčok. To znamená, že v tom stĺpci je 2011 políčok, na ktorých ešte nebol. Niektoré políčka sú nad ním a zvyšné pod ním. Niektorým smerom (nad ním alebo pod ním) musí byť nepárny počet políčok, keďže 2011 je nepárne číslo a súčet dvoch čísel bude nepárny iba vtedy, keď je jedno z nich nepárne a druhé párne.


Hráč, ktorý je práve na ťahu sa teda rozhoduje, či sa pohne smerom, kde je párny počet políčok, alebo nepárny počet políčok.


Ak sa hráč na ťahu pohne v nejakom smere, napríklad dole, tak jeho súper má jedinú možnosť ako pokračovať bez okamžitej prehry. Ak by totiž Viktora posunul doprava do posledného stĺpca, tak by hneď prehral. Naspäť ho pohnúť nemôže, keďže na tom políčku už Viktor bol, a teda sa musí pohnúť ďalej dole. Hráč, ktorý v tomto stĺpci začínal, Viktora pohne znova dole, pretože podobne nemá inú možnosť. takto sa budú striedať, keďže ani jeden z nich nemôže urobiť iný ťah ak nechce prehrať. To sa skončí až keď sa Viktor dostanena spodok tabuľky, kedy bude hráč na ťahu môcť ísť iba doprava, čím prehrá. To, ktorý hráč bude vtedy na ťahu záleží práve od toho, či je počet navštívených políčok párny alebo nepárny. Ak je nepárny, tak aj počet ťahov, ktoré hráči urobia, je nepárny. Teda hráč ktorý v stĺpci začínal a robí prvý, tretí, piaty ťah, a tak ďalej, musel práve urobiť ťah a na ťahu je teraz druhý hráč, ktorý teda nemá inú možnosť ako prehrať. Keďže hráč, ktorý je na ťahu pri vstupe do predposledného stĺpca, si vie vždy vybrať smer, v ktorom je nenavštívený nepárny počet políčok, vždy vie súpera donútiť prehrať, bez ohľadu na to, či je posledný stĺpec vyhrávajúci alebo prehrávajúci. 


Ako môže teda niektorý z hráčov donútiť toho druhého, aby vstúpil do predposledného stĺpca? Hráč, ktorý bude na ťahu pri vstupe do tretieho stĺpca z prava vie uplatniť rovnakú taktiku ako pre predposledný stĺpec, aby donútil súpera presunúť Viktora do predposledného stĺpca. Následne je na ťahu a už vieme, že vyhrá. Takto to funguje aj pri skorších stĺpcoch. Ak hráč ťahá ako prvý v niektorom stĺpci, vie ťahať prvý aj v každom ďalšom, až po predposledný, čo znamená, že vyhrá.


Takto máme stratégiu pre hráča, ktorý hru začína. Pri každom stĺpci bude postupovať ako hráč začínajúci v predposlednom stĺpci. Vždy pohne Viktorom smerom hore alebo dole podľa toho, kde je nepárny počet políčok. Tým donúti druhého hráča pohnúť Viktora do ďalšieho stĺpca, a je jedno, či tak urobí hneď alebo až keď sa dostane na vrchný alebo spodný okraj tabuľky (ak sa dostanú na kraj tabuľky, jedným smerom bude mať 0 políčok a druhým 2011. Musí sa pohnúť smerom k 2011 políčkam, ale to mu vyhovuje, pretože je to nepàrny počet). Túto taktiku bude robiť prvý hráč v každom stĺpci a teda druhý hráč vždy bude musieť urobiť ťah doprava. To znamená, že bude musieť vstúpiť do predposledného stĺpca a to už vieme, že vyhrá hráč, ktorý bude potom na ťahu, teda začínajúci hráč.


Zároveň si môžeme všimnúť, že pri tejto stratégii vôbec nezáleží na počte stĺpcov tabuľky. Nevyužívame totiž žiadnu vlastnosť ich počtu, ale iba postupne opakujeme rovnakú taktiku v každom stĺpci tak aby vždy zmenil stĺpec súper. 

Výhernú stratégiu má teda vždy prvý hráč bez ohľadu na to, kde Viktor začínal.