Sis granotes instruïdes

És molt conegut el problema de Les granotes i els gripaus inventat l'any 1982 per Richard Guy. És una activitat que combina joc i investigació i que es pot portar a l'aula des de finals de primària fins a qualsevol curs de l'ESO. Ja fa molts anys que la vam incorporar al web del Calaix +ie. El joc inicial es juga sobre un tauler de set caselles amb tres fitxes d'un color (les granotes) i altres tres d'un altre color (els gripaus) . L'objectiu és intercanviar les fitxes de posició tenint en compte que només poden avançar, cada color en un sentit, desplaçant-se a una casella immediata buida o saltant per sobre d'una fitxa d'un altre color si la casella següent està lliure, com al joc de dames. La investigació posterior es fa per a estudiar els moviments mínims necessaris per a itercanviar m granotes i n gripaus.

Ara proposem una investigació que la recorda, però que té algunes diferències importants. El problema el va presentar Henry Dudeney al seu llibre Amusements in Mathematics el 1917. El text original deia:

"Les sis granotes instruïdes de la il·lustració estan entrenades per invertir el seu ordre, de manera que els seus números es llegeixin 6, 5, 4, 3, 2, 1, amb el quadrat en blanc en la seva posició actual. Poden saltar a la següent casella (si està buida) o saltar per sobre d'una granota fins a la següent casella més enllà (si està buida), de la mateixa manera que ens movem en el joc de dames, i poden anar cap enrere o endavant a gust. Pots mostrar com fan la seva gesta en el menor nombre de moviments possibles? És bastant fàcil, així que quan ho hàgiu fet, afegiu una setena granota a la dreta i torneu-ho a provar. A continuació, afegiu més granotes fins que pugueu donar la solució més curta per a qualsevol nombre. Perquè sempre es pot fer, amb aquella única plaça buida, per moltes granotes que hi hagi."

Per tant, comencem amb les granotes estan en ordre creixent d'esquerra a dreta i amb la casella de l'esquerra buida i hem d'invertir l'ordre inicial deixant de nou la casella esquerra buida. I poden anar cap endavant i cap endarrere.

Aquest joc el podem representar molt bé amb targetes numèriques, nombres retallats o cartes de la baralla.

Podeu intentar resoldre'l també amb aquest aplicatiu. Però atenció, Dudeney diu que és fàcil trobar el mínim de moviments. No és del tot cert. Resoldre el problema no és difícil, però trobar la quantitat mínima de moviments costa una mica més. Especialment si no sabem quina és aquesta quantitat.

Enllaç al programa

A continuació analitzarem el problema i veurem que té aspectes interessants per trobar la forma de calcular la quantitat mínima de moviments i per descriure la resolució també mínima.

Continuem?

Abans de seguir una informacií: la quantitat mínima de moviments per a sis granotes és de 21. Si encara no voleu mirar la solució us donarem una pista amb una posició intermèdia:

Posició en 12 moviments: parells i senars separats (amb el més petit al mig)

Per arribar a la solució detallada del joc per a sis granotes, farem l'estudi amb menys granotes. Mirarem amb detall els casos amb una quantitat parell de granotes, en què és més fàcil detectar regularitats de resolució i de càlcul de moviments. Els casos senars els deixarem pel final i només plantejats;  enllaçarem a un document on s'estudien.

Quantitats parells de granotes

Si voleu investigar abans de començar a llegir, a continuació teniu un aplicatiu que us permetrà experimentar pel vostre compte amb 2, 4, 6 8 o 10 granotes..

Enllaç al programa

Quan busquem regularitats, del tipus que siguin, convé començar pels casos senzills. I el cas més senzill és de dues granotes.

• Dues granotes

Amb poques proves és molt fàcil trobar les dues solucions:

3 moviments (2 lliscaments i 1 salt)

• Quatre granotes

Quatre encara són poques granotes, per assaig i millora, no és difícil trobar alguna solució de només 10 moviments. Les quatre que mostrem tenen 4 lliscaments i 6 salts. Indiquem aquests últims en negreta.

