Amb el títol de Tot sumant, al novembre del 2013, vaig publicar un article en aquest blog en el que es plantejava un problema d'itineraris additius per una quadrícula. M'agradaria reprendre'l ara per estudiar-lo més àmpliament. Al passat C2EM va ser una de les activitats proposades pel Cesire de Matemàtiques al "taller virtual" Laboratori de matemàtiques i la participació de la gent va ser força animada. De fet el taller va generar algun correu, que després comentaré, i és el que ha promogut aquesta revisió ampliada.
El problema original, que vaig conèixer per un llibre de Fernando Corbalán i amb el nom de L'ascensor (Matemáticas de la vida misma, Ed. Graó, p. 40), és el següent: fer un recorregut per una quadrícula de 3x3 de la següent manera:
- comencem a qualsevol casella posant un 1.
- passem a una casella contigua, en vertical, horitzontal o diagonal, i escrivim el nombre que correspongui a la suma de totes les caselles del voltant, ja toquin per un costat o per un vèrtex.
- continuem fent un recorregut continu que, sense salts, completi tot el caseller.
L'objectiu és aconseguir el nombre més alt un cop completat el recorregut. Aquí teniu un exemple animat d'itinerari.
Si voleu podeu practicar amb aquest applet fet amb Scratch. Per a fer el recorregut cal anar clicant els punts blaus.
Quan fem aquesta activitat a l'aula convé saber quin és el màxim assolible per animar a l'alumnat a continuar provant si no l'han obtingut. O bé, per fer observar que hi deu haver alguna errada si diuen un resultat que el supera. Les errades habituals inicials són de càlcul o per no haver entès alguna de les regles del joc.
A continuació parlarem del correu que em van enviar i que proposava una màgica connexió entre problemes. Aquesta possible relació era d'obligatòria investigació i, a més, convidava a estudiar l'ampliació a quadrícules de 4x4 i 5x5. Però abans, us animo a practicar una mica aquest problema en aquests taulers més grans.
Us animeu a seguir les nostres exploracions?
El mateix dia que vam fer el taller vaig rebre un missatge de l'amic Guido Ramellini, un dels membres més actius del MMACA. En Guido té la virtut de veure sempre més lluny que jo. Serà perquè sempre camina, alegre, amb la mirada posada en l'horitzó de Galeano.
La connexió d'en Guido
D'entrada cal dir que en la quadrícula de 3x3 la suma màxima que s'obté és 44. En Guido em va enviar ràpidament una de les solucions possibles.
La sorpresa la vaig tenir al dia següent amb un missatge nou que, amb el seu permís, transcric.
"Em surt aquest camí d'Hamilton (lògic si només pots passar una vegada per cada casella) simètric, que comença per un vèrtex i acaba al vèrtex oposat i funciona en les dues direccions.Si codifiquem les línies ortogonals amb A i les obliqües amb S, tenim la seqüència: A,S,A,S,S,A,S,A, QUE ÉS LA SOLUCIÓ DE GRANOTES I GRIPAUS DE 2X2. (Simètric també per g i G). Vull dir: gra-Avança, GRI-Salta, GRi-avança, gra-Salta, gra-Salta, GRI-Avança, GRI-Salta, gra-Avança."
Situem. Quin és el problema de les Granotes i els Gripaus? Aquest problema el vam tractar fa molts anys al web del Calaix +ie i és força conegut. Podeu trobar l'activitat, i tot l'anàlisi, en aquest enllaç. El cas particular que comenta en Guido és com intercanviar les posicions de dues granotes (que avancen cap a la dreta) i dos gripaus (que avancen cap a l'esquerra) en un caseller com el de la imatge. Els moviments permesos són:
- avançar una casella.
- 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.
- no es pot retrocedir mai
Però abans de continuar ens hem de fer una altra pregunta. Amb 2x2 el màxim assolible és 4. Amb 3x3 és 44. Quin penseu que serà el màxim per 4x4? I per a 5x5? Només penseu un resultat aproximat per veure si els que obtindrem seran més grans, més petits o similars.
Continuem aplicant el "mètode Guido-Granotil" a 4x4 i 5x5.
Continuem aplicant el "mètode Guido-Granotil" a 4x4 i 5x5.
 |
| Per a 4x4 el màxim obtingut és 953 |
 |
| Per a 5x5 el màxim obtingut és 33805 |
Una observació, potser sorprenent, és que els resultats màxims són molt grans. Aquesta primera sorpresa la podem reduir si pensem en una altra sèrie additiva que creix molt ràpidament: la de Fibonacci.
 |
| Creixement comparat de la sèrie de Fibonacci i els de la solució de 5x5 d'en Guido |
Però, treballant en 4x4 vaig trobar un parell de solucions superiors a 953 que vaig enviar a en Guido. Una d'elles arribava a 1214. Però el "dibuix" de l'itinerari, que no respectava la "llei de les granotes", era molt més "lleig" i sense cap simetria.
La resposta d'en Guido no va trigar. Primer va modificar la meva solució lleugerament per arribar a 1244. Però després va recuperar l'itinerari granotil, tot renunciant a les simetries, i em va enviar una solució que millorava el màxim fins a 1395.
Sempre és més fàcil millorar un problema a partir d'un altra solució coneguda. Modificant una mica el seu itinerari (i abandonant "les granotes"), es pot arribar a un nombre millor en 468 unitats.
En tot cas, si anem mirant les darreres solucions, que van presentant una millora progressiva, comencem a veure algun esquema de per on ha d'anar la solució màxima de 4x4. I també veurem que, amb tota la pena del món, haurem d'abandonar la preciosa conjectura de les granotes. Hauria estat ben bonica de ser certa. En tot cas, és una conjectura que ens ha ajudat a caminar. Ha fet d'horitzó. Ara toca demanar noves ajudes per estudiar el problema.
Entra l'Enric Castellà al terreny de joc
L'amic Enric ja m'ha ajudat en molt dels problemes del darrers articles. A més de tenir una gran visió en la resolució de problemes s'ha convertit en el meu informàtic de capçalera. Si necessito un programa que no sé fer, li falta temps per dissenyar-lo. Haig de reconèixer que s'engresca fàcilment i no costa gens enredar-lo. Així que li vaig demanar si podia fer un programa que analitzés tots els casos per a 3x3, 4x4 i 5x5, ens trobés la solució màxima i totes les configuracions possibles.
La prova de foc la vam fer per confirmar el cas de 3x3 que teníem més estudiat. Efectivament la suma màxima era 44 i va obtenir 32 solucions diferents. Però si dibuixem els itineraris descobrirem que per girs, simetries o inversions (canviar l'inici pel final i viceversa) es poden reduir a tres solucions "base".
 |
| Les tres solucions "base" apareixen en color blau |
Què tenen en comú les tres solucions? Que divideixen el quadrat en tres zones:la diagonal i dos racons. Cada zona té tres caselles. Primer s'omple una zona, després es recorre la diagonal i, finalment, s'omple la tercera zona. Però, si ens hi fixem amb més detall, veurem que les tres solucions tenen una gran part del trajecte en comú. Només es diferencien en els dos quadrats inicials i els dos finals de l'itinerari.
 |
| Zones del tauler i part comuna de l'itinerari |
Servirà també pel cas de 4x4? Com s'haurà d'adaptar?
Ataquem el cas 4x4
Per a 4x4, amb el programa de l'Enric, vam descobrir que la solució màxima era 2473, millorant en 610 la nostra millor solució manual!
 |
| Exemple de solució màxima |
Podríem esperar una quantitat més gran de solucions que per a 3x3, però tornem a estar en 32.
 |
| Les 32 solucions sense classificar. Totes donen 2473. |
És un exercici interessant agrupar-les tenint en compte si són idèntiques al desfer girs, simetries o inversions. Quan ho fem, ens tornem a trobar que només hi ha tres solucions bàsiques.
 |
| Les tres solucions "base" apareixen en color blau |
I ens tornem a preguntar... què tenen en comú les diferents solucions? En primer lloc observem un moviment circular per quadrants (quadrats petits de 2x2).
 |
| La intensitat del color indica que els sumands es van fent més grans |
A més, com bé em va fer observar l'Enric, el recorregut pel 2n i 3r quadrants, per ordre d'itinerari, és simètric i no varia. De fet, com en el cas de 3x3, els tres recorreguts només es diferencien en les dues caselles inicials i les dues finals, la resta és idèntic. També veiem que s'intenta deixar els nombres més grans de cada quadrant a les zones "de frontera" amb el quadrant següent: a les parts més interiors.
Com veiem l'aspecte general del recorregut és ben diferent al de 3x3. Però tenim coses en comú, com que la part central de les solucions sigui igual. Potser caldrà investigar 5x5 per trobar un patró de recorregut.
5x5: encara obert
L'anàlisi de 5x5 és més complicat perquè la quantitat d'itineraris es dispara. El programa de l'Enric ha estat treballant 11 dies sense descans. Però l'hem hagut d'aturar, sense acabar, quan ja feia dies que no trobava solucions noves. La primera solució que va trobar era força gran i, ni de lluny, m'havia acostat amb les proves manuals.
 |
| D'aquesta solució, per gir, simetria o inversió, se'n deriven 15 més |
El programa n'ha trobat algunes més. De moment en tenim vuit, que hem pogut classificar en tres tipus i de les que derivem, per gir, simetria o inversió 15 més per a cada cas. Però observant les seves característiques n'hem trobat una més de bàsica i les seves 15 derivades. Fins ara en tenim 64. Però no tenim confirmat que sigui les màximes. Si tornem a fer funcionar el programa i apareix una de nova superior ja modificarem l'article. O refrendarem el resultat.
En tot cas, es veu també un sentit giratori en els itineraris i que primer es recorre un rectangle de 2x5 i, després, el de 3x5 que queda. També, com als casos anteriors, tot el recorregut és comú menys les dues caselles inicials i les dues finals. Aquí ja tenim clarament un patró. Una altra cosa és saber com és exactament aquest recorregut.
Finalment. com a curiositat, podem comparar el creixement d'aquesta sèrie amb la de Fibonacci. Ara sí que la supera, i molt, en creixement.
I a l'aula?
En quant a la cerca de resultats màxims, nosaltres hem recorregut a la programació. No és l'objectiu a l'aula, excepte en el cas de 3x3 que és assolible sense ser exhaustius en tots els casos. Sense descomptar per girs, simetries o inversions el programa a trobat 789 solucions completes (que recorren totes les caselles) per a 3x3, però per a 4x4 n'ha comptat 343 184. Per tant, en una primera proposta, es tractaria senzillament d'aconseguir la suma més gran del grup classe. Ja és molt. Però després podem presentar, per exemple, una de les solucions de 4x4 i veure si, amb petites modificacions, poden esbrinar les altres. Fins i tot, podem classificar-les per veure si s'arriba a obtenir la col·lecció completa i la detecció de les tres bàsiques. Si volem podem fer un treball similar amb 5x5, però aquí deixaria un temps llarg perquè l'alumnat anés provant a estones lliures per veure fins a quin màxim arriben.
I també podem investigar des del principi un cas intermedi: el rectangle de 3x4. i que ens genera un pont per observar patrons entre els casos de 3x3 i 4x4. Aquest pont és més abordable que el pas a 5x5.
Una altra tasca de possible interés és esbrinar, a partir de les solucions bàsiques, quantes solucions se'n deriven. Podem observar que de cada itinerari bàsic simètric, si admet el gir per ser una quadrícula quadrada, s'obtenen 8 casos. Si no es pot girar, per ser una quadricula rectangular, serien 4. I del recorregut no simètric, amb possibilitat de gir obtindríem 16 i, sense gir, 8. La diferència entre els casos simètrics i no simètrics és que, en els primers, les solucions per inversió (intercanviar el principi i el final) s'obtenen soles fent les simetries. En canvi, als recorreguts no simètrics no surten automàticament.
Per a les quadrícules quadrades, si anomenem S a la quantitat de recorreguts bàsics simètrics i N als no simètrics podem expressar la següent relació:
8·S + 16·N = Total de solucions
El problema invers, sabent la quantitat total de solucions esbrinar les bàsiques pot tenir més d'un resultat, ja que és una equació diofàntica on S i N han de ser nombres naturals o zero.
Pels dos casos de 32 solucions (el de 3x3 i 4x4) tenim que:
8S + 16N=32
S + 2N = 4
S = 4-2N
Donant valors a N les tres solucions vàlides són N=0 i S=4, N=1 i S=2 (que són els nostres casos) o bé N=2 i S=0.
Amb 3x4 el programa dona 16 solucions. No és una quadrícula quadrada. Quantes poden haver de bàsiques? (aquí teniu l'estudi)
Un regal final
L'Enric em permet compartir el codi del programa. Fins i tot convida a fer-ne millores per a accelerar la computació de casos. Aquest codi permet canviar les dimensions del caseller. Us animeu a treballar-hi?
Cap comentari:
Publica un comentari a l'entrada