1+1=2

Teoria jocurilor: numerele

mate

Sprague GrundyCosmin-Silvestru NegrueriDomeniu relativ nou i nc necercetat n adncime, teoria jocurilor este o ramur a matematicii n care de multe ori primeaz inventivitatea i nu cunotinele. Tocmai din acest motiv, n cadrul acestui articol vom introduce cteva noiuni teoretice care ne vor ajuta n rezolvarea uner probleme din teoria jocurilor. Ingeniozitatea celor pasionai poate fi testat prin introducerea unor probleme de teoria jocurilor la concursurile de matematic i informatic. Deoarece n Romnia, teoria jocurilor nu este studiat n coli, problemele din acest domeniu pot pune n dificultate concurenii.o ooo ooooo oooooo

atunci vom avea:1 = (0001)2 3 = (0011)2 5 = (0101)2 7 = (0111)2

NIMPentru nceput ne vom familiariza cu jocul clasic NIM: Se consider n grmezi de pietre. Doi juctori, vor ridica (alternativ) oricte pietre dintr-o singur grmad. Ctigtorul este cel care ia ultima piatr. Pentru cazul trivial n care numrul de grmezi este egal cu 1, primul jucator are evident strategie de ctig, el putnd lua toate pietrele din grmad. Dac numrul de grmezi este egal cu 2, primul juctor are strategie de ctig atunci cnd numrul de pietre din prima grmad este diferit de numrul de pietre din cea dea doua, strategia lui fiind cea de a aduce tot timpul grmada mai mare la numrul de pietre al grmezii mai mici, i cum jocul este finit, nseamn c primul juctor o s aduc jocul n starea (0, 0). Dac numrul de grmezi este mai mare dect doi strategia se complic i nu se mai observ cu "ochiul liber". Strile ctigtoare pentru mai multe grmezi sunt acele stri pentru care suma XOR a numerelor de pietre din grmezi este diferit de 0, restul strilor fiind de pierdere. De exemplu, dac avem o gramad cu o piatr, o gramad cu trei pietre, o gramad cu cinci pietre i o gramad cu apte pietre:

efectund XOR (operatorul ^ n C/C++) ntre reprezentrile binare ale numerelor obinem 0 = (0000)2. Conform propoziiei de mai sus aceast stare este de pierdere. S demonstrm cele afirmate. Dintr-o poziie cu suma XOR egal cu 0, pentru orice mutare ajungem evident la o poziie cu suma XOR diferit de 0, pentru c lund dintr-o grmad un numr x de pietre, n suma XOR corespunztoare noii stri bitul cel mai semnificativ al lui x va avea valoarea 1. Mai rmne de demonstrat c din orice poziie cu suma XOR diferit de 0 putem trece printr-o mutare convenabil ntr-o poziie cu suma XOR egal cu 0. Cutm o grmad care are un numr de pietre mai mare sau egal cu cea mai mare putere a lui 2 care apare n suma XOR. Fie x valoarea sumei XOR a tuturor grmezilor i y numrul de pietre din grmada gsit mai devreme. O mutare "ctigtoare" este extragerea din grmada gsit care are y pietre a y - (x XOR y) pietre (x XOR y este mai mic

19

GInfo nr. 14/5 - mai 2004

dect y pentru c se anuleaz biii cei mai semnificativi ai lui y i x). Atunci noua sum XOR va fi egal cu 0. De exemplu: 4 ^ 8 ^ 17 = (00100)2 ^ (01000)2 ^(10001)2 = (11101)2 = 29

Mutarea ctigtoare const n a lua din cea de-a treia gramad un num de pietre egal cu: 17 - (17 ^ 29) = 17 - 17 ^ 29 = 5 = (00101)2.

