El problema de Les granotes i els gripaus Richard Guy s’ha convertit en un clàssic dels jocs de recreació matemàtica. Va ser inventat pel matemàtic anglès, que el va publicar al llibre Winning Ways for Your Mathematical Plays (1982), coescrit amb Elwyn R. Berlekamp i John H. Conway.
| Índex | ||||
| Les regles | Estratègia | Comptem els moviments | Solucions | Activitat en pdf |
| Les regles del joc |
El problema general es planteja sobre un tauler fet per una filera de caselles, amb una quantitat qualsevol granotes, a un costat, i una altra quantitat de gripaus, no necessàriament igual, a l’altre cantó. Les granotes i els gripaus estan separats per una casella buida.
L’objectiu és intercanviar les posicions de les granotes i els gripaus. Passar els que estaven a la dreta cap a l’esquerra i els de l’esquerra a la dreta.
Només hi ha dos moviments legals:
- Avançar una casella (aquest moviment l’anomenarem “lliscament”).
- Saltar per sobre d’un animal de l’altre tipus, si la casella immediata de darrere és buida, i ocupant aquesta. És un salt com el d’una fitxa normal del joc de les Dames.
Ja hem dit que el nombre de granotes i de gripaus pot variar. Inicialment, proposem que intentis solucionar el problema amb 3 granotes i 3 gripaus, tal com està plantejat a l’esquema anterior.
Si no has pogut solucionar el problema aquí tens una resolució.
Quan ho hagis fet, pots provar amb cinc granotes i cinc gripaus o amb dues granotes i cinc gripaus.
| Busquem una estratègia general |
El problema es torna més interessant si intentem la recerca d’una estratègia general per a qualsevol quantitat de granotes i de gripaus.
Hem d’investigar els moviments que porten a situacions de bloqueig i diferenciar-los dels que permeten continuar progressant en el joc. Pots tenir en compte algunes orientacions:
- Normalment, en cada situació només tenim una o dues opcions de moviment. Si en tenim una no podem triar. Però si en tenim dues, no és difícil preveure la situació que es pot produir una o dues jugades després.
- Cal evitar quedar-se bloquejat. Una granota està bloquejada si té dos gripaus junts al davant o si té una altra granota a la casella següent. Podem dir una cosa similar, fent una adaptació convenient, per als gripaus.
- Si vas evitant bloquejos, previsibles en una o dues jugades, no és difícil resoldre el joc.
- Si analitzes la solució amb diferents quantitats de granotes i gripaus, veuràs que hi ha una posició clau que cal aconseguir.
Mirem-ho amb els primers moviments. Si comencem fent avançar una granota, després tindrem dues opcions: avançar-ne una altra o fer saltar un gripau. No és difícil veure que la primera opció porta a un bloqueig. Per tant, farem l’altre moviment.
Podem mirar que pel següent moviment tornem a tenir dues opcions. Però una d’elles porta a un bloqueig en dues jugades, perquè fa ajuntar dues granotes o dos gripaus.
D’aquesta manera, podem continuar analitzant cada jugada.
| Comptem els moviments |
Una qüestió interessant és estudiar quina és la quantitat de moviments mínima per intercanviar una quantitat qualsevol de granotes i gripaus.
Per a practicar, canviant les quantitats de granotes i gripaus, tens un aplicatiu al web d’NRICH.
Una bona pista per esbrinar-ho és estudiar diferents casos i comptar per separat els lliscaments i els salts. Et pot ajudar completar aquestes taules de doble entrada. Les files representen diferents quantitats de granotes i les columnes diferents quantitats de gripaus.
Si observes com es va formant la taula no trigaràs a observar quina és la pauta per endevinar la quantitat de moviments necessaris per a una quantitat G de granotes i una S de gripaus. Intenta escriure una fórmula.
És una mica més entretingut justificar aquesta fórmula. Per fer-ho, has de pensar en algunes qüestions com aquestes:
- Quantes caselles ha d’avançar cada granota per ocupar el lloc final?
- Quantes caselles han d’avançar totes les granotes?
- I cada gripau?
- I tots els gripaus?
Si tot fossin “lliscaments” ja ho tindríem, però els salts descompten moviments.
- Quantes granotes ha de saltar cada gripau?
- Quants salts es produeixen en total?