Un joc d'estratègia amb aire diofàntic

A la 53a Olimpiada Matemática Española, celebrada al mes de març de 2017, es va proposar el següent problema que convida a analitzar un joc. El més interessant és que, canviant els nombres, es pot jugar des de l'educació primària. Però la cerca d'una estratègia també comporta un bon treball matemàtic. La imatge del full de l'enunciat me la va enviar l'amic i especialista en jocs Jordi Deulofeu.

El joc es planteja sobre un tauler però poder fer un equivalent numèric ràpidament:

"Cada jugador pot sumar 53 o restar 2 alternativament. Es comença des de zero i guanya qui arriba exactament a 2017. No es pot sobrepassar en cap moment el 2017 ni es pot baixar de zero."

Com que no som "olímpics" treballarem el joc "a pic i pala". És interessant perquè en el seu estudi es poden veure dues fases ben diferents i, en una d'elles, la representació visual que fem ens pot ser de gran ajuda ja que ens permetrà fer analogies no numèriques per a la cerca de l'estratègia.

Reduïm el joc i fem les primeres passes

És molt habitual en l'anàlisi de jocs fer variacions que simplifiquin el problema i així poder facilitar els descobriments. Per exemple podem jugar amb +7 i -2 i que el límit sigui 23. Fins i tot per estudiar-lo a l'aula seria molt millor presentar inicalment una versió reduïda i més accessible. Abans de seguir llegint et proposem que analitzis el joc. I si ara no en tens ganes de fer-ho... continua la lectura.