Problema 3 (El Judge MIPT online programming contest Nim Game Give Away!) Se consider n grmezi de pietre, juctorii mut alternativ, fiecare juctor extrgnd oricte pietre dintr-o singur grmad. Cel care ia ultima piatr pierde jocul. Strategia acestui joc este similar cu cea aplicat n jocul NIM cu cteva mici diferene. Juctorul care are strategie de ctig n poziia curent n cadrul jocului NIM face aceeai mutare pe care ar face-o n cazul jocului NIM, exceptnd cazul n care aceast mutare las doar grmezi cu o singur piatr i numrul acestor grmezi este par. n aceast situaie, dac ar trebui s ia x pietre, juctorul poate lua x - 1 pietre din grmada actual, pentru ca numrul de grmezi s fie impar i el s fac ultima mutare.

mate

Dup acest pas grmezile vor avea 4, 8, 12 pietre. Ne aflm astfel ntr-o stare cu suma XOR egal cu 0. Exemplificm n continuare cteva probleme n care se folosete strategia de la jocul NIM. Problema 1 Pe o tabl de ah, care are n m csue, sunt plasai pe prima linie n pioni albi i pe ultima linie n pioni negri. Fiecare dintre cei doi juctori poate muta un singur pion, care i aparine, un numr strict pozitiv de csue n sus sau n jos, astfel nct s nu ajung vreun pion alb s fie mai jos dect pionul negru de pe aceeai coloan. Pierde juctorul care nu mai poate muta. Aceast problem este o deghizare a jocului NIM, numrul de ptrele libere ntre pionul alb i pionul negru de pe coloana i putnd fi considerat numrul de pietre din grmada i. Singura diferen este c se pot aduga pietre la grmad (existnd posibilitatea mutrii napoi). Aceast problem se rezolv uor, juctorul care are strategie de ctig putnd evita asemenea mutri. O astfel de mutare poate fi util numai pentru juctorul care este ntro poziie de pierdere. Cnd jucatorul care nu are strategie de ctig mut napoi x casue, cellalt juctor va muta pionul propriu de pe aceeai coloan cu x csue n fa, astfel ajungndu-se la aceeai stare cu cea existent cu dou mutri anterior (considernd diferena poziiilor). Problema 2 Aceast problem a fost propus spre rezolvare participanilor la barajul pentru lrgirea lotului naional din 1997. Pe o linie sunt plasate la coordonate ntregi 2 n piese roii i albastre. Fiecare pies roie poate fi mutat n dreapta oricte poziii astfel nct s nu sar peste o pies albastr, iar piesele albastre pot fi mutate oricte poziii la stnga astfel nct s nu depeasc vreo pies roie. Piesele vor alterna: rou, albastru, rou, albastru etc. Pierde juctorul care nu mai poate muta. Aceast problem poate fi, de asemenea, redus la jocul NIM. Diferenele poziiilor perechilor de piese roii i albastre consecutive constituie numrul de pietre al grmezilor din jocul NIM.

Numerele Sprague GrundyJocurile care prezint interes pentru juctori sunt acelea care necesit examinarea unui numr foarte mare de stri pentru determinarea strategiei de ctig, deoarece n caz contrar ctigtorul s-ar cunoate chiar de la nceput. Spre deosebire de acetia, matematicienii sau informaticienii sunt interesai de determinarea unor strategii pentru astfel de jocuri. Toate jocurile impariale cu doi juctori cu informaie total pot fi reduse la jocul NIM care se joac cu nite grmezi virtuale, n care mutrile posibile sunt extragerea orictor pietre dintr-o grmad sau adugarea orictor pietre la o grmad (aa cum am menionat anterior, adugarea de pietre la o grmad nu complic analiza jocului). Afirmaia anterioar constituie un rezultat al Teoriei Sprague-Grundy. Roland Percival Sprague (1936) i Patrick Michael Grundy (1939) sunt doi matematicieni care s-au ocupat, independent, de teoria jocurilor impariale. Majoritatea jocurilor impariale se pot reduce la jocul prezentat n problema Pioni de la runda 47 a concursului de programare Bursele Agora. Acolo se meniona urmtorul joc: Se consider un graf aciclic care conine n noduri civa pioni, juctorii alterneaz la mutare i fiecare poate muta cte un pion pe un arc care iese din nodul n care este situat pionul. Pierde juctorul care nu poate muta. Cum graful este aciclic, jocul este finit i are ntotdeauna un ctigtor. Practic, acest joc este suma unor jocuri, mai precis suma a mai multor jocuri cu un singur pion pe graful aciclic. Jocul cu un singur pion poate fi analizat destul de uor, fiecare nod al grafului putnd fi colorat cu alb sau negru dup cum exist sau nu strategie de ctig dac n nodul curent ar fi poziionat pionul. Aceast colorare poate fi realizat uor dac se pornete de la nodurile fr urma i la fiecare pas se coloreaz cte un nod ai crui urmai sunt deja colorai.

