El Nim "del doble" (1)

El jocs d'estratègia són un dels millors recursos per treballar la dimensió de resolució de problemes a l'aula. I de forma inevitable es treballen també les altres dimensions (raonament i prova, representació i comunicació i connexions). Són un dels tipus d'activitats més riques i completes. Però, tot i així, sembla que costa que entrin a l'aula com una activitat habitual. Probablement, entre les moltes raons que hi poden haver, està que sovint no semblen tenir una relació molt directa amb els continguts clàssics. També que mestres i professorat no tenim molt de costum en l'anàlisi de jocs, que tenim una certa inseguretat en l'abordatge de la seva resolució.

El "Tres en ratlla" és un exemple clàssic de joc d'estratègia

En els jocs d'estratègia, que no depenen de cap habilitat física o manipulativa especial ni de cap aspecte relacionat amb l'atzar, s'apliquen tècniques molt habituals de la resolució de problemes. Podeu veure algunes relacions en aquests quadres.

En aquest article estudiarem un joc que, en el passat C2EM, van plantejar Jordi Font i Laura Morera en la seva esplèndida conferència de cloenda. Aquest joc l'anomenarem el "Nim del doble" i és molt interessant i, fins i tot, sorprenent complex. Cal dir que també en conferència inaugural, a càrrec d'Eduardo Sáez de Cabezón, es va plantejat un altre joc de tipus Nim.

Per poder exemplificar millor el procés de l'anàlisi del joc no el mostrarem directament acabat. Anirem mostrant i comentant diferents moments d'aquest procés, fins i tot posant en evidència errades, conjectures falses, idees explorades i abandonades, descobertes de nous camins... Pensem que així, potser, es veurà millor la riquesa d'aquesta petita investigació matemàtica.

Presentem primer el joc. L'únic material necessari és un conjunt de fitxes.

Regles:

