Posted By: Xyster (X! [({})]) on 'CZscience'
Title:     Re: varianta NIMu
Date:      Sat Apr  1 15:03:53 2000

> Existuje nejaka zduvodnitelna vyherni strategie?
Tahle nebo podobna uloha se resila PSCG(Problem Solving and Computer Games) 
(asi trosku obecnejsi zadani - libovolny pocet v radku a radku)

(Charles Bouton. Harward University)

(ted nevim, kdo v tomto pridade vyhrava ... a nechce se mi studovat celou 
kapitolu)  

Udela se binarni xor poctu sirek v jednotlivych hromadkach a(n) -> b. Pozice 
je bezpecna(safe), pokud je vysledek 0. 
Pokud pozice neni bezpecna, existuje legalni tah, jak bezpecnou pozici 
dosahnout. 
 
Spravny tak se ziska :
udela se c=a(n) xor b, pokud je c<a(n), tak po odebrani a(n)-c sirek z 
hromahky n dosahneme bezpecnou pozici(v ne-bezpecne pozici je vzdy alespon 
jeden takovy tah)

(pro 1, 2, 3, 4, 5 je b=1, takze pozice neni bezpecna. Vyhrava zacianjici 
hrac. Mozne tahy by mely byt: (1)-1, (3)-1, (5)-1 ... )

(v pripade bezpecne pozice je nejlepsi sebrat jednu sirku z nejvetsi hromadky 
a doufat, ze to ten druhej zvore)

(v pripade modifikace zadani, kdy je mozne sebrat max N sirek se pouzije 
stejna strategie, pouze aritmetika %N. Opet existuje alespon jeden legalni 
tah, jak dosahnou bezpecnou pozici (dukaz E.H.Moore) ) 

V pripade zajmu mam poznamky z prednasek .... 

(Doufam, ze sem to spravne pochopil a prelozil)
Xyster

42

Search the boards