1) 2-1-3-4-1-2-3-4-2-3
2) 2-3-1-2-3-4-1-2-4-3
3) 2-4-3-1-2-4-3-1-2-4
4) 1-3-4-2-1-3-4-2-1-3

Després d'aquesta experimentació, podem començar a intuir algunes idees generals i a fer algunes observacions que, potser, ens seran útils amb més granotes:

• És millor fer salts que lliscaments perquè es redueixen moviments.
• Va fer crear forats prop als extrems que permetin encadenar salts.
• La quantitat de lliscaments sembla coincidir amb la de granotes (ho hem vist en els dos casos: 2 i 4 granotes).
• Les solucions mostren un cert ritme de salts i lliscaments. Les dues primeres són dos cicles SLSLS, la tercera són dos cicles SSLSLi la quarta dos LSLSS.
• La tercera solució sembla tenir una certa regularitat numèrica. Fa dos cicles 2-4-3-1 i tanca amb un 2-4
• Si fem "fotografies" de situacions intermèdies de les resolucions veurem que sembla ser interessant anar acumulant granotes juntes a cada costat (deixar la casella buida als extrems). La primera i la segona solució semblen tenir una certa simetria. En la tercera hi ha una oscil·lació clara "esquerra-dreta-esquerra..."

• Sis granotes

Experimentant una mica amb aquestes idees, i després d'unes quantes proves, podem arribar a trobar algunes solucions de 21 moviments (6 lliscaments i 15 salts) per al cas de sis granotes:

1) 2-1-3-5-6-4-1-2-3-5-6-4-1-2-3-5-6-4-2-3-5
2) 2-4-5-3-1-2-4-5-6-3-1-2-4-5-6-3-1-2-4-6-5
3) 2-4-6-5-3-1-2-4-6-5-3-1-2-4-6-5-3-1-2-4-6
4) 1-3-5-6-4-2-1-3-5-6-4-2-1-3-5-6-4-2-1-3-5

La idea de pes més utilitzada és la de la basculació cap a cada costat i el salt entrellaçat. Ho podem veure molt clarament en la imatge de moments intermedis de la tercera solució proposada.

Tenir solucions noves confirma alguna de les conjectures que havíem fet, però obre de noves. També ens permet fer conjectures de cara a la cerca de solucions pels casos de vuit i deu granotes.

• Quantitat de moviments

Com és habitual en aquetes recerques, organitzar les dades en una taula ajuda a trobar pautes.

Granotes	Lliscaments	Salts	Total
2	2	1	3
4	4	6	10
6	6	15	21

• Lliscaments

Sembla confirmar-se que la quantitat de lliscaments coincideix amb la quantitat de granotes. Si observem les solucions veurem que cada granota llisca una sola vegada. Podem veure el perquè si pintem alternadament les caselles del tauler. Veurem que les granotes que estan a una casella blanca acaben a una de blava i les que estaven a una de blava acaben a una blanca. Per canviar de color t'has de desplaçar, com a mínim, una casella ja que, en saltar, no es canvia de color. La conjectura té sentit.

• Salts

Per a dues granotes només hi ha un salt. Per a quatre són 6 salts i per a sis granotes en són 15. La sèrie 1, 6, 15, ens convida a seguir-la de diferents formes. Per exemple, la tenim a la sisena línia del triangle aritmètic. Continuaria amb 20, però no és un bon candidat perquè en el triangle aritmètic tornem a baixar i la nostra sèrie, a mesura que augment granotes, ha de ser sempre creixent. Una tècnica habitual, encara que amb tres casos és força agosarada, és estudiar les primeres i segones diferències. Si ho fem podem preveure 28 salts per a 8 granotes i 45 per a 10.

Però podem fer una altra observació. Si anotem, per a cada quantitat de granotes, com es salten entre elles, veurem que es salten entre si només una vegada. Per exemple, si la granota 2 salta a la 5 no la tornarà a saltar. I la 5 tampoc saltarà a la 2.

El nombre indica en número de moviment del salt

