13 d’octubre de 2019

Un problema operatiu sorprenent: "Treure monedes del banc"

El divulgador matemàtic Alex Bellos manté, entre altres publicacions i col·laboracions, la columna Monday Puzzle a la publicació digital The Guardian. Un autor a seguir. El dilluns 7 d'octubre va proposar un problema titulat Treure monedes del banc (Getting coins out of the bank) que mereix atenció per diferents raons i que té una possible explotació didàctica. D'aquí que passem a plantejar-lo i comentar-lo. L'autor del problema és el matemàtic argentí Carlos Sarraute, que també ha proporcionat problemes a altres divulgadors com Adrián Paenza. És un problema de plantejament fàcil i de resolució sorprenent que ens pot permetre a l'aula parlar de demostracions, de condicions necessàries, condicions suficients... i que ens pot obrir tot un ventall de preguntes noves. Passem a plantejar i comentar el problema.

Tenim un tauler quadriculat limitat per dalt i per l'esquerra però infinit cap la dreta i cap avall. En aquest tauler marquem un quadrat de 2x2 a la cantonada superior esquerra i que anomenarem com a "banca".
Posem tres monedes a la banca tal com es mostra a l'esquema.
L'objectiu és treure les tres monedes de la banca amb aquestes dues regles:
  1. Si traiem una moneda apareixen dues noves a la casella immediatament dreta i immediatament inferior.
  2. No podem eliminar una moneda si la casella dreta o inferior estan ocupades per una altra moneda.
La demanda del problema és explicar com treure les tres monedes de la banca... o demostrar que és impossible.

El mateix Bellos ens enllaça un applet fet amb Scratch, dissenyat per Mtega, per practicar el problema. Cosa que us animem a fer abans de continuar llegint.


Heu practicat ja?

Per poc que us hàgiu dedicat començareu a sospitar que si el problema costa de resoldre i a l'enunciat es demana la demostració d'impossibilitat, és que les coses van per aquí: que encara que a priori sembla que es puguin treure les monedes en realitat és impossible.

De fet la demostració d'impossibilitat és sorprenent per indirecta, bella, entenedora... però poc intuïtiva en el que respecta al plantejament i el camí de resolució. És molt difícil que algun alumne arribi a aconseguir-la, però sí que l'entenguin i vegin la bellesa i potència de les matemàtiques. Presentar alguna demostració d'impossibilitat és interessant per a l'alumnat perquè entenguin com són les matemàtiques i com, amb una mica d'esforç, ens podem estalviar treballs inútils que no ens portaran enlloc.

T'animes a continuar i veure possibilitats didàctiques?
La demostració que ens explica Bellos té poques passes. La primera idea brillant és numerar les caselles del tauler assignant un "pes" a cadascuna aplicant el següent mètode. A la casella superior esquerra li donem un valor 1 i, a partir d'aquí, a cada casella situada immediatament a la dreta i immediatament a sota li reduïm el valor a la meitat. D'aquesta manera ens queda un tauler com aquest.


Què passa si eliminem una moneda de la casella de valor 1? Que apareixen dues monedes a la de valor 1/2. Per tant el valor "ocupat" continua sent 1. I si eliminem una moneda d'una casella amb valor 1/8? Que apareixen dues monedes a les de valor 1/16 i la suma, 2/16, continua sent 1/8. En conseqüència podem dir que el "valor" inicial que tinguem de monedes es manté invariant durant tot el joc.

La demostració segueix preguntant-se quin és el valor total del tauler. Per poder-ho saber hem de recordar que la sèrie infinita 1/2+1/4+1/8+1/16... suma 1 (cosa que podem treballar amb els alumnes en aquest moment o altres i explicar de formes prou intuïtives a partir de la paradoxa de Zenó, de gràfics...). En primer lloc mirem quan suma cada fila:


El valor total del tauler l'obtindrem del valor de la suma de les infinites files... i veiem que és 4:

Quin és valor de la banca?

I el de la resta del tauler? Ho podem esbrinar restant el valor de la banca al de tot el tauler.


Només queda el cop de gràcia. Recordeu que el valor total de les monedes és invariant? El valor de la posició inicial proposada és de 2 (8/4).


Aquest valor es mantindrà invariant mentre anem jugant. Hi hagi la quantitat de monedes que hi hagi i estiguin on estiguin. Però treure-les de la banca vol dir passar-les a la zona on només hi cap un pes total de 7/4. Serà totalment impossible!

