12 de juliol de 2019

Problemes connectats?

En aquest article plantejarem i estudiarem alguns problemes, de formats diferents, en els que buscarem patrons de creixement. Posteriorment mirarem si entre aquests patrons trobem alguna connexió i, si existeix, de quin tipus és.

Ens hi posem amb els problemes?
  • Problema 1. Tenim una "escaleta" quadriculada de 3x3. De quantes maneres diferents hi podem posar exactament tres rectangles a dins? I si l'escaleta és de 4x4, de quantes maneres podrem posar-hi quatre rectangles? (Entenem que els quadrats també són rectangles).
  • Problema 2. Tenim sis jugadors de bàsquet. Els hi volem fer una fotografia posant-los en dues files de tres, una davant de l'altra, de manera que el jugador de darrere sempre sigui més alt que el de davant i que, en la mateixa fila, el de la dreta també sigui més alt que el de l'esquerra. Quantes fotografies diferents podrem fer? I si tenim  vuit jugadors?
  • Problema 3. Quants camins (sense retrocés) hi ha per anar per la quadrícula des d'A fins a B sense creuar la diagonal a la quadrícula de 3x3? I si la quadrícula és de 4x4?
  • Problema 4. Disposem de sis palets. Quantes "muntanyes" o "serres muntanyoses" diferents podem fer de forma que hi hagi tres palets de pujada i tres de baixada? I si disposem de vuit palets? (Quatre de pujada i quatre de baixada).

Estudiem cada problema?

  • Problema 1 (escaletes)

Aquest problema pot ser interessant planejar-lo a l'aula amb material. Una plantilla impresa amb les escaletes de 3x3 i 4x4 i els rectangles de les mides convenients per retallar-los... o fets amb multilink.

En el cas de 3x3 trobarem cinc solucions diferents.


Per a 4x4 trobem 10 solucions noves fàcilment aprofitant les anteriors de 3x3. Només cal afegir un rectangle d'1x4 horitzontal o verticalment. Si ara juguem amb un rectangle nou de 2x3 trobarem les quatre solucions que falten per tenir el total de 14.


No és difícil retrocedir per a buscar les solucions d'1x1 i 2x2.


Podem fer una taula recollint els resultats.


  • Problema 2 (fotografies de bàsquet)

Per a 6 jugadors (dues files de tres) trobem 5 solucions diferents.


Les 14 solucions per a 8 jugadors (dues files de 4) les mostrem amb diferents taules.


