6. príklad - Vzorové riešenie

Na začiatok sa zamyslime nad tým, či vieme nejako donútiť súpera, aby prehral. Každé kladné celé číslo k je deliteľné číslom 1 a číslom k.Ak sú tieto dve čísla rôzne (k \neq 1), tak máme vždy aspoň dve možnosti, ako spraviť náš ťah. Číslo k môže mať aj ďalších deliteľov, no tie nás zatiaľ nezaujímajú. Aby súper prehral, potrebujeme, aby odčítal k. Nemôžeme sa však spoliehať na to, že to spraví len tak sám od seba. Ak bude mať na výber, tak odčíta iné číslo, takže jediný spôsob, ako zaručiť súperovu porážku, je dostať pred neho číslo 1.

Číslo 1 je takzvaná prehrávajúca pozícia, teda hráč z nej nevie vyhrať bez chyby súpera. Naopak, číslo 2 je vyhrávajúca pozícia, lebo odčítaním 2-1 = 1 dostaneme súpera do prehrávajúcej pozície, čím si zaistíme víťazstvo (ak nespravíme chybu). To, ktorý hráč má víťaznú stratégiu pre dané n, záleží od toho, či je n vyhrávajúca alebo prehrávajúca pozícia. V prvom prípade vie začínajúci hráč zariadiť svoje víťazstvo, v opačnom prípade to dokáže druhý hráč.

Teraz by sme sa vedeli pozrieť zaradom na čísla 3, 4, 5, \ldots a zisťovať, či z nich vieme dostať súpera do prehrávajúcej pozície. Ak áno, dané číslo zodpovedá vyhrávajúcej pozícii, ak nie, tak je to pozícia prehrávajúca. Napríklad z čísla 3 vieme buď odčítaním 1 dostať súpera do vyhrávajúcej pozície (2) alebo rovno prehrať odčítaním čísla 3. Takže 3 je prehrávajúca pozícia.

Tento postup nám síce čo-to naznačí pre menšie čísla, no my skrátka nevieme vyskúšať všetky prirodzené čísla. Musíme prísť teda s nejakými všeobecnými pozorovaniami.

Napríklad na začiatku sme si všimli, že v každom ťahu vieme odčítať číslo 1. Ak teda máme prehrávajúcu pozíciu pre nejaké n, tak z čísla n+1 vieme odčítaním 1 dostať súpera do prehrávajúcej pozície.Napríklad n=3 je prehrávajúca pozícia, takže ak sa dostaneme do situácie, že je pred nami číslo 4, tak vieme zabezpečiť, aby súper získal 4 - 1 = 3, čím ho vieme donútiť prehrať. Avšak dokázať, že niečo je prehrávajúca stratégia je ťažšie. Na to musia všetky delitele čísla n viesť do vyhrávajúcej pozície, inak si súper môže vybrať takú cestu, ktorou sa prehre vyhne.

Skúsme sa teda zamyslieť nad tým, ktoré čísla by mohli byť ktoré. Zatiaľ vieme, že 1 a 3 sú prehrávajúca pozície, kým 2 a 4 sú vyhrávajúce.Z toho sa dá odvodiť viacero záverov, no ľahko si vieme vyskúšať ďalšie čísla. To by nás malo presvedčiť, že párne čísla budú vyhrávajúce a nepárne prehrávajúce. Otázkou ostáva, prečo?

Je jasné, že z párneho čísla vieme spraviť nepárne tým, že odčítame číslo 1.Aké máme možnosti pri nepárnom čísle? Keďže nepárne číslo nie je deliteľné 2, tak nie je deliteľné ani násobkami 2. Všetky jeho delitele sú teda nepárne. A keďže odčítaním nepárneho čísla od nepárneho dostaneme párne číslo, tak je jasné, že ľubovoľný ťah ponúkne súperovi párne číslo. Súper odčíta 1 a opäť budeme v rovnakej situácii s nepárnym číslom.

To znamená, že hráč s párnym číslom vie zabezpečiť, aby pred jeho nasledujúcim ťahom opäť dostal párne číslo (alebo to súper "vzdá" a rovno skočí na 0). Postupne budú čísla menšie a menšie, až hráč dostane číslo 2, o ktorom už vieme, že je víťazná pozícia.

Odpoveď: Ak je n párne, tak vyhrá začínajúci hráč. Ak je n nepárne, tak vyhrá druhý hráč.