Amb aquests nous nombres, quina quantitat anterior a 23 m'assegura guanyar? La resposta no és massa difícil: 18. Si al contrari li deixo 18 no pot sumar 7, perquè es passaria de 23, per tant està obligat a restar 2 deixant 16. Ara només em caldrà sumar 7 per arribar a 23. Molt bé, però quina quantitat anterior m'assegura arribar al 18 guanyador. Aplicant un raonament regressiu (molt habitual també en l'anàlisi de jocs) veurem que també seran 5 abans del 18: el 13. Si suma 7 podré restar 2 i deixar el total en 18 (13+7-2=18). Si en resta 2 podré sumar 7 i tornar a deixar en 18 (13-2+7=18). Fent aquest raonament regressiu veiem que els nombres guanyadors són:

18 - 13 - 8 - 3

A partir de qualsevol d'aquests nombres només cal fer "el contrari" que l'altre jugador: si suma 7 restarem 2, i si en resta 2 sumarem 7. Hi ha un nombre clau amagat que marquen les solucions: van de cinc en cinc. El cinc s'obté dels nombres del joc 7-2. El 3 que inicia la sèrie tampoc és difícil de calcular: és el residu de dividir 23 entre 5.

Com aconseguir un nombre guanyador?

El problema ara és com aconseguir una d'aquestes quantitats. Una possibilitat és fer un diagrama en arbre de les possibles jugades i "netejar-lo" després per deixar només l'estratègia guanyadora. Fent-ho veurem que amb aquests nombres pot guanyar sempre el primer jugador (A) ja que pot assegurar-se arribar a 3 o a 13 i, a partir d'aquí, aplicar el que hem vist: fer la jugada contrària a l'altre. Les línies vermelles indica que són jugades obligades.

Tornem al joc original

Apliquem el nostre anàlisi al problema original (-2, +53,  de 0 a 2017). El "nombre clau" serà 51 (53-2). El primer nombre guanyador serà 28 (el residu de dividir 2017 entre 51). Aquest nombre ens permet obtenir la resta de la sèrie de nombres guanyadors: 28 - 79 - 130 - 181.... 1915 - 1966. El primer dels jugadors que assoleixi una d'aquestes quantitats (de la forma 51n+28) podrà guanyar la partida. Però quin dels dos la pot aconseguir primer? Com? No sembla que el diagrama en arbre ens pugui ajudar gaire ara. Haurem de canviar l'enfocament.

T'animes a seguir?

Per continuar el nostre anàlisi tornem a plantejar una reducció del joc. Les tirades possibles seran -3 i +8. L'objectiu serà aconseguir 37. Amb el que sabem ja podem deduir que els nombres guanyadors són de la forma 5n+2 (el 5 ve de 8-3 i el 2 és el residu de 37/5): 2, 7, 12, 17, 22, 27 i 31

• Quins nombres podem aconseguir a cada jugada?

Mirem.ho. La primera jugada per al primer jugador (A) és obligatòria: +8. A la següent jugada el segon jugador podrà restar 3 o sumar 8, per tant es podran aconseguir 5 o 16. Cap d'aquestes és una quantitat guanyadora. A la següent jugada A podrà obtenir 2, 13 o 24. Ep! Ja tenim un dels nombres guanyadors, però aquest només l'aconseguirà el primer jugador si la jugada inicial de B és restar 3... i potser no ho farà si sap que pot perdre. Podem fer una taula amb més jugades i veure totes les quantitats assolibles per cada jugador durant el joc. Podrem veure també que els moviments possibles queden representats a la taula: anar a la casella immediatament inferior serà equivalent a restar 3 i anar a la inferior dreta serà el mateix que sumar 8.

Aclarim el codi de colors de les caselles

• Grises. Jugades possibles d'A
• Blanques. Jugades possibles de B
• Vermelles. Jugades prohibides per que passen dels límits.
• Negres. Jugades no accessibles.
• Grogues. Nombres guanyadors per al jugador A
• Verdes. Nombres guanyadors per al jugador B

Aquesta taula ens proporciona una imatge interessant. Les caselles guanyadores formen una mena de línia, una"barrera".

• Com podem arribar a una casella guanyadora?

En aquest cas l'estratègia guanyadora és per A. L'únic que ha de fer és anar empenyent a B cap a aquesta línia "barrera". De fet, s'ha de limitar a anar restant 3 fins assolir-ne una de les cel·les guanyadores i, a partir d'aquest moment, fer l'acció contrària de B fins arribar a 37. El fet de que no es pugui sobrepassar el límit  de 37 és el que farà que, en algun moment, B es vegi obligat a anar baixant fins que A pugui assolir un dels nombres guanyadors. També podem veure que B té alguns nombres guanyadors (2, 7 i 32) però seran inassolibles si A juga perfectament.

A continuació tenim un exemple de partida en la que A aconsegueix el nombre guanyador 27 encara que B va intentant separar a A d'aquests nombres. Les fletxes vermelles representen els moviments de B i les blaves els d'A.

• Com podem aplicar l'estudi al joc original (-2, +53, de 0 a 2017)

Part de l'anàlisi ja l'havíem fet. Teníem els nombres guanyadors:

28 - 79 - 130 - 181 - 232 ... 1915 - 1966 - 2017 (51n+28)

Si fem una taula semblant a l'anterior podrem observar que la línia "barrera" és accessible, en primer lloc, per al primer jugador (caselles grogues). 

Per tant l'estratègia per a A serà la mateixa d'abans: anar "baixant" (restant 2) fins assolir una de les cel·les guanyadores. Convindrà, perquè la partida pot ser llarga, tenir la llista de nombres a mà. O si no mirar que si li resto 28 sigui divisible per 51, com es pot deduir de la fórmula general dels nombres guanyadors.

Generalitzem el joc mirant taules

La taula anterior està construïda amb un full de càlcul que resol automàticament diferents casos i assenyala les caselles guanyadores per tots dos jugadors. Encara que no està molt acabat el podeu descarregar en aquest enllaç. Veiem-ne algunes taules de jocs diferents i que donen resultats amb algun detall per observar:

• -4, +9, de 0 a 23

Guanya B sumant 9 a la primera jugada

• -2, +15, de 0 a 41

Guanya A des del principi

• -3, +9, de 0 a 23

No guanya ningú, el 23 no es pot assolir

• -2, +17, de 0 a 18

Pseudojoc: B guanya senzillament seguint jugades obligades

Generalitzem el joc fent càlculs

Si no volem anar fent taules també podem esbrinar "el mapa" guanyador fent només alguns càlculs.

Com he pogut veure a les taules anteriors el que ens interessa és esbrinar qui por trobar primer la línia "barrera".  Per això ens basta trobar el primer nombre guanyador abastable, ja que el següent sempre queda desplaçat una columna i dues files més avall.

Podem construir un sistema de coordenades que ens indiqui la situació de cada casella. Per exemple indicant en primer lloc la columna i, en segon lloc, la fila que ocupa en aquella columna. La primera fila de cada columna la numerarem amb el zero.

D'aquesta manera podem observar que les coordenades abastables pel jugador B estan formades sempre per dos nombres parells o dos nombres senars. En canvi les coordenades assolibles per a A estan formades sempre per un parell i un senar. De què ens servirà això? Si trobem les coordenades del primer nombre guanyador observant la seva paritat sabrem si l'estratègia és per a A o per a B. Observem alguns exemples pas a pas.

Primera prova: -4, +11, de 0 a 59

1. En primer lloc obtenim una llista de nombres guanyadors de la forma que ja sabem (11-4=7; residu de 59/7 = 3; sèrie de nombres 7n+3: 3, 10, 17, 24...)
2. Analitzem la 1a columna que començarà per 11 (jugada obligaria d'A) per veure si es pot assolir alguns dels nombres guanyadors més petits, en el nostre cas 3 o 10. Per saber-ho restem 11 del nombre guanyador, per saber la distància, i la dividim per 4 per saber si podem arribar en una quantitat exacta de restes.
   
   11-10 = 1; 1 no és divisible per 4
   11- 3 = 8; 8/4 = 2
3. Hem observat que es pot assolir el primer nombre guanyador (3) a la columna 1. De no haver trobat cap nombre hauríem de passar a la següent columna que començaria per 22 (2·11), però no és el cas. La fila ens la indica el quocient de la divisió: 2. Per tant el primer nombre guanyador està a la casella (1, 2). Les caselles senar-parell són accessibles per a A i l'estratègia guanyadora és per a ell. Ho podem visualitzar amb la taula corresponent.

Segona prova: -5, +12, de 0 a 81

• 12-5=7; 81/7 r: 4; sèrie 7n+4 → 4, 11, 18, 25, 32... 
• Columna 1: 12-11=1 (no divisible per 5); 12-4=8 (no divisible per 5)
  Columna 2: 24-18=6 (no divisible per 5); 24-11=13 (no divisible per 5), 24-4=20 (20/5=4)
• Tenim que el primer nombre guanyador tindrà com a coordenades (2, 4). En ser parell-parell l'estratègia guanyadora serà per a B.

Tercera prova: -4, +13, de 0 a 57

Aquest cas ens farà veure una situació especial

1. 13-4=9; 57/9 r: 3; sèrie 9n+3 → 3, 12, 21, 30, 39...
2. Columna 1: 13-12=1 (no divisible per 4); 13-3=10 (no divisible per 4)
   Columna 2: 26-21=5 (no divisible per 4); 26-12=14 (no divisible per 4); 26-3=23 (no divisible per 4)
   Columna 3: 39-39=0 (0/4=0). Ja tenim una casella (3, 0) però cal continuar mirant. 39-30=9 (no divisible per 4); 39-21=18 (no divisible per 4); 39-12=27 (no divisible per 4); 39-3=36 (36/4=9). Tenim un segona casella guanyadora, la (3, 9)
3. La casella (3, 0), senar-parell, és d'A. La casella (3, 9), senar-senar, és de B. En casos com aquest, l'estratègia guanyadora és per la casella més baixa i B seria el possessor d'aquesta. La raó la podem veure mirant el gràfic de la taula. No podem obligar a anar cap a la "barrera" superior de color groc, però, gràcies a que no es pot sobrepassar el 57 sí que podem forçar a anar a la"barrera" inferior de color verd.

Però sempre hi ha excepcions. Aquesta excepció és un cas com el que es produeix amb -3, +8, de 0 a 41. A la segona columna B té una casella guanyadora (2, 0) i A té la (2, 5). Com que a la (2, 0) es pot arribar en el primer moviment l'estratègia serà per a B.

És possible que fent més proves, però, es trobin altres casos en que calgui modificar un pèl la regla. De moment... no n'he trobat gaires més.

Trobar nombres guanyadors i coordenades amb GeoGebra

A més del full de càlcul el GeoGebra també ens pot servir d'ajuda per trobar les coordenades dels primers nombres guanyadors que ens indicaran si l'estratègia és per a A o per a B. Ja en el títol de l'article hem destacat el caràcter diofàntic del joc. No és difícil pensar que, associada al problema original olímpic, estava una de les possibles solucions de l'equació diofàntica:

53x - 2y = 2017

La primera versió reduïda en la que hem il·lustrat una possible partida (-3, +8, de 0 a 37) seria la solució particular x=8 i y=9 de l'equació 8x - 3y = 37. Vuit moviments en diagonal (de suma) i nou cap avall (de resta).

Es pot veure la relació entre les taules construïdes amb full de càlcul. La x es correspon amb a columna (la primera coordenada d'una casella) i la y amb la fila corresponent a aquella columna (la segona coordenada). Per tant, si trobem les primeres solucions enteres positives de les equacions associades a cada nombre guanyador tindrem també les coordenades d'aquestes caselles.

Observem un exemple per a -4, +11, de 0 a 58. Els primers nombres guanyadors seran 2, 9, 16, 23, etc. Nombres de la forma  7n+2.  Les "caselles guanyadores" vindran marcades per les solucions enteres positives de l'equació

11x - 4y = 7n +2

En general si a la solució més baixa x i y són les dues parells o les dues senars l'estratègia serà per a A i si tenen paritat diferent per a B. Trobar les diferents solucions pot ser una mica pesat i, a més, quedaran lligades a dos paràmetres a i b. Les solucions generals, en aquest cas, serien x=a; y=a+7b+3 i n=a-4b-2. Clar que podem limitar els valors dels paràmetres per no fer tantes proves, però també podem tirar de GeoGebra.

Per fer-ho podem representar diferents equacions: una per a cada valor guanyador. No cal fer-los tots, amb uns quants normalment en tindrem prou:

11x - 4y = 2

11x - 4y = 9

11x - 4y = 16

11x - 4y = 23

...

A continuació representem les rectes de cada equació amb ajut del Geogebra i mirem les coordenades dels punts de cada recta per a x=1, que es correspondria als nombres de la primera columna.

Podem observar que el valor de la y no és, en cap cas, un enter positiu. Per tant no tenim solucions per a la primera columna.

Mirarem ara el valors per a x=2.

Observem que tenim la primera solució amb les condicions esperades: (2, 5). Al tenir diferent paritat sabem que l'estratègia és per a A i que només li caldrà anar restant quatres fins arribar a un dels números guanyadors per, a partir d'aquell moment, fer el contrari que B. podem comprovar el que hem observat a la taula corresponent.

A continuació teniu la construcció en GeoGebra per experimentar.

Enllaç a la construcció GeoGebra

Sempre té solució el joc?

Hem vist ja un cas (-3, +9, de 0 a 23) que no tenia solució. La qüestió de si té solució o no està lligada a la naturalesa diofàntica de l'equació associada. En general el joc tindrà solució, és a dir, estratègia guanyadora per a un dels jugadors, quan l'equació que el representa té solució i aquestes equacions sempre tenen solució quan el nombre que es busca és múltiple del màxim comú divisor dels coeficients de la x i la y. Molts dels casos que hem presentat estaven triats de forma que els coeficients d'aquests termes fossin primers entre sí per tal de garantir la solució.

Però que l'equació tingui solució no garanteix que el joc en tingui. Un exemple senzill el tenim en el cas -3, +11, de 0 a 12. L'equació 11x - 3y = 12 té infinites solucions, per exemple, x=3 i y=7, però cap d'elles es pot obtenir, pas a pas, sense sobrepassar els límits 0 i 12 com imposa el joc. Mirant la taula de joc és molt fàcil d'observar que les columnes queden desconnectades. Només són possibles les restes i durant tres jugades.

Per tant, estar convençuts de que hi ha solucions vàlides és un problema més complex del que sembla. Deixem aquest problema obert per a una altra ocasió.

I a l'aula?

• A primària el podem jugar senzillament per practicar sumes i restes. Potser al cicle superior es pot buscar l'estratègia guanyadora per a nombres senzills.
• A mesura que avancem en edat podem anar complicant els nombres per arribar, al final de la secundària o al batxillerat a buscar l'estratègia general del joc.
• En alguns casos senzill, amb nombres no massa grans, es pot programar el joc amb Scratch incloent l'estratègia guanyadora. A continuació teniu un model que pot servir de punt de partida. Per exemple, espot millorar perquè pugui començar qualsevol dels jugadors o perquè es pugui jugar amb altres nombres.

• Si les investigacions van pels camins que hem seguit pot ser un bon exercici construir fulls de càlcul com els que hem fet servir a les imatges presentades. És una bona opció per treballar amb fórmules, formats condicionals... També es pot fer una construcció en GeoGebra similar a la nostra i que permeti, amb els punts lliscants, estudiar diferents possibilitats de joc.
• I un altre tema pendent. En molts jocs d'estratègia existeix una estratègia guanyadora per un dels dos jugadors. Normalment són perquè un dels dos jugadors pugui guanyar o, com a mínim. fer taules. També habitualment si un dels jugadors no coneix l'estratègia o s'equivoca l'altre es por apoderar d'aquesta. Pot donar-se que l'estratègia sigui per a A però que, si en un moment, no fa la jugada correcta, B pugui fer la jugada que no havia fet A i, continuant aplicant bé l'estratègia que fins aquell moment era d'A, acabi guanyant la partida. En aquest joc, com pot actuar un jugador quan l'altre no ha aplicat l'estratègia correcta? No és un tema molt clar. Hi ha vegades que un dels jugadors té impossible aconseguir el número objectiu. Per exemple amb les condicions -2, +10, de 0 a 27 cap dels jugadors pot assolir el nombre objectiu i amb -3, +11, de 0 a 30  A no pot assolir mai el nombre objectiu perquè només pot aconseguir resultats senars en cada jugada (mirar imatge). Una investigació colateral interessant és investigar com ha d'actuar el jugador que inicialment no té l'estratègia guanyadora.