Per tant, la quantitat de salts coincideix amb la quantitat de parelles de granotes que puguem fer:

Aquesta fórmula confirma la quantitat de salts previstos per a 8 i 10 granotes.

• Total de moviments

Si recordem que hi ha tants lliscaments (n) com granotes, només en cal sumar les dues quantitats i simplificar.

• Vuit i deu granotes.

Tenim una idea ja de la quantitat de moviments mínims. Fins i tot, en detall, la quantitat de lliscaments i salts. També tenim una estratègia de basculació esquerra-dreta que ens permet fer temptejos una mica més orientats. Però podem explorar altres idees per buscar solucions. Per exemple, trobar patrons de de seqüències repetides de salts i lliscaments. Per exemple, si mirem les terceres solucions de 4 i 6 granotes podem veure un patró que ens permet conjecturar les seqüències per a 8 i 10 granotes. Observem que són cicles d'n+1 moviments que es repeteixen n/2 vegades.

Granotes	Salts	Lliscaments	Salts	Lliscaments	Repeticions del cicle
4	2	1	1	1	2
6	3	1	2	1	3
8	4	1	3	1	4
10	5	1	4	1	5

Aquestes observacions porten a una solució per a cada cas:

• 8 granotes. 36 moviments (8 lliscaments i 28 salts)
  2-4-6-8-7-5-3-1-2-4-6-8-7-5-3-1-2-4-6-8-7-5-3-1-2-4-6-8-7-5-3-1-2-4-6-8
• 10 granotes. 55 moviments (10 lliscaments i 45 salts)
  2-4-6-8-10-9-7-5-3-1-2-4-6-8-10-9-7-5-3-1-2-4-6-8-10-9-7-5-3-1-2-4-6-8-10-9-7-5-3-1-2-4-6-8-10-9-7-5-3-1-2-4-6-8-10

També les segones solucions de 4 i 6 ens donen un altre patró..

Granotes	Salts	Lliscaments	Salts	Lliscaments	Salts	Repeticions del cicle
4	1	1	1	1	1	2
6	2	1	2	1	1	3
8	3	1	3	1	1	4
10	4	1	4	1	1	5

Aquest segon patró aporta les següents solucions:

• 8 granotes. 36 moviments (8 lliscaments i 28 salts)
  2-4-6-7-5-3-1-2-4-6-7-8-5-3-1-2-4-6-7-8-5-3-1-2-4-6-7-8-5-3-1-2-4-6-8-7
• 10 granotes. 55 moviments (10 lliscaments i 45 salts)
  2-4-6-8-9-7-5-3-1-2-4-6-8-9-10-7-5-3-1-2-4-6-8-9-10-7-5-3-1-2-4-6-8-9-10-7-5-3-1-2-4-6-8-9-10-7-5-3-1-2-4-6-8-10-9
  

Però tenim altres opcions per a aconseguir el reordenament de formes diferents. Mantenint la idea de la basculació podem provar uns primers moviments diferents. Per exemple

• Si el 1r moviment és 1 el segon 3 tenim:

• 8 granotes. 36 moviments (8 lliscaments i 28 salts)
  1-3-5-7-8-4-6-2-1-3-5-7-8-4-6-2-1-3-5-7-8-4-6-2-1-3-5-7-8-4-6-2-1-3-5-7
• 10 granotes. 55 moviments (10 lliscaments i 45 salts)
  1-3-5-7-9-10-8-6-4-2-1-3-5-7-9-10-8-6-4-2-1-3-5-7-9-10-8-6-4-2-1-3-5-7-9-10-8-6-4-2-1-3-5-7-9-10-8-6-4-2-1-3-5-7-9

• Si el 1r moviment és 2 el segon 1 tenim:

• 8 granotes. 36 moviments (8 lliscaments i 28 salts)
  2-1-3-5-7-8-6-4-1-2-3-5-7-8-6-4-1-2-3-5-7-8-6-4-1-2-3-5-7-8-6-4-2-3-5-7
