4. Kubo, Mince a Sušička vzorové riešenie

Ešte predtým, než sa začneme hrať, si uvedomme, že nezáleží na poradí kôpok. Je jedno, ktorá kôpka je prvá a ktorá je druhá. Nás zaujímajú len počty mincí na kôpkach.

Na začiatku hry môžu nastať dve situácie. Celkový súčet mincí na oboch kôpkach môže byť párny alebo nepárny. Ak je nepárny, znamená to, že na jednej kôpke je párny počet mincí a na druhej nepárny, lebo akokoľvek rozdelím nepárne číslo na dve čísla, vždy bude jedno z nich párne a jedno nepárne. Keďže ťahmi sa celkový súčet mincí nemení, vždy bude na jednej kôpke párny a na jednej nepárny počet mincí a hrať sa bude donekonečna.

Hra je zaujímavejšia, keď je súčet párny. Na počty mincí sa odteraz budeme pozerať trochu inak. Každý počet mincí \(N\) vieme zapísať ako \(2^x Z\), kde \(Z\) je nepárne číslo. Namiesto každého \(N\) teda budeme uvažovať \(x\), kde \(x\) je najväčšia mocnina \(2\), ktorá delí \(N\). Odteraz sa budeme zaoberať len týmito mocninami (\(x\)-kami) a počty mincí na kôpkach budeme značiť len pomocou nich, pretože v tejto hre sa kôpky s rôznym počtom mincí, ale s rovnakým \(x\) správajú úplne identicky. Aritmetika s takýmito číslami funguje inak, ako s bežnými číslami. Keď takéto číslo \(x\) rozdelím napoly, dostanem \(x-1\). Keď sčítam \(x+y\), kde \((x<y)\), výsledok bude \(x\). Pozrime sa aj podrobne, čo sa pri takomto sčitovaní deje: \[2^xZ_1+2^yZ_2=2^x(2^{y-x}Z_2+Z_1)\] Keďže \(2^{y-x}Z_2+Z_1\) je nepárne číslo, tak \(2^x(2^{y-x}Z_2+Z_1)=2^xZ_3\) je v našom systéme \(x\).

To však platí iba keď \(x<y\). Čo keď \(x=y\)? V tomto prípade výsledok bude buď \(x+1\) alebo \(x+2\), alebo \(x+k\), kde \(k\) je prirodzené číslo. Iba podľa \(x\) a \(y\) sa nedá povedať, ktoré z toho. Napríklad pre bežné čísla \(4+4=8\) dostaneme \(2+2=3\) a pre bežné čísla \(4+12=16\) dostaneme \(2+2=4\). Pre bežné čísla \(124 + 4 = 128\) máme \(2+2=7\). Neskôr si však ukážeme, že to vôbec nevadí a podstatné je iba to, že sčítaním dvoch rovnakých mocnín dostaneme väčší výsledok.

Pozrime sa teraz v kontexte tohto nového zápisu čísel na hru s mincami. Dve kôpky s počtom mincí \(N\) a \(M\) si reprezentujeme usporiadanou dvojicou čísel \((x, y)\), kde \(N=2^xZ_1\); \(M=2^yZ_2\); \(x\leq y\). Hra sa skončí, keď na kôpkach sú čísla \((0,0)\). Vtedy sú obe čísla nepárne, žiadna kôpka sa nedá rozdeliť a hráč na ťahu prehráva. Na začiatku sme si ukázali, že hra \((0, 1)\) sa bude hrať donekonečna. (Dokonca hra \((0, k)\), \(k>0\) sa bude hrať donekonečna.)

Rozoberme si najprv prípady, keď \(x=y\), teda situácie tvaru \((x,x)\). Tu vôbec nezáleží na tom, ktorý hráč rozdelí ktorú kôpku, hra bude postupovať vždy rovnako. Po rozdelení kôpky \(x\) sa z nej stane kôpka \(x-1\) a k druhej kôpke sa pripočíta \(x-1\). Keďže \(x-1<x\), dostaneme kôpky \((x-1,x-1)\). Takto to bude pokračovať až k \((0,0)\), kedy niektorý hráč prehrá. Keďže hra postupuje stále rovnako, kto prehrá závisí jedine od parity \(x\). Pre nepárne \(x\) vyhrá prvý hráč (Kubo) a pre párne druhý hráč (Nina).

Čo však, keď \(x\neq y\)? Keďže platí \(x<y\) a pri "sčítavaní" čísel určuje výsledok to menšie, všetko závisí od \(x\). Ak je \(x\) nepárne, prvý hráč rozdelí kôpku \(x\). Je jedno, aké veľké bolo \(y\), druhý hráč proste dostane situáciu \((x-1, y+(x-1))=(x-1,x-1)\) a prehrá, lebo už nemá na výber. Takýmto spôsobom hráč dokáže situáciu \((x,y)\) premeniť na \((x,x)\), ak mu to vyhovuje.

Ak je \(x\) párne, ten hráč, ktorý rozdelí \(x\), prehrá. Druhý hráč vtedy totiž dostane \((x-1,x-1)\), čo sú dve rovnaké nepárne čísla, a preto vyhrávajúca pozícia. Prvý hráč teda rozdelí \(y\) a nastane situácia \((x+(y-1), y-1)=(x,y-1)\). Druhý hráč je teraz postavený pred rovnakú situáciu ako predtým prvý. Ak by rozdelil \(x\), prehrá. Musí teda rozdeliť \(y-1\), čím sa presunieme k \((x+(y-2),y-2)=(x,y-2)\). Vidíme, že \(y\) sa bude zmenšovať, až kým nedostaneme situáciu \((x, x+1)\). Stále platí, že ten, čo rozdelí \(x\), prehrá, preto hráč na ťahu rozdelí \(x+1\). Posunieme sa do \((x+x, x)\). Tu môžu nastať dva prípady. Prvý prípad nastane, keď \(x+x=x+1\). Vtedy máme situáciu \((x+1, x)\), vymeníme kôpky na \((x, x+1)\) a sme v tej istej pozícii, ale pre iného hráča. Ten nechce prehrať, takže spraví to isté, čo jeho súper a hra bude takto pokračovať donekonečna. Ak zrovna pre naše \(x\) platí \(x+x=x+k\), dostaneme \((x+k, x)\), znova vymeníme kôpky na \((x, x+k)=(x, y')\). Odtiaľto bude priebeh znova rovnaký, \(y'\) sa bude zmenšovať až ku \(x+1\) a celý cyklus sa zopakuje. Pre párne \(x\) teda hra bude trvať donekonečna.

Zhrnutie

Keď si počty mincí na kôpkach preložíme do nášho formátu čísel \((x,y)\), kde \(x \leq y\), platia nasledovné podmienky:

• Ak \(x=y\) a \(x\) je nepárne, vyhrá prvý hráč (Kubo).

• Ak \(x=y\) a \(x\) je párne, vyhrá druhý hráč (Nina).

• Ak \(x\neq y\) a \(x\) je nepárne, vyhrá prvý hráč (Kubo).

• Ak \(x\neq y\) a \(x\) je párne, hra sa nikdy neskončí.