4. Kika, Mince, Šarlatán (κ ≤ 4) vzorové riešenie

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.