No és difícil veure que per a 4 jugadors (dues files de dos) i dos jugadors (dies files d'un) hi ha dues i una solució respectivament.


Com al problema 1 podem fer una taula que reculli els resultats.


  • Problema 3. Camins sense creuar la diagonal
Per a una graella de 3x3 tenim 5 camins diferents. I per a una de 4x4 14.
Camins de 3x3 (5 camins)
Camins de 4x4 (14 camins)
Si estudiem graelles d'1x1 i 2x2 trobarem 1 i 2 solucions respectivament.

La taula següent recull tots els resultats:

  • Problema 4. Muntanyes i serres
A aquestes alçades ja podem sospitar les solucions per un parell de palets, per dos, per tres i per quatre... i que la taula serà la mateixa.




Com continua la sèrie?

Tenim un començament de sèrie numèrica que, abans d'anar a l'OEIS (The On-Line Encyclopedia of Integer Sequences), pot ser interessant d'estudiar. Una manera habitual de començar a estudiar sèries és mirar les diferències entre termes consecutius.


Sembla que la diferència són les successives potències de 3. Segons aquesta observació el següent element de la sèrie seria 41.


Les conjectures sempre s'han de comprovar. Fem-ho a partir del problema 1, el de les "escaletes". Aquesta vegada no buscarem tots els casos un per un, sinó que accelerarem una mica el procés tenint en compte que coneixem la quantitat de solucions per a 2x2, 3x3 i 4x4. Si ampliem a 5x5 podrem posar diferents rectangles inicial
  • Si posem un de 5x1 en horitzontal ens quedarà a sota una escaleta de 4x4 que té 14 solucions.
  • Si posem un de 5x1 en vertical passarà el mateix: 14 solucions més.
  • Si posem un de 4x2 i, obligatòriament, un d'1x1 en horitzontal o en vertical tindrem 10 solucions més (5+5)
  • Si posem un de 3x3 quedaran dues escaletes de 2x2 amb dues solucions cadascuna. Seran 4 solucions noves (2x2)
  • En total tindrem 42 solucions.




Com hem vist no obtenim el 41 previst com a continuació de la sèrie. Encara podem corroborar que el creixement és molt diferent a la successió de potències (de fet és més gran) si fem un estudi similar per a una escaleta de 6x6 on trobarem, amb un raonament similar, 132 solucions (H és horitzontal i V vertical).


A la resta de problemes també la sèrie és aquesta mateixa.


No posarem les solucions de tots però podeu trobar, com a exemple, les solucions dels problemes de les escaletes i dels itineraris en aquest enllaç (Mathematical Figures Using Mathematica by Robert M. Dickau).

Les 132 solucions del problema dels itineraris en una quadrícula de 6x6

El problema de les fotografies de l'equip de bàsquet el podem trobar al web de l'NRICH (One Basket or Group Photo). És interessant mirar la resolució proposada pel cas de 10x10 per Andrei, un alumne del Tudor Vianu National College, de Bucarest (Romania). De fet l'espurna d'aquest article sobre "problemes connectats" va ser aquesta proposta de l'NRICH.

I quina és aquesta sèrie? El nombres de Catalan!

Aquesta sèrie és la mateixa que va descobrir Leonhard Euler tot estudiant la quantitat de triangulacions mínimes d'un polígon.




Però porta el nom del matemàtic belga Eugène Charles Catalan que la va redescobrir resolent un problema ben diferent. Per poc que cerqueu per internet trobareu altres problemes (a la Viquipèdia mateix hi ha uns quants més dels que hem exposat) en els que "els nombres de Catalan" apareixen sorprenentment. De fet recomano mirar el capítol que els hi dedica Martin Gardner (qui si no?) al seu llibre Viajes por el tiempo y otras perplejidades matemàticas. D'ells afirma Gardner que

"encara que no són tan coneguts com els nombres de Fibonacci, els de Catalan tenen aquesta mateixa encantadora propensió a presentar-se inopinadament, especialment en problemes combinatoris.


Només caldria afegir que apareixen sovint en "problemes combinatoris de caràcter recursiu. En aquest mateix llibre de Gardner trobareu també altres "problemes catalans" (i em refereixo només als relacionats amb aquesta sèrie numèrica. No poseu "problemes catalans" al cercador del vostre navegador que us pot petar l'ordinador).

També tenen, com és lògic, el seu espai en l'OEIS (A000108). Cal observar que la sèrie comença amb dos uns i no amb un de sol com en els nostres exemples. Només que, en els problemes proposats, comencem amb el cas inicial 0 ja ho tindríem resolt (una escaleta de zero, zero parelles de jugadors, etc.)

A internet podreu també fórmules i demostracions de com calcular els diferents termes de la sèrie. Una que crida especialment l'atenció és una forma recursiva d'obtenir-los. És mèrit del matemàtic, contemporani a Euler, Johann Andreas von Segner.

Si coneixem els primers n nombres de Catalan i els posem en dues files, una ordenada del dret i l'altre del revés, podem calcular el terme següent (n+1). Només cal multiplicar els nombres que queden en una mateixa columna i sumar els resultats. Per exemple, si coneixem els set primers termes (1, 1, 2, 5, 14, 42 i 132) podem esbrinar el 8è de la següent manera:


I a l'aula?

Hem triat quatre problemes fàcilment abordables a finals de la primària i al començament de l'ESO. Es poden proposar en diferents moments i anar "recuperant" la sèrie. Però una opció bonica és proposar cada problema a una quarta part de la classe i després compartir resultats i viure la sorpresa de que els resultats siguin els mateixos. Encara que és complicat es poden intentar discutir alguns dels nexes entre les situacions perquè s'obtinguin resultats semblants.

Posteriorment es pot proposar que busquin més informació sobre aquests nombres (i els matemàtics implicats) i altres problemes en els que apareixen. La nostra intenció és fer un altre article, pròximament, sobre la seva presència en arbres binaris i fer una petita ampliació relacionada amb el camp de la genètica.



Cap comentari:

Publica un comentari