Sorprenent, no?

S'ha acabat el problema?

Si poden aparèixer noves preguntes... el problema no s'acaba. I de preguntes ens podem fer un munt. Per exemple, què passa amb altres disposicions de tres monedes? Aquestes dues primeres tenen un valor total de 7/4 i a priori les podríem treure.

Però això significaria omplir la resta del tauler (el "forabanca") d'infinites monedes, cosa que a no és possible fer de forma real. Per tant són descartables. Ens queda una quarta disposició de valor 5/4 i que podem estudiar.

Bé... us animo a intentar-ho amb aquest applet adaptat de l'original.


Podem començar a sospitar que la resolució és molt llarga o, fins i tot, impossible. Per veure que, d'existir una solució, serà molt llarga només cal observar que el valor de les caselles decreix exponencialment a mesura que ens allunyem del vèrtex superior esquerra. En el cas de que fos impossible resoldre-ho ens porta a pensar que el fet de que el valor total de les monedes sigui inferior a 7/4 és condició necessària però no suficient. Una bona oportunitat per parlar amb els nostres alumnes d'aquesta característica lògica. Si trobeu la solució us demanaria que me la comuniquéssiu per modificar l'article.

Estudiem casos més senzills amb menys monedes

Si anem als casos d'una o dues monedes no ens sentirem tan frustrats perquè podrem trobar solucions. Una possibilitat per anotar les posicions de sortida i les seves resolucions és assignar a cada casella unes coordenades segons la fila i columna.


Els quatre casos d'una moneda es poden solucionar amb poques passes (entre 1 i 8).

Inici (1,1)
[8 moviments]
Applet
Inici (1,2)
[2 moviments]
Applet


Inici (2,1)
[2 moviments]
Applet
Inici (2,2)
[1 moviment]

Pels sis casos de dues monedes costa trobar solució pels tres en què una de les monedes està a la cantonada superior esquerra (1,1). L'amic Enric Castellà (@Enric_Castella) que ha estat treballant en el disseny d'un programa que analitzi aquests casos però que no han donat solucions. Comentarem el seu treball amb més detall amb les dues addendes finals de l'article. De fet a la segona addenda tenim una possible demostració de la seva impossibilitat.

   
Inici (1,1-1,2)
[Pendent de solució]
Applet
Inici (1,1-2,1)
[Pendent de solució]
Applet
Inici (1,1-2,2)
[Pendent de solució]
Applet
 
 
 
Inici (1,2-2,1)
[7 moviments]
Applet
Inici (1,2-2,2)
[6 moviments]
Applet
Inici (2,1-2,2)
[6 moviments]
Applet

I si canviem la forma de la banca?

És una altra pregunta que obrim perquè experimenteu. Aquí teniu algunes possibilitats. Algunes, clarament no tindran solució però altres sí.


I a l'aula?

Ja ho hem anat comentant des de l'inici de l'article: aquesta activitat ens pot ser molt útil per parlar de demostracions, condicions necessàries, condicions suficients, invariància, per generar noves preguntes, per cercar formes de representació per anotar les solucions... I, com a valor afegit i per comprendre un dels passos de la demostració, discutir el valor de la suma 1/2+1/4+1/8...


Addenda 1 (20/10/19)

El programa que ha fet l'Enric Castellà per a una de les dues disposicions de dues fitxes no resoltes i en un tauler de 10x10, ha provat més de 150 000 000 de casos sense que en trobés cap solució. Finalment, després d'un dia de treball de l'ordinador, l'Enric va aturar el programa perquè hi havia tantes opcions a estudiar que va pensar que. per aquesta via, es necessitaria un temps excessiu. 

Unes línies abans comentàvem que, a mesura que ens allunyem de la casella superior esquerra (1,1), el decreixement del pes de les cel·les és exponencial.

La casella (10,10) valdria 1/262144; aproximadament unes 4 milionèsimes
Les cel·les de la banca, especialment la de la cel·la (1,1), pesant exageradament més que las que resta de cel·les del tauler. Cada vegada que fem un moviment augmentem en una la quantitat de monedes sobre el tauler. "Diluir" el pes de les monedes de la banca entre les altres implica col·locar moltes i moltes monedes sobre el tauler i procurant deixar algunes lliures tocant la banca per treure la darrera moneda, que normalment serà la situada a la casella (2,2) amb un pes d'1/4: hem de tenir lliures les dues adjacents de pes 1/8, la (2,3) i la (3,2). Si ho proveu... és complicat.

