Grafs aplicats a la resolució de jocs

Butlletí de la Societat Catalana de Matemàtiques Vol. 12, núm. 1, 1997. Pàg. 17–25. Grafs aplicats a la resolució de jocs Josep M. Basart i Pere Guitart 1 Conceptes previs Un graf G(V,A) (o simplement Gsi no hi ha ambigüitat) és una estructura formada per un conjunt finit de vèrtexs Vi un conjunt finit de línies A, de manera que cada línia relaciona dos dels vèrtexs. Les línies s’anomenen arcs si estan orientades, és a dir, si tenen determinat el sentit de recorregut; en cas contrari, s’anomenen arestes. Un arc que va del vèrtex xal vèrtex yes representa com una parella ordenada (x, y). Si el graf és simètric (x, y) és equivalent a (y, x). Una aresta del tipus (x, x) s’anomena llaç. Un graf format per arcs s’anomena dirigit, si està format per arestes s’anomena simètric i no considerarem grafs mixtos. Si Gés dirigit i x∈Vel conjunt dels antecessors de xve donat per Γ−1(x) ={y|(y, x) ∈A}. Igualment, el conjunt dels successors de xve donat per Γ(x) ={y|(x, y) ∈A}. Si Gés simètric, Γ(x) =Γ−1(x) i aquests elements són els veïns de x. En un graf dirigit, grau interior(x) =#{Γ−1(x)} grau exterior(x) =#{Γ(x)}. Si el graf és simètric es parla simplement de grau (x). El graf subjacent corresponent a un graf dirigit s’obté de prescindir de l’orientació imposada a cadascun dels arcs, dit d’una altra manera, el graf passa a ésser considerat com si fos simètric. Un multigraf és tot graf que admet arestes repetides una o més vegades, en aquest tipus de graf cada aresta incident en x∈Vcontribueix en una unitat al grau(x).Uncamí de xay(x,y ∈V) és una llista d’arestes 18 Josep M. Basart i Pere Guitart (d’arcs) que comença en x, tal que el vèrtex final de cada aresta (arc) és l’inicial del següent, tret del darrer que és y. Un graf simètric és connex si conté un camí entre cada parella de vèrtexs. Un camí en què coincideixen el vèrtex inicial i el final és un circuit. Un circuit que no repeteix cap aresta (arc) s’anomena simple. Un circuit és eulerià si és simple i recorre totes les arestes (tots els arcs) del graf. Un graf és eulerià si té un circuit eulerià. Un factor en un graf (multigraf) simètric de nvèrtexs és tot conjunt de narestes que formen un o més circuits disjunts simples. Final ment, el nucli d’un graf dirigit és un subconjunt de vèrtexs tal que: i) no hi ha cap arc entre dos vèrtexs del nucli, i ii) hi ha un arc des de cada vèrtex fora del nucli cap a un vèrtex del nucli. 2 Tres jocs Considerarem tres dels jocs paradigmàtics en què un graf (diferent en cada cas) serveix per modelitzar la situació i analitzar-ne el desenvolupament. Així, amb l’ús adequat d’algun concepte o propietat del graf resultant es podrà resoldre el joc. Els jocs progressius finits —il.lustrats en el primer joc— foren estudiats, en un context més general, en [2], mentre que el model de resolució del trencaclosques amb cubs —corresponent al segon joc— aparegué en [5]. Tant [1] com [3] són obres generals sobre la formulació i l’anàlisi matemàtica de jocs. Pel que fa al darrer joc, els circuits eulerians —tal com llur nom indica— van ser estudiats per L. Euler ara fa dos-cents seixanta anys. Les seqüències de De Bruijn foren introduïdes en [4] i generalitzades en [6]. 2.1 Primer joc «Es disposen vint-i-una cerilles damunt d’una taula. Dos jugadors, al seu torn, en van prenent una, dues, tres o quatre cada vegada. Guanya el jugador que pren la darrera.» Considerem aquells jocs per a dos jugadors en què, al seu torn, cadascun fa una jugada o moviment fins que un d’ells acaba guanyant. Si el nombre d’opcions per a cada jugada és sempre limitat i el joc acaba necessàriament en un nombre finit de moviments, el joc s’anomena progressiu finit. És el cas, per exemple, del joc proposat més amunt, mentre que el joc de les dames no ho és. Un joc progressiu finit pot ésser modelitzat mitjançant un graf dirigit Gen què cada estat del joc ve representat per un vèrtex i cada transició d’un estat xa un altre yes denota per (x, y).Enel cas del joc enunciat tindríem un graf de 22 vèrtexs (des de vint-i-una cerilles fins a zero cerilles) indexats v0,v 1, ..., v21.Dev21 sortirien (v21,v 20),(v21,v 19),(v21,v 18) i(v21,v 17),av0arribarien (v4,v 0),(v3,v 0)(v 2,v 0)i(v1,v 0), i en els altres vèrtexs hi hauria els arcs corresponents d’arribada i de sortida. Una posició guanyadora és aquella que dóna la victòria al jugador que l’assoleix. Una estratègia guanyadora és aquella que, en cada estat del joc, condueix el jugador que la segueix cap a una posició guanyadora. Com que els vèrtexs de grau exterior nul en el graf corresponent a un joc progressiu finit es corresponen a posicions guanyadores, s’anomenen vèrtexs guanyadors. En el joc de les cerilles tindrem com a posició guanyadora la representada pel vèrtex guanyador v0, mentre que pot comprovar-se fàcilment que l’estratègia guanyadora consisteix a fer sempre una jugada que deixi el joc amb un nombre de cerilles múltiple de cinc, és a dir, moure Grafs aplicats a la resoluci´ o de jocs 19 sempre cap a v20,v 15,v 10 ov5. D’aquesta manera, el primer jugador s’assegura la victòria si comença prenent una única cerilla. En general, a partir dels vèrtexs guanyadors podem establir l’estratègia guanyadora analitzant les possibilitats en la tornada enrere des dels vèrtexs guanyadors cap a l’estat inicial, tot detectant quins són els vèrtexs «bons» que cal assolir per poder guanyar la partida. En el nostre cas, per assegurar v0cal haver assegurat abans v5i, prèviament, v10,v 15 iv20. Notem que el nucli de Gcorresponent al joc està format precisament per aquests cinc vèrtexs. Passem ara a formalitzar la idea de vèrtexs bons i a situar-los en el graf Gque hem definit. 1 Proposició Si Gté un nucli N, una estratègia guanyadora consisteix a situar-se, en cada moviment, en un vèrtex de N. Prova: Atès que els vèrtexs que no estan en Nhan de tenir un arc cap a algun vèrtex en Ni que els vèrtexs guanyadors han de tenir grau exterior nul, és clar que tots els vèrtexs guanyadors estaran en N. D’altra banda, per la definició de nucli tenim que, si el primer jugador fa una jugada cap a un vèrtex de N, el segon jugador haurà de moure cap a un vèrtex de fora de Ni, a continuació, el primer jugador podrà tornar a entrar-hi. Així, mantenint aquesta alternança de vèrtexs dins i fora de Nel joc acabarà amb la victòria del primer jugador. Notem que si el vèrtex inicial del joc està en el nucli, és el segon jugador qui es pot apoderar de l’estratègia guanyadora.  Ara cal veure que el graf Gde tot joc progressiu finit té un nucli (no tot graf dirigit en té) i que aquest pot ésser localitzat fàcilment. Per a això ens cal abans estructurar els vèrtexs de Gen funció de com es troben de propers d’un vèrtex guanyador. Definim per a cada x∈Vel seu nivell d(x) en Gi construïm els conjunts Dtde vèrtexs a nivell ≤tcom: d(x) =0Γ(x) ={} D0={x|d(x) =0}; d(x) =1x∈ D0iΓ(x) ⊆D0 D1=D0∪{x|d(x) =1}; ······ d(x) =tx∈ Dt−1iΓ(x) ⊆Dt−1 Dt=Dt−1∪{x|d(x) =t}. És clar que cada vèrtex a nivell 0 és un vèrtex guanyador, mentre que moure cap a un vèrtex a nivell 1 porta a la derrota. Arribar a un vèrtex de nivell 2 també hi porta, si és adjacent a un vèrtex de nivell 0, mentre que és un vèrtex que porta a la victòria si tots els seus successors estan a nivell 1. I anàlogament per als vèrtexs en els nivells superiors. Observem també que, per construcció, cada vèrtex a nivell t>0 tindrà un arc cap a un altre vèrtex a nivell t−1 però mai un arc cap a un altre vèrtex de nivell to superior. 2 Proposició En tot joc progressiu finit el graf associat té un únic nucli. Prova: Per inducció sobre els Dt. Sigui Ntel conjunt de vèrtexs del nucli que estan en Dt. Pel cas base, el conjunt D0, sabem que tots els vèrtexs guanyadors es troben en el nucli, per tant, N0=D0. Prenem com a hipòtesi d’inducció que Nn−1és el 20 Josep M. Basart i Pere Guitart conjunt de vèrtexs del nucli que es troben en Dn−1. Hem de trobar un conjunt únic de vèrtexs a nivell ntal que afegit a Nn−1formi el nucli Nnper a Dn. Ara, si un vèrtex xa nivell nno és adjacent a cap vèrtex del nucli en Nn−1, aleshores, xha d’estar en Nn; d’altra banda, si xés adjacent a algun vèrtex del nucli en Nn−1, aleshores, xno pot estar en el nucli. Per tant, Nn=Nn−1∪x|d(x) =non Γ(x) ∩Nn−1={}  és el conjunt de vèrtexs del nucli en Dn. Per inducció, Gté un nucli i aquest és únic.  Tenim, doncs, per la demostració inductiva de la proposició 2, un esquema per a formar el nucli. Començant el nucli amb els vèrtexs guanyadors, anem afeginthi —seguint l’ordre dels nivells— els vèrtexs que no són antecessors de cap dels vèrtexs del nucli en l’estat actual. Per aconseguir això d’una forma sistemàtica pot seguir-se el procediment següent d’etiquetatge numèric dels vèrtexs. A cada vèrtex xli assignem una etiqueta E(x) definida com l’enter més petit no negatiu que encara no ha estat assignat a cap vèrtex en Γ(x). Així, tot vèrtex xa nivell 0 rep E(x) =0; a continuació, determinem E(x) per als vèrtexs xa nivell 1, després el mateix per als de nivell 2, etc. Aquest procediment acaba generant el nucli del graf. Finalment, 3 Proposició L’etiquetatge E(x) dels vèrtexs xdel graf Gassociat a un joc progressiu finit és únic. Prova: És clar que cada vèrtex del graf rep una i només una etiqueta. Per la definició de l’etiquetatge, si xté E(x) =0 no pot existir un (x, y) en Gtal que E(y) =0ja que, si fos així, xhauria rebut una etiqueta diferent. Igualment, tot vèrtex yamb E(y) > 0 ha de ser vèrtex antecessor d’un vèrtex zamb E(z) =0 ja que, en cas contrari, tindríem E(y) =0. Per tant, l’etiquetatge satisfà les dues propietats que caracteritzen el nucli.  2.2 Segon joc «Disposem de quatre cubs pintats amb un dels quatre colors, blanc, vermell, negre o groc, en cadascuna de les sis cares. Es demana de formar una columna apilant els quatre cubs de manera que aparegui una vegada cadascun dels quatre colors en cadascun dels quatre costats de la columna.» Si tenim cada cub pintat sencer amb un únic color, diferent del color de cadascun dels altres tres cubs, els podem apilar de qualsevol manera i obtindrem una solució. En el cas general, però, determinar si el trencaclosques té solució o no, és força més complicat. Pensem que el cub presenta 24 simetries i que, per tant, tenim en principi 244configuracions possibles, tot i que —segons els colors assignats— moltes podrien ésser descartades directament. Durant l’anàlisi usarem la notació següent: cub1, cub2, cub3, cub4 seran els quatre cubs del joc; B, V,NiGelsquatre colors, mentre que ˆ fi,ˆ ri,ˆ di,ˆ eidenotaran, respectivament, els colors del i-èsim cub (1≤i≤4)en els costats front, rere, dret i esquerre de la columna formada. La solució del trencaclosques verifica la que anomenarem propietat de separabilitat oindependència entre els costats adjacents en la columna de cubs. Aquesta Grafs aplicats a la resoluci´ o de jocs 21 propietat recull el fet que podem resoldre per separat el joc considerant únicament dos costats oposats de la columna (com ara el dret i l’esquerre), la resolució dels altres dos costats (front i darrere) es pot obtenir mitjançant la rotació de cadascun dels cubs (al voltant d’un eix horitzontal, en aquest cas). Aquesta possibilitat de descomposició del problema en dos subproblemes serà explotada a continuació. El model per representar i analitzar el joc és un multigraf Gamb les arestes etiquetades. Assignarem un vèrtex a cadascun dels colors (B, V, N, G) i una aresta entre dos vèrtexs xiyetiquetada ksi el k-èsim cub té els colors xiyen cares oposades. En total, doncs, quatre vèrtexs i dotze arestes. Il.lustrem en la figura 3 el multigraf corresponent als quatre cubs representats en les figures1i2. cub1 cub2 BB BGVBBV GN GG Figura 1: cub1 i cub2. NG NBGNVG NG VN cub3 cub4 Figura 2: cub3 i cub4. Per la propietat de separabilitat considerarem únicament els costats esquerre i dret de la columna de cubs, és ací on volem obtenir —en cada costat— una cara amb cada color. De fet, podem començar rebaixant una mica més el propòsit: demanem, per ara, d’obtenir vuit cares oposades dels quatre cubs que en total facin aparèixer dues vegades cadascun dels quatre colors. Més tard ja veurem com assegurar que cada color apareix un cop en cada costat (esquerre i dret) de la columna. En termes de grafs, volem determinar en el multigraf del joc quatre arestes, una amb cadascuna de les etiquetes 1, 2, 3, 4, de manera que en el subgraf format cadas- 22 Josep M. Basart i Pere Guitart BG N V BG N V 44 1 233 2 1 (α) (β) Figura 3: Multigraf associat. cun dels quatre vèrtexs tingui grau dos (per convenció, cada llaç contribueix en dues unitats al grau del vèrtex corresponent). Això és el mateix que determinar un factor que tingui les quatre etiquetes possibles en les arestes; en direm un factor canònic. En la figura 4 tenim representats dos dels cinc factors canònics corresponents al multigraf de la figura 3. BG N V43 4 1 4 2 3 12 2 1 3 Figura 4: Dos factors can` onics. El pas següent és veure com per a cada factor canònic podem obtenir la resolució parcial del joc, és a dir, els costats esquerre i dret de la columna de cubs amb els quatre colors alternats. Considerem el factor canònic αde la figura 4. Si en fem un recorregut al llarg del circuit començant per un qualsevol dels vèrtexs, podem obtenir una disposició dels cubs en la columna si fixem com a costat esquerre el primer vèrtex de cada aresta trobada i com a costat dret el segon. Així, d’aquest factor, començant pel vèrtex Vobtindrem: ˆ e4=V, ˆ d4=N; ˆ e3=N, ˆ d3=G; ˆ e1=G, ˆ d1=Biˆ e2=B, ˆ d2=V. En el cas del factor βde la mateixa figura, obtindrem: ˆ e4= V, ˆ d4=N; ˆ e2=N, ˆ d2=B; ˆ e3=B, ˆ d3=Viˆ e1=G, ˆ d1=G. Arribats ací, podem donar el trencaclosques per resolt. Efectivament, només cal inspeccionar el multigraf associat als cubs i determinar si hi ha dos factors canònics disjunts d’arestes. Si aquest és el cas, per la propietat de separabilitat, cadascun d’ells ens permetrà —seguint el procediment acabat de veure— obtenir la disposició de dos costats oposats de la columna. Atès que el multigraf G(V,A) del joc és sempre prou reduït (#{A}=12,#{V}=4)la recerca d’aquests dos factors no presenta cap dificultat computacional. Grafs aplicats a la resoluci´ o de jocs 23 2.3 Tercer joc «Disposem d’un nombre il. limitat de pedretes blanques i negres, i volem formar un braçalet enfilant-les una rere l’altra. Quantes n’hi podrem col. locar sense que es repeteixi cap agrupació de kpedretes consecutives?» Atès que podem formar fins a 2kseqüències diferents de longitud k, és clar que aquest és el nombre màxim de pedretes que podrem enfilar. Cal tenir present que el braçalet és circular, és a dir, que la darrera pedreta enfilada quedarà entre la penúltima i la primera. A continuació, veurem com un graf ens permetrà de generar braçalets amb 2kpedretes que verifiquen la condició enunciada. Usarem un 0 o un 1 per a representar cada pedreta segons sigui, respectivament, blanca o negra, mentre que k≥2 és un nombre natural. Per al cas k=4 una solució és la seqüència 0000100110101111, la qual té longitud 24. La resolució del joc passa per estudiar els anomenats diagrames de De Bruijn, una família de grafs dirigits que contenen circuit eulerià. Comencem, però, presentant una caracterització dels grafs dirigits eulerians. 4 Proposició Un graf dirigit G(V, A) és eulerià si, i només si, té el graf subjacent connex i grau interior (x) =grau exterior (x) ∀x∈V. Prova: És clar que si el graf subjacent no és connex no podrem formar un circuit eulerià. La condició d’igualtat entre grau interior i grau exterior en cada vèrtex és també immediata. Efectivament, cada vegada que el circuit visita un vèrtex qualsevol necessita un arc per arribar-hi i un altre per sortir-ne. Queda per veure que aquesta condició és, alhora, suficient. Aquest resultat s’obté construint un circuit eulerià. Començant per un vèrtex xqualsevol, formem un circuit simple C1que acabi en x.SiC1ha usat tots els arcs, hem acabat obtenint el que volíem. En cas contrari, eliminem els arcs usats en C1; amb això cada vèrtex ydel graf continua amb grau interior (y) =grau exterior(y). Prenem un vèrtex zqualsevol que formi part d’algun dels arcs no eliminats i repetim el procediment seguit per a xformant així un nou circuit C2.SiC1∪C2=A, hem acabat i la unió dels dos circuits forma un circuit eulerià. En cas contrari, eliminem també els arcs de C2i repetim el procés amb un altre vèrtex tpertanyent a algun arc romanent. Finalment, de la unió de tots els circuits n’obtindrem un d’eulerià.  Sigui ara G∗(V∗,A ∗)el graf dirigit amb 2k−1vèrtexs definits per totes les seqüències binàries de longitud k−1i2 karcs etiquetats per totes les seqüències binàries de longitud k, de manera que l’arc etiquetat s1,s 2, ..., sk(si∈{0,1})va del vèrtex s1,s 2, ..., sk−1al vèrtex s2,s 3, ..., sk.G∗s’anomena un diagrama de De Bruijn.Enla figura 5 tenim el G∗corresponent a k=3. 5 Proposició G∗és eulerià per a tot natural k≥2. Prova: Per construcció, G∗té el graf subjacent connex. El vèrtex s1,s 2, ..., sk−1 és assolit pels dos arcs etiquetats 0,s 1,s 2, ..., sk−1i1,s 1,s 2, ..., sk−1. D’altra banda, el vèrtex s1,s 2, ..., sk−1és el vèrtex de sortida dels dos arcs s1,s 2, ..., sk−1,0i s1,s 2, ..., sk−1,1. D’aquesta manera, tenim grau interior (x) =grau exterior(x) =2 en cada x∈V∗. 24 Josep M. Basart i Pere Guitart Figura 5: G∗per k=3. Ara ja tenim la feina feta. Efectivament, tal com hem definit el graf, si formem un circuit eulerià en G∗i prenem el primer símbol (si)de l’etiqueta de cadascun dels arcs que el formen, obtenim una seqüència (seqüència de De Bruijn) de longitud 2k, que representa un dels braçalets desitjats. Així, en el graf de la figura 5, podem considerar el circuit eulerià que comença en el vèrtex 00 i és donat pels arcs 000 001 010 101 011 111 110 100 De la primera columna n’obtenim la seqüència 00010111. Notem que, tant la segona columna com la darrera produeixen també seqüències de De Bruijn, atès que no són altra cosa que desplaçaments circulars consecutius dels símbols de la primera columna. Finalment, destacar que la generalització per a braçalets amb n≥2 tipus de pedretes és directa a partir del que hem vist. Per analogia, obtindrem una seqüència de De Bruijn amb nksímbols a partir d’un circuit eulerià en un graf G∗amb nk−1vèrtexs inkarcs, de manera que per a cada x∈V∗grau interior(x) =grau exterior (x) =n. Referències [1] Berlekamp, E.; Conway, J.; Guy, R. On Winning Ways. New York: Harcourt Brace, 1978. Grafs aplicats a la resoluci´ o de jocs 25 [2] Bonton, C. L. «Nim, a game with a complete mathematical theory». Ann. Math. 3 (1902), p. 35–39. [3] Conway, J. H. On Numbers and Games. New York: Academic Press, 1976. [4] De Bruijn, N. G. «A combinatorial problem». Ned. Akad. Wet. 49 (1946), p. 758– 764. [5] De Carteblanche, F. «Pile of cubes». Eureka, (April 1947). [6] Good, I. J. «Normal Recurring Decimals». J. Lond. Math. Soc. 21 (1946), p. 167– 169. Departament d’Informàtica Universitat Autònoma de Barcelona 08193 Bellaterra [email protected]