• 10 granotes. 55 moviments (10 lliscaments i 45 salts)
  2-1-3-5-7-9-8-6-4-1-23-5... Us la deixem descobrir la continuació.

Resumim els casos parells

Hem descobert la quantitat mínima de moviments per a una quantitat n de granotes

Per altra banda, tenim una estratègia general de basculació i maximització els salts, si és possible fent-los encadenats. Aquesta estratègia no és pròpiament un algoritme perquè no hem precisat què fer exactament a cada pas. Però, estant atents a cada situació és perfectament aplicable a quantitats parells de granotes.

Dudeney, que només exemplificava un tipus de solució per a cada cas, sí que l'explicava en forma d'algoritme:

1. Es mouen les granotes parells en ordre ascendent: 2-4-6...
2. A continuació es mouen les granotes senars en ordre descendent: Si són 8 serà 7-5-3-1
3. Es reprodeueix aquest cicle n/2 vegades
4. S'acaba movent les granotes parells en ordre ascendent

De dues a vuit granotes les solucions serien aquestes:

Casos parells	Moviments
2	(2) (1) (2)
4	(2-4) (3-1) (2-4)
6	(2-4-6) (5-3-1) (2-4-6) (5-3-1) (2-4-6) (5-3-1) (2-4-6)
6	(2-4-6-8) (7-5-3-1) (2-4-6-8) (7-5-3-1) (2-4-6-8) (7-5-3-1) (2-4-6-8) (7-5-3-1) (2-4-6-8)

Dudeney no va comentar que l'algoritme simètric, moure primer els senars en ordre ascendent, i després els parells, en ordre descendent, també funciona.

Quantitat senar de granotes

A continuació us enllacem un aplicatiu que us permetrà jugar amb 3, 5, 7 i 9 granotes. Alguns dels principis que hem descobert pels casos parells ens poden ser útils, però els haurem d'adaptar.

Enllaç al programa

 Us mostrem una taula amb els moviments mínims per si voleu estudiar com esbrinar-los per a una quantitat senar n de granotes.

Granotes	Lliscaments	Salts	Total
3	2	3	5
5	6	10	16
7	10	21	31
9	14	36	50

 En aquest document trobareu un anàlisi més detallat del problema.

I a l'aula?

• En principi és recomanable haver treballat abans el problema de Les granotes i els gripaus. Al tenir les fitxes un sol sentit de moviment és més fàcil de trobar la quantitat mínima de moviments i l'estratègia general de resolució. També la generalització sobre el càlcul de la quantitat total de moviments, si més no en el cas dels salts, és més evident. També ho és la justificació general. Però si en algun curs l'han treballat ja, aquesta és una bona modificació per a cursos posteriors. No és imprescindible fer-ho així, perquè són problemes independents, però és recomanable.
• També, a priori, segurament és millor plantejar només el cas de quantitats parells de granotes. Cal insistir en que el problema no és difícil de solucionar. Per exemple, portant les granotes per ordre (la 1, la 2, etc.) al seu lloc. Però trobar la quantitat mínima a partir de sis granotes, és més costós. Potser, en algun moment, pot ser aconsellable explicitar quina és aquesta quantitat mínima. En tot cas, un "atac col·lectiu" col·laboratiu entre tota la classe pot ajudar a trobar aquest mínim. Es poden donar també pistes, o recollir observacions d'alumnes: "És millor saltar que lliscar", "És bo encadenar salts", "I com ho fem per encadenar-los?"
• Abans d'atacar generalitzacions a 8 o més granotes convé aturar-se a mirar què hem fet amb 2 i 4, per observar patrons.
• Justificar el càlcul de salts i lliscaments (que des d'un principi convé separar) tampoc és evident. La pista del canvi de color de les caselles pot ajudar a fer veure que cada granota ha de fer un lliscament com a mínim. El càlcul de salts (de parelles) és un bonic i clàssic problema de combinatòria. En tot cas, revisar quines fitxes salten a quines pot ajudar. De la mateixa forma, anotar quines fitxes llisquen (per veure que cadascuna ho fa una sola vegada).