No és difícil calcular quant pesen les diferents corones al voltant de la banca.

Recordem que el "forabanca", on hem de posar les monedes de la banca, pesa 7/4 (1,75). Podem veure que arribem molt a prop d'aquest pes en un tauler de 12x12. De fet a partir d'aquí augmentar el tauler en una fila i una columna proporciona un creixement de pes total gairebé imperceptible.


Per poc que practiquem veurem que, a mesura que anem omplint el tauler de monedes. la situació de bloqueig de les caselles properes a la banca és creixent. La qual cosa redunda en la impossibilitat de resolució pels quatre casos pendents [(1,2) (2,1) (2,2)], [(1,1) (1,2)],[(1,1) (1,2)] i [(1,1) (2,1)].

Però l'Enric i jo hem treballat un temps pensant que això només és una hipòtesi i que cal obrir el debat.

Us deixem una altra conjectura: si resolem un cas amb el mínim de moviments, la disposició final de monedes serà la mateixa independentment de l'odre en què fem els moviments?

Addenda 2 (28/10/19)

Al dia següent de publicar la primera addenda l'amic Enric em va proporcionar uns nous arguments que deixen de forma molt clara (si no demostren definitivament) la impossibilitat dels casos que teníem pendents. Si no refaig completament l'article és perquè crec que és interessant deixar el rastre de com es va resolent el problema i exemplificar les voltes que li podem arribar a donar quan no estem del tot satisfets amb una resposta.

L'observació principal de l'Enric és que, per les normes de moviment del joc, a la fila superior o a la columna de la dreta sempre tindrem tantes monedes com hi havia a la disposició d'origen. Si practiqueu una mica ho veureu clarament. En els quatre casos que tenim pendents estem parlant d'una (casos 3 i 4) o dues monedes (casos 1 i 2).


Inici (1,1-1,2)
Applet
Inici (1,1-2,1)
Applet
Inici (1,1-2,2)
Applet
Inici (1,2-2,1-2,2)
Applet

Estudiarem inicialment el cas de tres monedes. Donat que només tindrem una moneda en aquesta 1a fila i en aquesta 1a columna les podem donat per "perdudes". Serà com si estiguessin plenes de monedes.


D'alguna manera podríem dir que el tauler queda reduït, un cop traguem la moneda de la fila superior o la de la primera columna, en un pes d'una unitat. El "forabanca" de la primera fila és 1/2. El resultat de sumar:


Per tant, treure de la banca la moneda de la primera fila ocupa un pes d'un mig del tauler. Amb l'altre mig de la primera columna ja tenim la unitat perduda. Això significa que el pes real del "forabanca" no és de 7/4 sinó de 3/4. I ens quedarà una situació derivada de la següent que mostrem a la imatge (en la que només hem posat les monedes clau).

Seguirem el raonament per demostrar que aquesta situació no es pot resoldre.

En primera instància podríem pensar que la moneda que encara està a la banca té un pes d'1/4 i que encara disposem de 3/4 de pes lliure en el tauler. Però això no és de tot cert. Per què? Perquè per treure les monedes de la primera fila i de la primera columna (amb un pes d'1/2 cadascuna en la seva posició inicial) hem fer aparéixer dues monedes d'1/4 de pes. Al gràfic tenim representades dues d'aquestes quatre monedes, però els altres dos quarts estan en monedes dispersades pel tauler.


Si als 3/4 de tauler que teníem li descomptem aquests dos quarts que ja hem ocupat només ens queda un quart de tauler útil.

En conclusió: després de treure les dues monedes de la banca als llocs 1,3 i 3,1 ens queda una moneda d'un quart per repartir en un tauler d'un quart, que haurem d'omplir d'infinites monedes, cosa que és impossible de fer. Ja ho tenim!

O no? Ens queden tres casos de dues monedes pendents. Però és fàcil observar que els tres casos que ens queden hauran de passar en un moment o un altre per la disposició de tres monedes que acabem d'estudiar... o per una posició derivada d'aquestes. Per tant, tampoc es podran resoldre.


Voleu opinar? Teniu altres demostracions? Ens les expliqueu?





Cap comentari:

Publica un comentari