GInfo nr. 14/5 - mai 2004

20

Orice joc imparial poate fi redus la un joc cu un singur pion. Nodurile sunt poziiile jocului i arcele grafului sunt mutrile posibile din fiecare poziie. Jocul iniial poate fi i el transformat, dar numrul de noduri crete foarte mult (pentru n pioni i m noduri, numrul de noduri din jocul transformat este nm) i nu este practic s colorm graful rezultat. Folosind teoria dezvoltat de Sprague i Grundy, putem reduce complexitatea analizei jocului cu n pioni la complexitatea analizei jocului cu un pion. Vom introduce funcia mex cu semnificaia: mex(S) este elementul minimal natural care nu aparine mulimii S. Pentru fiecare nod x al grafului aciclic considerat, vom calcula valoarea funciei gx = mex(gx1, gx2, , gxk), unde x1, x2, , xk sunt urmaii nodului x n graf. Pentru nodurile fr urmai gx = 0. Analog jocului cu un singur pion, graful poate fi etichetat din aproape n aproape, pornind de la nodurile fr urmai. Observm c, dac gx = 0 n jocul cu un singur pion situat n nodul x nu avem strategie de ctig, iar dac gx este diferit de 0 avem strategie de ctig. Restul informaiei ne ajut la determinarea unei strategii pentru jocul cu n pioni. Observm c putem reduce acest joc la jocul NIM n care grmada virtual asociat pionului i are un numr de pietre egal cu valoarea g a nodului n care este situat pionul i. De ce este acest joc echivalent cu jocul NIM? Aa cum la NIM puteam lua oricte pietre dintr-o grmad, aici putem muta pionul dintr-un nod cu valoarea g ntr-un nod astfel nct noua valoare pentru pionul i poate fi orice numr de la 0 la g - 1. Prin urmare, pentru a verifica dac suntem ntr-o poziie de ctig n jocul cu pionii, putem aplica strategia jocului NIM i obinem c suntem ntr-o poziie de ctig dac suma XOR a numerelor din nodurile ocupate de cei n pioni este diferit de 0. Aceast sum se numete funcia Sprague Grundy, SG(i1, , in) = gi1^ gi2 ^ gi3 ^ ^ gin. Problema de la runda 47 se rezolv acum uor efectund o sortare topologic a nodurilor grafului aciclic i numerotnd nodurile folosind funcia mex. S studiem acum alte probleme care se pot rezolva folosind numerele Sprague Grundy. Problema 4 Problema Joc a rundei 13 a concursului de programare Bursele Agora putea fi rezolvat n acest mod. n acea problem se cerea s verificm existena unei strategii de ctig pentru un joc similar cu NIM n care se putea lua dintr-o grmad o piatr sau un numr prim de pietre. Dac determinm valorile Sprague Grundy pentru grmezi de dimensiuni mici putem observa c se repeta o succesiune de numere: 0 1 2 3 0 1 2 3