• Tenim una pila d'n fitxes. Per exemple 20.
• El primer jugador, a l'inici, pot agafar totes les fitxes que vulgui menys una (en el nostre exemple pot agafar d'una a dinou).
• El segon jugador pot agafar entre una i el doble de les que ha agafat l'anterior. Per exemple, si el primer (A) agafa 4 fitxes , el segon (B) podrà agafar-ne entre 1 i 8.
• Es continua jugant amb aquesta regla.
• Guanya qui deixa la taula neta (qui agafa l'última o últimes fitxes)

A les dues taules següents teniu l'exemple del desenvolupament de dues partides. La primera la guanya B (el 2n jugador) i la segona A (el primer jugador) .

No cal dir que, abans de continuar llegint, és millor que jugueu algunes partides i comenceu a fer les primeres hipòtesis.

Analitzem el joc?

En els jocs d'estratègia hem de pensar, que si no intervé l'atzar, tot pot estar determinat. És a dir: ha d'existir una estratègia per a guanyar (per al primer o per al segon jugador) o per a no perdre (fer taules). Una altra cosa és que coneguem aquesta estratègia. Als escacs o al Go, per exemple, no les sabem encara. Del tres en ratlla, en la seva versió TIC-TAC-TOE, sí. Tenir una estratègia significa saber què hem de fer, en cadascuna de les situacions possibles de la partida, per a obtenir el millor resultat: victòria o taules.

Una consideració prèvia que hem de fer sobre l'anàlisi és que, en tot moment, hem de pensar que els dos jugadors juguen perfectament, que no s'equivoquen. Això, de vegades, ens costa una mica. Però ens permet descartar moltes jugades durant la investigació del joc. Fins i tot abandonar una línia d'anàlisi quan veiem que la situació és perdedora, immediatament o a vàries jugades vista. També hem de tenir cura en la consideració de les possibles respostes a una jugada. Hem de parar atenció a no deixar-nos casos d'estudi.

1a fase: reduïm el joc

Una primera possibilitat d'anàlisi és fer una reducció del joc. Podem començar, per exemple, amb 7 fitxes. D'aquesta manera anirem agafant les primeres idees. Després podrem reduir-lo o ampliar-lo més. Segons ens interessi. 

D'entrada podem pensar que, encara que segons les regles el 1r jugador té sis opcions (pot agafar entre una i sis fitxes) algunes són descartables perquè són directament perdedores. Mirant aquesta taula veurem clarament que només tenim dues sortides no perdedores: agafar-ne una o dues fitxes.

Comencem per estudiar que A agafa una fitxa.

B pot agafar-ne una o dues. No és difícil veure que si B agafa 2 nosaltres, donat que podem agafar fins el doble de la tirada anterior, podem agafar 4 i guanyarem. Per tant, descartem aquesta jugada i suposarem que B jugarà "perfectament" i agafarà una només. Gairebé podem dir que és una "jugada obligada" per a no perdre de forma directa.

És el torn d'A que pot agafar-ne una o dues. Si n'agafa dues en deixa tres i B pot agafar fins a quatre. Per tant, la jugada "obligada" és agafar-ne una també.

Amb el mateix raonament veurem que B només pot tornar a agafar-ne una, ja que si n'agafa dues A guanyarà.

De nou és el torn d'A que ja ho té tot perdut. Si n'agafa una, B podrà agafar les dues que queden, i si n'agafa una, B es quedarà la que queda.

Ja tenim una petita conclusió. El jugador A no ha de començar agafant una fitxa perquè B podrà guanyar segur. Estudiem ara iniciant el joc amb una extracció de dues fitxes.

Com abans entrem en una seqüència de jugades "obligades" ja que hi ha opcions directament perdedores. Aquestes jugades porten a B a aquesta situació de joc perdedora. És indiferent que agafi una o dues que perdrà.

Conclusió: per al joc amb set fitxes guanya A si comença traient dues fitxes, deixant-ne 5. Si l'altre agafa 2, 3 o 4, A guanya directament agafant les que queden. Si B n'agafa només una, A també agafarà una, deixant-ne tres. Si B agafa una, A agafa dues i si B agafa dues A agafa una. Podem fer un diagrama en arbre que ens ho resumeixi. Les jugades d'A són les de color verd i en blau estan les de B i anotem la jugada que fem i, entre parèntesis, les fitxes que deixem al contrari. Les línies vermelles marquen el camí per guanyar d'A. Podem veure que per a cada jugada possible de B hi ha una resposta que porta a la victòria. Fins i tot, podríem fer un arbre simplificat només amb les branques vermelles.

Arbre complet del joc amb 7 fitxes

Aquí haig de confessar que vaig cometre una errada: tot i ser conscient de que l'estratègia era per a A vaig anotar al marge que era per a B. Tindrà, com veurem la seva importància en la formulació de conjectures errònies.

Provem amb casos més petits i fem la primera conjectura.

A continuació vaig passar a cercar les estratègies per a menys fitxes. No mostraré, com per a 7 fitxes, els arbres complets del joc sinó la reducció que assenyalen les estratègies guanyadores.

• 6 fitxes

Amb 6 fitxes guanya A

• 5 fitxes

Amb 5 fitxes guanya B

• 4 fitxes

Amb 4 fitxes guanya A

Bé... tenia anotat, erròniament, que amb 7 fitxes guanyava B i, observant que amb 5 també, i que l'estratègia era per a A quan es començava amb 6 i 4 vaig fer la primera conjectura.

Conjectura: Si la quantitat inicial de fitxes és parell guanya A i, si és senar, guanya B

Tot i així no quedava definida l'estratègia general a seguir. Només creia que sabia qui guanyaria. I m'hi vaig posar.

Estudiem l'inici i ensumem una estratègia

Una tècnica típica de l'anàlisi de jocs és començar des del final de la partida. En el Nim normal, amb unes quantitats fixes per poder agafar, per exemple 1,2 o 3, és la millor per a trobar l'estratègia general. Però en aquest cas vaig pensar que no em serviria perquè les jugades possibles depenen de les anteriors (recordeu: entre 1 i el doble). Per tant em semblava més òptim començar des de l'inici. Per exemple mirant com esbrinar les primeres jugades "no perdedores". Donat que ja estava més familiaritzat amb aquest "nim del doble" vaig observar que si el primer jugador fa una jugada a, el segon pot anar fins al doble, 2a. Això feia pensar en dividir la quantitat de fitxes entre 3 (a+2a=3a) i observar si en sobraven o no. Mirem un exemple amb 9 fitxes.

Múltiple de 3. A no pot començar amb tres fitxes o més

Així, d'alguna manera, podem provar la següent conjectura d'estratègia:

Conjectura: hem de deixar al contrari amb una quantitat de fitxes que sigui múltiple de 3.

Provem-ho amb una partida amb 10 fitxes.

Podem intuir que una bona sortida serà agafar la que sobra de dividir per 3 (10:3=3, residu 1). Agafem una i queden 9 fitxes.

Observació de terços i jugada d'A

Podem explorar que B jugui aplicant la mateixa idea dels terços o no. De moment explorarem com si no ho fes. Només serà A qui l'apliqui en el seus torns. Segons el que jugui B farem la divisió per 3 al que deixi i eliminarem el residu. Imaginem que agafa 2 fitxes. Ara calculem la jugada per A amb les 7 fitxes que ens han deixat (7:3=2, residu 1). Agafem una i en deixem 6.

Jugada de B. Observació de terços. Jugada d'A.

Imaginem ara que B juga de nou 2. Iterem el procés. Queden 4 (4:3=1, residu 1). Agafem 1 i deixem 3.

Jugada de B. Observació de terços. Jugada d'A

B ja està perdut. Si agafa una, A agafa dels dues últimes. Si agafa dues, A agafa la que queda.

Sembla que ha funcionat. Però alguna cosa no hem fet bé. Hem d'estar sempre alertes a que no ens haguem descuidat res. Aquí no hem tingut en compte les diferents opcions de B a cada jugada o si B podia aplicar la mateixa norma de la divisió per 3. De fet, si anem provant amb altres quantitats de fitxes veurem que no acaba de funcionar. I, si ho mirem amb més detall, veurem alguna contradicció. Per exemple, hi ha un moment de la partida que hem fet amb 10 fitxes que hem passat per la situació en què A es trobava amb 7 fitxes a la taula. L'estratègia per a 7 fitxes la tenia estudiada (tot anotant, erròniament, que gavanyava A). Per tant B podria haver guanyat. Aquí és quan vaig revisar l'arbre i vaig descobrir l'error. L'estratègia era per A. Semblava eliminar-se la contradicció. Però en va sorgir una de nova: A no havia seguit l'estratègia! Comparem l'estratègia simplificada (eliminant jugades perdedores directes) amb el desenvolupament de la partida. Hi ha coses que quadren i coses que no.

Per més inri vaig poder descobrir una altra partida en la que A aplica persistentment l'estratègia del "terç" i acaba perdent.

Una observació nova i retornem a l'inici

Un dels problemes que em va donar l'anàlisi d'aquest joc és que les opcions de tirada eren variables. Sempre depenien de les jugades anteriors. Això em feia pensar que no hi havia situacions de joc guanyadores o perdedores predeterminades. És a dir que, per exemple, deixar al contrari amb 3 fitxes podia ser guanyador si hi arribem traient una fitxa, però no si arribem traient-ne 2 o més. Però hem vist també que les tirades més usuals són curtes, el que ens pot permetre aprofitar algunes d'aquestes situacions guanyadores. Per tant vaig fer alguns arbres més: per a 8, 9, 10.. i per a 3 i 2 fitxes. (Que si ho hagués fet abans hauria vist que la primera conjectura, la de parells i senars, era falsa). Cal dir que no vaig fer els arbres complets. Ara no em calia. Sabia que si deixava al contrari una situació com 5 (que l'arbre em deia que era guanyadora per B) i venia de treure una o dues fitxes, ja tenia la partida guanyada. A partir d'aquí només em calia seguir l'arbre que ja tenia d'abans. No mostro aquests arbres, però si la taula que vaig fer. Anotant qui guanya (A o B) i les quantitats de fitxes que deixo al contrari durant la partida. He anotat alguns nombres en vermell. Segur que us sonaran.

