Les granotes i els gripaus

Una petita investigació sobre un clàssic problema d'entreteniments matemàtics

Les granotes i els gripaus

 

El trencaclosques de les granotes i els gripaus és un del problemes més clàssics de la matemàtica recreativa.

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.

 

Posició inicial

gripau gripau gripau j granota granota granota

 

Posició final

granota granota granota j gripau gripau gripau

 

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 darrera és buida, 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. Després pots practicar amb altres quantitats.

Per poder jugar clica sobre aquesta granota:

Anar al joc

Si no has trobat cap solució pots trobar una aquí.

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 o de gripaus.

Hem d'investigar els moviments que porten a situacions de bloqueig i diferenciar-los dels que permeten continuar progressant en el joc.

Practica una mica amb diferents quantitats de granotes i gripaus i intenta descriure un mètode de resolució.

 

Per tornar a jugar clica sobre un altre cop sobre la granota:

Anar al joc

Si no has trobat una estratègia òptima aquí en pots trobar una.

 

Comptem els moviments



Una qüestió interessant és estudiar quina és la quantitat de moviments mínima per intercanviat una quantitat qualsevol de granotes i gripaus.

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

LLiscaments
  1 2 3 4 5
1

2

       
2          
3    

6

   
4          
5          
Salts
  1 2 3 4 5
1

1

       
2          
3    

9

   
4          
5          
Total
  1 2 3 4 5
1

3

       
2          
3    

15

   
4          
5          

Si observes com es va formant la taula no trigaràs en 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.

Tot i així é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?

Si no has trobat cap fórmula o no saps justificar-la clica aquí.