Zoznam úloh

4. Kika, Mince, Šarlatán (κ ≤ 4)

Zadanie

Kika narazila na letisku na šarlatána. Ten mal na stole dve kôpky po $n$ mincí. Kika sa rozhodla, že šarlatána niečo naučí, a preto sa s ním pustila do nasledujúcej hry.

Kika a šarlatán hrajú proti sebe hru. Na stole majú položené dve kôpky, na každej je $n$ mincí. Kika začína a následne sa so šarlatánom striedajú v ťahoch. Hráč na ťahu musí vykonať práve jednu z nasledujúcich akcií:

  • vyberie si jednu kôpku a zoberie z nej ľubovoľný kladný celočíselný počet mincí,

  • zoberie po jednej minci z oboch kôpok (ak je na oboch kôpkach aspoň $1$ minca).

Hráč, ktorý zoberie svojím ťahom zo stola poslednú mincu, vyhráva. Zistite v závislosti od kladného celého čísla $n$, ktorý hráč má víťaznú stratégiu.[^1]


  1. Hráč má víťaznú stratégiu, ak si vie svojimi ťahmi zaručiť výhru bez ohľadu na to, ako hrá jeho súper.

Najprv sa zamyslíme, ako to v takomto type hier funguje. V týchto hrách sa hráči striedajú v ťahoch, neexistuje v nich prvok náhody, majú konečný počet pozícií a nemôže nastať remíza. Takéto hry sú známe aj ako kombinatorické hry.

Keďže hra má konečný počet pozícií (pre ľubovoľné $n$), tak to znamená, že pre každú pozíciu musí byť jednoznačne určené, či je prehrávajúca $(P)$, alebo vyhrávajúca $(V)$. Zamyslime sa teraz, čo to znamená, ak je pozícia $V$, alebo $P$.

  1. Ak je pozícia $V$, tak to znamená, že vieme urobiť aspoň jeden ťah, ktorým súpera dostaneme do $P$ pozície.

  2. Ak je pozícia $P$, tak to znamená, že ľubovoľným z našich ťahov dostaneme súpera do $V$ pozície.

Vráťme sa späť k našej úlohe. Na začiatok je pre ľubovoľnú pozíciu ťažké rozhodnúť, či je $V$, alebo $P$. Preto si túto hru trochu rozanalyzujeme pre malé počty mincí. Tým si vieme urobiť základný prehľad o hre a dopracovať sa k nejakým hypotézam. Ešte si však uvedomme, že nakoľko vieme brať z ľubovoľnej kôpky, nezáleží nám na poradí kôpok.

Vieme, že pozícia $(0;0)$ je $P$, lebo hráč, ktorý by mal byť na ťahu v tejto pozícií už vlastne prehral. Pozície $(1;1), (1;0), (2;0), (3;0), \dots{}, (n;0)$ sú teda $V$, lebo z nich svojím ťahom dokážeme dostať súpera do $P$ pozície $(0;0)$. Pozícia $(2;1)$ je už ale prehrávajúca, lebo každý z našich ťahov dovedie súpera do $V$ pozície. Takýmto postupom ďalej dostaneme:

$\textbf{(0;0) - P}, (1;1)-V, (1;0)-V, (2;0)-V, (3;0)-V, \dots{}, (n;0)-V \
\textbf{(2;1) - P}, (3;1)-V, (4;1)-V, (5;1)-V,\dots{}, (n;1)-V \ \textbf{(1;2) - P}, (2;2)-V, (3;2)-V, (4;2)-V, \dots{}, (n;2)-V \ \textbf{(3;3) - P}, (4;3)-V, (5;3)-V, (6;3)-V, \dots{}, (n;3)-V \\ $

Skôr či neskôr si asi všimneme, že pozície tvaru $(3k;3k)$ a $(3k+2;3k+1)$ sú $P$. Hypotézu konečne máme, stačí to už len dokázať.

Pozície tvaru $(3k;3k)$ a $(3k+2;3k+1)$ si označme ako pozície typu $A$ a všetky ostatné pozície si označme ako pozície typu $B$. Rozmyslite si, že aby naozaj platilo, že pozície $A$ sú prehrávajúce a pozície $B$ sú vyhrávajúce stačí, aby platili tieto tri predpoklady:

  1. Konečná pozícia $(0;0)$ musí byť pozíciou typu $A$.

  2. Z ľubovoľnej pozície typu $B$ vieme dostať súpera do pozície typu $A$.

  3. Z ľubovoľnej pozície typu $A$ vieme súpera dostať iba do pozícií typu $B$.

Pre predpoklad $1$ je zrejmé, že platí. Pre predpoklad $2$ si stačí premyslieť všetky možnosti. V prípade $(3x,y)$, kde $y>3x$, stačí vytvoriť dve kôpky po $3x$ mincí. Ak je $y<3x$, tak je buď tvaru $3z+1$ alebo $3z+2$. Ak je tvaru $3z+1$, tak z druhej kôpky odoberieme toľko mincí aby na nej zostalo $3z+2$ mincí. Podobne ak je tvaru $3z+2$. Vtedy odoberieme z druhej kôpky toľko mincí aby na nej zostalo $3z+1$ mincí. Už nám zostáva len možnosť, že máme $(3x+1, 3y+2)$ mincí, pričom $x \neq y$. V tom prípade zoberieme z niektorej kôpky toľko mincí, aby sme dostali možnosť $(3k+1, 3k+2)$, pričom $k$ je menšie z dvojice $x,y$. Tým máme dokázané, že z týchto pozícií vieme dostať súpera do pozície typu $A$.

Pre predpoklad $3$ vidíme, že z pozície $(3k;3k)$, ani z pozície $(3k+2;3k+1)$ naozaj nevieme dostať súpera do pozícií typu A.

\ Keďže všetky tri predpoklady naozaj platia, pozície tvaru $(3k;3k)$ a $(3k+~2;3k+~1)$ sú naozaj prehrávajúce a všetky ostatné sú vyhrávajúce. Čiže pre $n=3k$ má víťaznú stratégiu šarlatán a pre $n=3k+1$ a $n=3k+2$ má víťaznú stratégiu Kika.

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty