9. príklad - Vzorové riešenie
Zadanie
Majme 7 kôpok drahokamov s 2014 drahokamami a jednu kôpku s 2008 drahokamami. Dvaja hráči sa striedajú v ťahoch, pričom v každom ťahu hráč z každej kôpky odstráni iný počet drahokamov od 1 po 8. Hráč, ktorý nemá ťah, prehráva. Určte, ktorý hráč má výhernú stratégiu.
Vzorové riešenie
Pri objavovaní výherných stratégií je dobré si pre začiatok zmenšiť počty. Skúsme si to teda na začiatok s jednou kôpkou. Ak sa na ťahu hráča A bude v kôpke nachádzať 1 až 8 drahokamov, vie vždy odobrať tak, aby po jeho ťahu ostalo v kôpke 0. To znamená, že hráč B už nemôže spraviť ťah a teda prehráva.
Z tohto vieme povedať, že hráč ktorý ma na začiatku svojho ťahu pred sebou 1 až 8 drahokamov, má víťaznú stratégiu. Hráči sa teda budú snažiť dosiahnuť taký stav, pri ktorom nezáležiac na tom, koľko drahokamov odoberie ich súper, na ich ťahu budú mať pred sebou 1 až 8 drahokamov.
Najmenší možný počet odobratia drahokamov je 1. Takže stačí aby bolo v kôpke pred ťahom hráča B len o jeden drahokam viac ako 8 a hráč A bude mať pred svojim ťahom v kôpke najviac 8 drahokamov.
Najväčší možný počet odobratia drahokamov je 8. Takže ak pred ťahom hráča B bude v kôpke 9 drahokamov, nemôže ich odobrať všetky a po jeho ťahu v kôpke ostane najmenej 1 drahokam. Z tohto vieme, že hráč, ktorý má pred svojim ťahom v kôpke 9 drahokamov prehráva.
Takto sa môžeme v počtoch drahokamov v kôpke posúvať vyššie. Ak je v kôpke 10 až 17 drahokamov, hráč A si vždy vie nájsť taký počet na odobratie, aby jeho súperovi ostalo 9. Ďalšia prehrávacia pozícia je potom 18 drahokamov, lebo po odobratí ľubovoľného počtu ostane na kôpke 10 až 17 drahokamov
Teraz si skúsme nejako zovšeobecniť víťaznú stratégiu:
Vždy keď sa na ťahu hráča A nachádza v kôpke počet drahokamov deliteľný 9, po odobratí ľubovoľného počtu drahokamov vie jeho súper odobrať toľko drahokamov, aby súčet odobraných drahokamov v týchto dvoch ťahoch bol 9. Takto sa striedajú až kým hráč B zanechá po svojom ťahu na kôpke 0 drahokamov a vtedy hráč A už nemá ťah.
Takže ak je na začiatku na kôpke počet drahokamov deliteľný deviatkou, začínajúci hráč A prehráva.
Ak je na začiatku ale na kôpke počet drahokamov nedeliteľný deviatkou, začínajúci hráč A vie odobrať toľko drahokamov, aby po jeho ťahu ostávajúce drahokamy už boli deliteľné deviatkou, čiže hráč B prehráva.
Teraz sa pozrime na našich 8 kôpok:
Hráči sa budú snažiť na kôpke s najmenším počtom drahokamov po sebe zanechať počet deliteľný deviatkou. Z ostatných kôpok potom vedia vždy drahokamy odobrať tak, aby v nich ostalo viac, ako v danej najmenšej kôpke, takže bude prvá, z ktorej budú odobrané všetky drahokamy. Presne táto kôpka určí, kto vyhrá.
Dokáže to dosiahnuť začínajúci hráč A? Najbližšie počty deliteľné deviatkou sú 1998 a 2007. Na 1998 drahokamov v hocijakej kôpke sa hráč A jedným ťahom dostať nedokáže, takže mu ostáva skúsiť sa dostať na 2007. To vie dosiahnuť buď odobratím jedného drahokamu z kôpky s 2008 drahokamami, alebo odobratím 7 drahokamov z kôpky s 2014 drahokamami. Avšak toto nebudú kôpky s najmenším počtom drahokamov, keďže musel odobrať drahokamy aj z ostatných kôpok.
Ak hráč A odobral 1 drahokam z kôpky s 2008 drahokamami, musel z 2014-drahokamových kôpok odobrať všetky čísla okrem 7. Počet drahokamov v kôpkach bude: 2006, 2007, 2007, 2008,2009, 2010, 2011,2012. Hráč B vie teraz na svojom ťahu dosiahnuť aby kôpka s najmenším počtom drahokamov ich mala 1998 odobratím ôsmich drahokamov z 2006-drahokamovej kôpky. Teraz mu stačí na túto kôpku použiť už vyššie objavenú víťaznú stratégiu pre jednu kôpku (odoberie toľko, aby súčet odobratých drahokamov hráča A a jeho bol 9) a vyhrá
V skutočnosti nezáleží ako na začiatku hráč A odoberie kamienky, vždy bude aspoň jedna kôpka s počtom drahokamov menším ako 2007 na ktorú vie hráč B vyhrať.
Odpoveď: Víťaznú stratégiu má hráč B (hráč, ktorý nezačína)