i
i
“444-Rojko-NIM” — 2010/5/26 — 7:51 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 7 (1979/1980)
Številka 4
Strani 209–213
Roman Rojko:
IGRA NIM
Ključne besede: matematika, rekreacijska matematika,
matematične igre, NIM.
Elektronska verzija: http://www.presek.si/7/444-Rojko-NIM.pdf
c© 1980 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
MATEMATIKA___I@I
IGRA NIM
~re davan je na 17. seminarju DMF A 1980 - Zanim i va matemat i ka)
1. UVOD
Ime i gr e NI M verj etno i z vi r a i z ne mškega ve le ln ika "n i mm", kar
pomeni "vzemi" , Obrnimo za šalo besedo NIM na glavo, pa dobimo
besedo WIN, kar v a ng leš čini pomeni "z ma gati",
NIM je v resnici skupno i me za igre, v katerih dva igra l ca iz-
menično pob irata kam ne z enega a li več kupov. Kdor naredi zad -
njo možno potezo, je zmagovalec . Med seboj s e te igre ločijo
po številu kupov in kamnov na začetku igre in po pravilu, ki
predpisuje vel ikost vsakega vzetka . Vsa ka poteza mor a seveda
spremenit i cel otno števi lo kamnov v ig ri i n mora tako vzet i
najmanj en kam e n .
Za vse te igr e velja, da je že na začetku igr e znano, kateri
od obe h i gr al c ev l a hko za nesl j i vo zmaga, ne da bi se mu mogel
pri tem nasprotnik upirati. Posl edica tega pa je, da igra ni
več zan imiva. Tudi mi se bomo ukv a r j a l i z njo z en im samim na -
menom, raziskati namreč že limo ta zanes ljiv i nač in (strategijo)
zmagovanja v ig r i.
2 . NIM Z ENIM KUPOM
Defini rajmo zda j i gro z i me nom Nim (M ) .
Igralca imata pred seboj kup z N kamni, vzetki pa so l a h-
ko najman j en i n največ M kamnov naenkrat . Dobitnik zad -
njega kamna je seveda zmagovalec.
Ni težko uganit i, da traja najdal jša igra N/ 2 potez za vsake
209
ga i gr al ca . Kadar je N ~ M , pa igra sp loh n i za n imiva, saj
bo pr vi zmaga l v prvi potez i, s ka t e r o bo vze l vse kamne.
NaZog a 1 : S prijateljem poskusi i gr a t i i gr o Nim (M ). Pred tem
se dogovorita, kol ikš na na j bosta M in N ( recimo M = 4, N = 15 ).
Označ i mo z (x) kup, v katerem je X kamnov. Za po ljuben kup
bomo defin ira li ce loštevi lčno vrednost p(x ) , ki j i bomo rek -
l i kar VR EDNO ST POZ ICIJ E i gr e . Do nj e pr ide mo t a kole :
a) Prazen kup i ma vrednost nič, prO) = O
b) Naj bodo (Xl)' (X2), •. • (Xy» vs i možni kupi, do ka -
teri h la hko pridemo s prav i lnim jemanjem s kupa (x),
tedaj je
p(X) = najmanJse nenegat ivno ce lo števi lo, ki je raz
l i čn o od vse h vrednost i
P(X
i
) , i = 1,2, ... , y>
Pri mer
Vzemi mo i gr o Ni m(2), ki ima na začetk u 4 kamne. Vsak vzetek je
t or e j l ah ko 1 al i 2 kamna . Da bomo l a ž j e računa li vrednost i PQ
zic ije, s i najp rej nar iš imo vse možne poteze v igr i :
o OO 000 0000
(0) - ..--- ( 1) - ..~-- ( 2 )-..- - - (3) -.~-- (4)
Očitno so vrednost i poz ic ije: p r O)
P ( 3 ) = O, p ( 4 ) = 1.
O, P( 1 ) 1, p ( 2 ) 2,
NaZoga 2 : ! z r a č un a j še nekatere vred nost i pozicij (za kupe s
5,6, . .. ,20 kamni) .
210
P(X ) = O, j e lah ko kup prazen i n 'i gr a k o n č a n a .
ni prazen, pa katerako li pra v i lna pot e za povzr9
je p (x - vze t e k) > O .
ci ji
b) če je
če kup
č i, da
Sedaj s i og lejmo dvoj e l a s t nos ti vr ed nos t i pozicije i gr e :
a) če je p (x ) > O , pomeni , da kup (x) ni prazen, igra -
lec, ki je na vrsti, pa lahko med možnim i potez ami i z-
bere tako, da bo z njo dosege l p (X- vze t e k) = O . če
na mre č t a ka poteza ne bi obsta ja la, bi bi lo po de fini -
p ( X ) = O •
Pri P(x ) = O je pozi cija I ZG UBLJ ENA , p (x ) > O pa pomeni
DOBLJ ENa poz i ci j o , kar se nanaša na i gr al ca , ki je na vrsti .
Tor e j zmeraj obstaja poteza, ki spremeni dob ljeno poz icijo v
izgubljeno, vsa ka poteza pa spreme ni izgubljen o pozi ci jo v d o~
ljeno. Tako smo pri š li do osno vne l as t nos t i igre Nim : č e je
v zače tku i gr e P(N) > O , l a hko prvi zmaga tako, da sp re minja
dobljeno pozicijo v izgubljeno. Drugi mu pr i tem odgovar ja ta-
ko, da i zgubl j e no pozi cijo spreminja v dob ljeno, dokler se kup
ne izprazni.
če j e na zače tk u i gr e P(N) = O , prvi n ima možnost i za zmago,
raz en če se drugi zmot i. Zat o bo prvi vzel samo en kam en , s aj
pomeni večji kup t ud i večjo možnos t za napa ko. Drugi se veda
upora blja isto strategij o, kot bi jo prv i . Strategija ni odv i -
sna od vrstnega reda i gr a l ce v , ampak samo od števi la kamnov v
kupu in pravi la za poteze.
Pr i mer
Og lej mo s i potek že omenj ene igre Ni m( 2 ) S št irim i kamn i na
začetku. Pr v i mora vz eti en kame n , tako pust i tri kamne , ki jih
drugi zmanjša na 2 ali 1, oboje pa prvi v naslednji potezi vz~
me i n zmaga .
Naloga 3 : Ugotovi vse izg ubl jene poz ic ije i z na loge 2 .
Og lejmo s i še en način računanja vzetka pri Nim (M)
Vsa ko kr a t j e na j bo lje pust it i v kupu mnogokr at ni k od M+ l
kamnov, se prav i
211
vze t e k = X mod (M+ l)
kjer j e X ve l i kost kupa, c e l a des na s tran pa os ta nek pr i
de lj enju X z M+ 1. Ta koj vi d imo , da da je t a f ormul a na j ve~
j i vze tek M kamnov. Kadar je poz ici ja izgubljena, pa je
rez ul t a t form ule enak nič, kar pa n i pr a v i len vze t e k . V
zadn j em primeru je najb olj ši vzetek en kam en, formul o pa
bomo poprav i li:
vzete k = max ( 1 , X mod (M+ l ) )
Zap iš imo še en kra t vred nost i poz ic i je igr e Nim (M )
0,1 ,2 , . .. , M , 0 , 1 ,2 , .. , M , O, 1 ,2 , . .. , M, O, 1 ,2 , . . .
Vidi mo , da j e vr edn os t poz ic i je e naka veli kos ti vze t ka pri po-
l j ub nem ku pu , razen pri vr ednost i O. To ve l j a nas pl oh s amo za
i gr o Nim (M ) . Pri d rug a čn ih pr av i l i h s e vzet ki drug a č e računa jo.
Naloga 4 Kakše n j e na j bolj ši vzet e k pri i gr ah :
a) N 100 , M 15
b ) N 20 M 4
c ) N 2 1 M 4
Seda j s i bom o ogleda l i vr ed nos ti pozi cije ig er z d ruga čnim i
pr av i l i za d ol o č an j e vz et kov:
a) vze t e k je 1i ho št e vi lo
O, 1 , O, 1 , O, 1, O, 1, O, 1 , O, 1,
b) vzete k j e so do š te v i lo
O, O, 1 , 1 , 2 , 2 , 3 , 3 , 4 , 4 , 5, 5 ,
c ) vzete k je n ajv e č pol ovi ca ku pa +
O, 1, 2 , O, 3 , 1, 4, 2, 5, O, . ..
d ) vze t e k ni v e č ko t po lo vica kupa
O, O, 1, O, 2 , 1 , 3 , O, 4 , 2 ,
e) vzet ek j e praštevilo
O, O, 1 , 1, 2 , 2 , 3, 3, 4 , O, O, .. .
Nal oga 5 : R azi š či vr edn osti P OZ1 C1J za pr avil o "vz e t ek je
kub " in ve likost i ku pov : O, 1 , 2 , .. . , 30 ka mnov.
2 12
3 .  O B R N J E N I  MIH 
Obrnjenl N f m  ima f s t a  prar i la  ko t  navadni .  l a  zmagovalca do lo -  
Eamo drugate: 
zmag~valec fe igralec, kf  ne more n a r e d i t j  poteze .  
V Btnn(M) t o  pomeni, d a  i z g u b l  t i s t f  fgralec, ki mora v r e t i  rnd 
n j i  kamen. Tako se seveda tud i  tmagovalna strategija rahlo  
spremeni ,  P r v i  se bo t r u d i l ,  da bo na konru p u s t i l  natanEno en 
kamen, ki ga bo drugi  taka moral v r e t i .  
Obrnjeni I P ~ ~ ( M )  igrbsno takole:  zaEetni kup s i  mislfmo zmanjSan 
z a  en kaman, nato pa fgramo k o t  p r e j .  Tako lahko pridemo do 
predzsdnjega kamna. Kaka j e  5 paz ic i jami?  RaEunenje poteka t a -  
ko k o t  p r e j ,  l e  zaEetek j e  d r u g a t e n ,  namreE P ( 0 )  = 1 . Ysak 
v z e t e k  pa izratunamo takole:  
vze tek  = ( B - 1 )  mod (&!+I) 
Batogo 8: Kako lahko o b r n j e n f  N i m  s s p l o S n e j b i a i  p r a v i l i  jema- 
nja prevedamo na navadnega?