Matematické Fórum

↑ Brano: Spíš mi jde o ten vzorec. Algoritmus je jednoduchý - pracuje rekurentně. Definuješ si nějaký stavový prostor - ten bude dvojdimenzionální (veškerá informace o aktuálním stavu hry je shrnuta ve dvou číslech - počet kamenů na hromádce a poslední zahraný tah). Ve stavovém prostoru si definuješ nějaké výchozí prohrávající pozice. A pak řekneš, že vyhrávající je každá taková, z níž existuje aspoň jeden tah, jímž se dostaneš do prohrávající pozice. Prohrávající pozice je pak taková, která není vyhrávající (tj. taková, z níž veškeré přípustné tahy vedou pouze do vyhrávajících pozic). Rekurence je pak vedená skrze počet kamenů na hromádce - každý přípustný tah totiž nutně počet kamenů sníží.

↑ Anonymystik:

A co kdyz zacinajici hrac odebere N kamenu? Druhy hrac automaticky prohral, protoze uz nezbyl zadny kamen. Nebo to ma jeste nejake jine omezeni?

Náhodou jsem narazil na toto téma. Existují pro nějaké k výherní počty kamenů, ze kterých by se dalo něco vykoukat?

Netriviální případy jsou ty, kdy k je liché. Taky si myslím že pokud obecně je [mathjax]k+1=2^m.(2c+1)[/mathjax] pro m sudé, pak je to taky snadné - pokud soupeř zvolí (k+1)/2, já zvolím (k+1)/4, atd.... A snahou je se po svém tahu dostat na násobek k+1.

A pro m liché mi to připadá, že proherní pozice budou právě ty (myšleno na začátku hry), u kterých je počet kamenů o 1 větší než nějaký násobek k+1.

Hra může mít nejvýše k tahů.
Myslím, že když je N větší než součet všech čísel od 1 do k,  záleží jenom na tom, jestli je k liché nebo sudé. Pro liché k vyhraje ten, kdo začal, pro sudé k prohraje. Bez ohledu na to, kdo jak tahá.

↑ osman:
Samozřejmě, to se dá intuitivně čekat.

↑ MichalAld:
Nemusí se na to jít jen zvýšením o jedničku - a jak jsem psal, sudká k jsou jasná....

↑ osman:
To ne, není povoleno odebrat tolik kamenů, kolik odebral soupeř ve svém minulém tahu - a to chápu tak že "v bezprostředně předcházejícím" a ne "v některém z minulých". Kdyby to bylo v libovolném z předcházejících, tak by zadavatel napsal "v některém z minulých" a ne "v minulém" - což právě evokuje jeden konkrétní tah, ten poslední.

A rovněž je to zřejmé také z poznámky zadavatele #3, kde hovoří o stavovém prostoru.

↑ osman:
... a ta by byla ještě o dost těžší....