Putem demonstra prin inducie c aceast secven se va repeta la nesfrit. Pentru o grmad de dimensiune n valoarea asociat va fi n modulo 4. Pentru 0 n 3 afirmaia este adevrat. Vom presupune afirmaia adevrat pentru toate valorile m < n. S demonstrm acum c este adevrat i pentru n. Deoarece putem lua din n pietre una, dou sau trei pietre, mai rmne valoarea n modulo 4 care nu este eliminat nc din valorile poteniale asociate grmezii de dimensiune n. Vom arta n continuare c aceast valoare nici nu va fi eliminat. Eliminarea ei ar nsemna c putem lua din n un numr p de pietre i atunci din (n - p) modulo 4 = n modulo 4, am avea: p modulo 4 = 0, dar p este un numr prim, deci valoarea Sprague Grundy asociat unei grmezi de dimensiune n este n modulo 4. Problema 5 (El Judge MIPT online programming contest, Stone game) Se consider k grmezi cu n1, n2, , nk pietre fiecare. Cnd este rndul su, un juctor poate lua dintr-o gramad 2m pietre. Juctorul care ia ultima piatr ctig. Restricii: k 50, ni 10200. S determinm valorile Sprague Grundy pentru grmezi mici: 0 : 0; 1 : 1; 2 : 2; 3 : 0; 4 : 1; 5 : 2; 6 : 0 Observm i aici secvena repetitiv 0 1 2 0 1 2, deci am putea trage concluzia c valoarea Sprague Grundy asociat unei grmezi de dimensiune n este n modulo 3. Aceast afirmaie este adevarat i urmeaz aceeai demonstraie ca n cazul problemei anterioare, iar restul modulo 3 pentru un numr cu 200 de cifre este simplu de gsit determinnd suma cifrelor numrului. Problema 6 (El Judge MIPT online programming contest, Stone game II) Se consider k grmezi de pietre cu n1, n2, , nk pietre. Un juctor poate lua dintr-o grmad la mutarea lui un numr pozitiv de pietre dar nu mai mult de jumtate din pietrele din grmad. Juctorul care nu mai poate muta pierde. Restricii: k 50, ni 100000. Numrul 100000 nu este foarte mare i valorile Sprague Grundy pot fi determinate off-line i incluse n programul nostru ca i constante. Putem scrie pentru valori mici secvena Sprague Grundy: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 010213042 5 1 6 3 7 Pentru n impar valoarea asociat este aceeai cu valoarea asociat lui n/2, i pentru n par valoarea asociat este n/2. Acest lucru se poate demonstra prin inducie matematic.

mate21GInfo nr. 14/5 - mai 2004

mate

Problema 7 (CEOI 2000, Cluj-Napoca, problema Sticks) Se consider n (n 10) rnduri de bee pe o mas, cu Si (Si 10) bee aliniate pe fiecare rnd i doi juctori. Beele de pe rndul i sunt numerotate secvenial de la 1 la Si. Cei doi juctori mut alternativ. Fiecare micare const n eliminarea a unu, dou sau trei bee de pe acelai rnd. Beele trebuie s fie numerotate secvenial, adic s fie consecutive. De exemplu, un rnd are 10 bee i primul juctor elimin beele 4, 5, 6, deci vor rmne numai beele 1, 2, 3, 4, 8, 9, 10. Al doilea juctor poate lua la rndul su beele 1, 2, 3, dar nu beele 3, 7, 8 pentru c acestea nu sunt numerotate consecutiv (bineneles c exist i alte mutri valide). Ctig juctorul care ia ultimul b de pe mas. Problema general are o soluie ingenioas care ine seama de paritile rndurilor, dar la aceast problem, datorit mrginirii lui Si (Si 10) nu este necesar s fim ingenioi. Restricia Si 10, ne ajut prin faptul c numrul total de poziii (dac jucm pe o singur gramad), este 210. Vom reprezenta o poziie printr-un ntreg, iar dac acel ntreg are n codificarea lui binar pe poziia i un bit de 1 nseamn c el reprezint un rnd de bee care conine n el bul numerotat cu i. Este uor de realizat un graf aciclic al micrilor pentru un rnd (graful este aciclic pentru c la fiecare mutare lum bee din configuraie). Numerotm fiecare poziie cu numerele Sprague Grundy, i acum problema deciderii dac suntem sau nu ntr-o poziie ctigtoare devine banal. n problema iniial trebuia s jucm mpotriva calculatorului i s ctigm. Putem realiza aceasta folosind mutarea ctigtoare prezentat la jocul NIM. Problema 8 Aceast problem a fost propus spre rezolvare la concursul Internet Problem Solving Contest (cel mai prestigios concurs online) i o putei gsi la adresa http://ipsc.ksp.sk/ xxproblems/ipsc2003/g.php. Ea a fost folosit i la concursul organizat de .campion la o rund online. Rezolvarea ei, complicat, folosind numerele Sprague Grundy prezentate n acest articol, se poate gsi n [3], pe site-ul [7], sau pe siteul concursului .campion.

