8. Konečnú Misku Schlamstnem! vzorové riešenie

Stav hry medzi ťahmi je úplne popísateľný počtom misiek na stole a hráčom na ťahu. Teda pozícia, do ktorej hráč svojim ťahom hru dostáva, je popísaná iba jedným nezáporným celým číslom – počtom misiek. Misiek vždy, keď je na stole aspoň jedna, ubúda, takže hra sa musí skončiť za nanajvýš toľko ťahov, koľko je na začiatku misiek, čo je konečne mnoho.

Vďaka tomu môžeme pozície rozdeliť na vyhrávajúce a prehrávajúce. Vyhrávajúca pozícia je taká, že keď do nej potiahneme, tak vyhrávajúca stratégia ostáva na našej strane – vieme zaručene vyhrať. Nech \(0\) je vyhrávajúca pozícia. Ak z pozície existuje ťah do vyhrávajúcej pozície, je prehrávajúca, inak je vyhrávajúca. Takéto rozdelenie je dobre definované, pretože môžeme pozície prechádzať podľa počtu misiek vzostupne.

Najprv si všimnime, že neexistujú dve vyhrávajúce pozície zhodujúce sa vo zvyšku po delení počtu misiek číslom \(n\). Ak by existovali, z tej s vyšším počtom misiek by existoval ťah do tej s nižším (pretože rozdiel medzi ich počtami je násobkom \(n\)), čo je spor s neexistenciou ťahu z vyhrávajúcej pozície do vyhrávajúcej.

Predpokladajme, že počiatočná pozícia je vyhrávajúca. Nech počiatočný počet misiek na stole je \(kn+z\), kde \(k\) je celé číslo a \(z\in\{1,2,\dots,n\}\). Keďže \(kn+z>n^2\) a \(n\geq z\), tak musí byť \(k>n-1\). Pozrime sa na \(n\) pozícií s počtami misiek \(k'n+z\) pre \(k'\in\{0,1,\dots,n-1\}\). Tieto počty sú nižšie než počiatočný počet (\(k'\leq n-1<k\)) o násobky \(n\). To znamená, že do všetkých týchto pozícií existujú ťahy z počiatočnej vyhrávajúcej, a teda sú prehrávajúce.

Ťah tretieho typu z pozície s \(k'n+z\) miskami vedie do prehrávajúcej pozície, lebo všetky pozície s menej miskami s tým istým zvyškom modulo \(n\) sú prehrávajúce. Odtiaľ ide o ťah prvého alebo druhého typu. Ťah druhého typu vždy znižuje počet misiek o menej než \(n\). Ťah prvého typu tiež, ak \(n\not=1\). Pre \(n=1\) však ťah o \(m=1\) je zároveň ťahom o násobok \(n\), čiže vedie do prehrávajúcej pozície. To značí, že každý ťah z \(k'n+z\) vedie do prehrávajúcej pozície alebo znižuje počet misiek o menej než \(n\), čím vedie do pozície s počtom misiek vyšším než \((k'-1)n+z\).

Každá pozícia \(k'n+z\) je prehrávajúca, odkiaľ z nej musí jestvovať ťah do vyhrávajúcej pozície. V zmysle predchádzajúceho odseku táto vyhrávajúca pozícia musí mať viac než \((k'-1)n+z\) misiek, takže pre každé \(k'\) je medzi \((k'-1)n+z\) a \(k'n+z\) vyhrávajúca pozícia. Tieto rozsahy sa neprekrývajú, nuž pre \(n\) rôznych \(k'\) musí ísť o \(n\) rôznych vyhrávajúcich pozícií. Ani jedna z nich nedáva zvyšok \(z\) po delení \(n\), pretože jediná vyhrávajúca pozícia s týmto zvyškom má \(kn+z\) misiek. Z Dirichletovho princípu potom medzi \(n-1\) ostatnými zvyškami aspoň jeden obsahuje viac než jednu z našich \(n\) vyhrávajúcich pozícií, čo je v spore s tým, čo sme si už dokázali.

Náš predpoklad musí byť nepravdivý a počiatočná pozícia je prehrávajúca. Odtiaľ už dostávame vyhrávajúcu stratégiu pre začínajúceho Kubka: Vždy potiahne do vyhrávajúcej pozície. Z takej je Jótaró nútený ťahať do prehrávajúcej pozície. Napokon z takej pozície vždy jestvuje ťah do vyhrávajúcej pozície, čo znamená, že Kubkovi sa ťahy neminú a neprehrá. Po konečnom počte ťahov sa však hra musí skončiť. Vtedy Kubko vyhrá.