Sorprenent: apareixen els nombres de Fibonacci! Si la quantitat inicial de fitxes és un d'aquests nombres l'estratègia és per a B. Si no ho és, l'estratègia serà per a A jugant al primer nombre de Fibonacci que pugui, al més proper a la quantitat inicial del joc.  I en tots dos casos hem d'anar passant per nombres de Fibonacci a les jugades intermèdies. Sembla que ho tenim. Les dues primeres conjectures eren falses. Però ara tenim una més consistent:

Conjectura: Per a guanyar hem de deixar al contrari una quantitat de fitxes que sigui un nombre de Fibonacci. 

I si ho provem amb 12 fitxes, que no ho tenim estudiat encara?

La crisi de les 12 fitxes

Si mirem la partida amb 12 fitxes i volem aplicar la conjectura anterior, haurem de deixar a B amb 8 fitxes, que és el nombre de Fibonacci més proper. Però, per fer-ho, hem d'agafar 4. I, si agafem 4, B podrà agafar les 8 que queden i ens guanyarà.

Sembla que hem d'estudiar més. Tocarà fer un arbre nou. I, ja posats ho farem també per 13, que torna a ser un nombre de Fibonacci i segons la nostra conejctura serà una partida guanyadora per a B.

Treballant els arbres

Amb 12 fitxes trobem que l'estratègia guanyadora és per a A. Si mireu l'arbre que resumeix l'estratègia guanyadora veureu que ja no el fem fins al final. Quan arribem a una situació guanyadora coneguda, per exemple 2(5) o 1(5) posarem etc. i entendrem que hem de seguir l'arbre que ja teníem per a 5 fitxes.

Què ens produeix la crisi sobre la conjectura? Que per a guanyar A ha de deixar 11 fitxes, que no és un nombre de Fibonacci.

Mirem ara l'arbre d'estratègia per a 13 fitxes, tot recordant que, com abans, no posem les jugades immediatament perdedores i no acabem totes les branques quan ja sabem la continuació.

Com veieu podem aprofitar com a resposta a la jugada d'A 1(12) la jugada guanyadora que coneixem de l'arbre de dotze: 1 (11). També veiem que amb una quantitat inicial de fitxes que és un nombre de Fibonacci guanya B, com havíem observat.

Bé... Els nombres de Fibonacci tenen un paper important en aquest joc. Però l'11 que ens ha aparegut com a jugada guanyadora no ho és. Hi ha alguna cosa més que se'ns escapa per a poder trobar una estratègia general i no anar resolent cas a cas i matar-nos a fer arbres. Caldrà seguir estudiant.

Però això serà tema del proper article. Aquest està sent molt llarg.

Continuarà...

PD: i, mentrestant, podeu anar investigant vosaltres!

 

• El Nim "del doble (2)