Nici una dintre aceste trei mutri nu poate fi efectuat asupra unei tablete de dimensiune 1 1. Pierde juctorul care nu mai poate efectua nici o mutare. n fiierul de intrare se va afla numrul N (1 N 100) de tablete, iar pe urmtoarea linie sunt N perechi de numere ntregi care reprezint dimensiunile tabletelor. n fiierul de ieire se va afla un singur numr ntreg reprezentnd numrul mutrilor ctigtoare pentru primul juctor. Pentru aceast problem vom calcula matricea SGi,j care reprezint valoarea Sprague-Grundy asociat unei tablete de dimensiuni (i, j). S vedem care este recurena care va satisface elementele matricei SG: SGi,j = mex(SGi,k ^ SGi,j-k, (1 k < j) mutarea nti SGk,j ^ SGi-k,j, (1 k < i) SGi,k ^ SGi,j-k-1, (1 k < j - 1) mutarea a doua SGk,j ^ SGi-k-1,j, (1 k < i - 1) SGi-2,j-2) (i > 2 i j > 2) mutarea a treia Acum, pentru a calcula numrul de mutri ctigtoare efectum asupra fiecrei tablete din fiierul de intrare toate mutrile posibile care sunt cel mult de 4 100 + 1 i facem suma XOR a valorilor Sprague Grundy pentru restul tabletelor neimplicate n mutare i a tabletelor rezultate din mutare. Pentru a calcula SGi,j trebuie s parcurgem cel mult 2 i + 2 j + 1 valori obinute. Astfel, algoritmul de determinare al valorilor matricei SG are ordinul de complexitatea O(N3). Complexitatea algoritmului care determin numrul de mutri ctigtoare este O(N2). Am vzut c aceste numere sunt folositoare pentru rezolvarea unor probleme de jocuri combinatorice. Chiar dac numrul strilor grafului nostru aciclic poate s fie foarte mare, putem s ne dm seama, cteodat, din valorile mici de o regul pe care o urmeaz numerele, sau mcar putem determina mai uor configuraii pentru care jocul are sau nu strategie de ctig, fapt care ne poate ajuta n descoperirea rezolvrii generale.

GInfo nr. 14/5 - mai 2004

BibliografieProblema 9 Aceast problem a fost propus spre rezolvare la ediia din acest an a Olimpiadei Naionale de Informatic din Ucraina. Doi participani mnnc alternant din nite tablete de ciocolat dup urmtoarele reguli: taie o tablet n dou, tietura trebuie s fie paralel cu una din laturile tabletei i trebuie s nu taie ptrelele de ciocolat; poate s rup i s mnnce orice linie sau coloan de ptrele care nu se afl pe marginea tabletei; poate s rup i s mnnce toate patrelele de pe marginea tabletei, cu condiia ca tableta rmas s aib cel puin dimensiunea 1 1. 1. ***, colecia GInfo 2. Mihai Oltean, Programarea Jocurilor Matematice, Editura Albastr, Cluj-Napoca, 1996 3. Thomas S. Ferguson, Game Theory Text (online)http://www.math.ucla.edu/~tom/gamescourse.html

4. http://www.ams.org/new-in-math/cover/games1.html 5. http://www.cut-the-knot.com 6. http://www.mathworld.wolfram.com 7. http://ipsc.ksp.sk/Cosmin-Silvestru Negrueri este student n anul III la Universitatea Babe-Bolyai din Cluj-Napoca. El poate fi contactat prin e-mail la adresa kosmin_2000@yahoo.com.

22