Kategórie:
5
6
7
8
9

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

Opravovali: Johnny, mati

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)