3 de maig de 2017

Una qüestió d'intercanvis

Aquest problema l'he conegut per Abel Hernández, alumne de Didàctica de les matemàtiques de Sergi Muria (@smuria)  i Jordi Font (@jfontgon) a la UB. És prou interessant com per dedicar-li un temps d'estudi. Com en molts problemes no interessen tant els casos particulars com la generalització. Però... com arribar a ella sense els casos particulars? Per altra banda, és un problema molt bonic per treballar-lo a l'aula reproduint-lo amb els propis alumnes.

Imaginem la situació següent: tenim una certa quantitat de persones, cadascuna amb un objecte personal. Les posem en fila, una al costat de l'altra. Cada persona pot fer dues coses: quedar-se amb l'objecte que té o intercanviar-lo amb una de les persones que tingui al costat. Aquest procés només es fa una vegada. El problema és esbrinar quantes distribucions d'objectes diferents podem obtenir després de fer-ho. En el següent vídeo podem veure quantes en podem obtenir amb tres participants.


Amb tres persones no és difícil d'analitzar. Si el segon no vol fer cap intercanvi cadascun es quedarà amb el seu objecte (el 1r i el 3r no se'l poden intercanviar). Si el 1r i el 2n se l'intercanvien el 3r es quedarà mirant. I si fan l'intercanvi el 2n i el 3r serà el 1r el que es quedarà amb el seu objecte. Hi ha tres casos.

Però i si són quatre persones? I si són cinc?

Investiguem?

  • Provem alguns casos
Què passarà si estudiem el problema per a quatre persones? Podrem descobrir que, en aquest cas, són cinc les solucions possibles: una sense intercanvis, tres amb un intercanvi (1r i 2n, 2n i 3r o 3r i 4t) i una amb dos intercanvis (1r amb 2n i 3r amb 4t)



Per estudiar més casos pot ser una bona idea buscar una notació que ens ajudi. Ja hem vist amb altres problemes que les formes de representar-los poden ser útils per simplificar la seva resolució. En aquests cas podem considerar que no m'interessen tant les distribucions finals sinó la quantitat d'intercanvis i entre qui es fan. Ens podem ajudar representant les persones amb punts. Si fan un intercanvi els unirem amb un segment. El cinc casos per a quatre persones quedarien representats així:


Mirem ara com quedaria el gràfic per a una, dues i tres persones (una, dues i tres solucions respectivament).

Per a cinc persones tenim vuit possibilitats.
Segurament és moment de fer una taula per començar a buscar alguna pauta.
No és difícil reconèixer la sèrie que s'està obtenint: 1, 1, 2, 3, 5, 8... Efectivament són els nombres de Fibonacci. Cada nombre de la sèrie s'obté de la suma dels dos anteriors. Caldrà comprovar si per a 6 persones tindrem 13 casos (5+8).

6 participants - 13 distribucions

Per acabar-ho de confirmar mirem si realment per a set persones són 21 casos (8+13).

7 participants - 21 distribucions

  • Generalitzem i argumentem
Podem veure que, en general, per un cas particular de n la quantitat d'intercanvis serà el nombre de Fibonacci següent a n. Per a 7 persones serà el 8è nombre de la sèrie.

Si no voleu continuar de forma recurrent i per a un cas qualsevol de n, per exemple 234 persones, podeu utilitzar una fórmula o bé una calculadora en línia de números de Fibonacci com la que trobareu en aquest enllaç.


Fórmula per calcular un terme n de la successió de Fibonacci

La pregunta que pertoca ara és... i per què hi apareix la successió de Fibonacci?

Una possible forma de justificar-ho és observar un cas particular però distribuint les solucions en dos grups.

El primer grup el formarem amb les diferents situacions que s'obtenen en el cas de que el primer participant no vulgui intercanviar. Podem observar que s'obtenen les mateixes 8 possibilitats que si només participessin cinc persones. Té sentit: si una de les sis no "juga" és com si "juguessin" amb una menys.

El segon grup els formem amb les situacions en les que els dos primers participants intercanvien els seus objectes. En aquests cas veiem remarcat que les altres són les mateixes 5 possibilitats que per al joc amb quatre persones. També té sentit: els dos primeres "juguen entre ells" i el que queden, dos menys del total, han de fer-ho també entre ells.


Així ja ho tenim. El total de casos per una quantitat n és la suma dels casos per a n-1 i els corresponents a n-2, els dos resultats immediatament anteriors.

I a l'aula?
  • L'experimentació del joc amb poques persones es pot fer des de primària. No és difícil un cop obtinguda la taula veure la seva pauta recurrent. Amb els més petits convé treballar formes ordenades de buscar casos per assegurar-nos que no se'n deixen. Aquestes formes poden sortir del contrast entre grups de la mateixa quantitat de persones i que obtinguin totals diferents.
  • Podem aprofitar la situació treballar els nombres de Fibonacci i algunes de les seves propietats.
    • el quadrat d'un nombre de Fibonacci difereix en una unitat, per sobre o per sota, dels producte de l'immediatament anterior per l'immediatament posterior (82=5·13-1)
    • qualsevol nombre natural es por expressar com una suma de nombres de Fibonacci sense que cap d'ells aparegui més d'una vegada (54=2+5+13+34)
    • el 2 ocupa el 3r lloc de la sèrie i cada tres nombres trobarem un múltiple de 2. El 3 ocupa el 4t lloc i cada quatre nombres torbarem un múltiple de 3. El 5 ocupa el 5è lloc de la sèrie i cada...
    • per calcular la suma dels n primers nombres de la successió avancem dos nombres en la sèrie i restem u (1+1+2+3+5+8 = 20 = 21-1) (1, 1, 2, 3, 5, 8, 13, 21...)
  • Una modificació interessant és estudiar aquest mateix sistema d'intercanvis però posar als participants formant un cercle en comptes de fer-ho en línia. Com canvia ara el càlcul de situacions? En aquest cas no s'obtenen els nombres de Fibonacci sinó els nombres de Lucas. Édouard Lucas va ser un gran divulgador matemàtic i, entre altres coses, l'inventor del joc de les Torres d'Hanoi. No és la primera vegada que apareix en aquest blog. També va ser el primer investigador-popularitzador dels nombres de Fibonacci. La successió de Lucas es construeix igual que la de Fibonacci però començant amb els nombres 2 i 1. Els primers nombres són 2, 1, 3, 4, 7, 11, 18, 29... Els nombres en negreta són els que surten al problema. La sèrie funciona des del nombre 4 que correspon a la solució per tres persones posades en cercle. 
Els 11 casos posant cinc persones en cercle
En general la quantitat de distribucions per un nombre n de participants serà el nombre de Lucas n+1. La fórmula general per trobar un nombre qualsevol de Lucas és una mica incòmoda d'usar. La forma més pràctica és elevar el nombre φ a n i arrodonir. Així per esbrinar quantes distribucions tenim per a 5 persones farem:

Altres preguntes de l'Abel Hernández

L'Abel no proposa exactament el joc com l'hem plantejat aquí. Nosaltres hem parlat sempre "d'intercanvis". Ell parla de "donar" l'objecte a alguna persona de les del costat i imposa que, al final, tothom tingui un objecte. En el cas d'estar en fila l'enunciat és equivalent. Però en el cas d'estar en cercle hi ha dues possibilitats més per a cada nombre n: que tots donin el seu objecte (i en rebin un altre) en sentit horari o que ho facin en sentit antihorari. Així la sèrie que s'obté per a tres persones, quatre, cinc, etc, serà 6, 9, 13... augmentant en dos cada cas de la successió de Lucas. Per altra banda formula altres preguntes interessants. Les que es refereixen a disposicions circulars les hem d'entendre amb les seves regles (tot i que no costa gens d'adaptar-les a les nostres). No les resoldrem i les deixarem perquè les penseu vosaltres i les enunciem tal com ho fa ell:
  1. Quina és la probabilitat de que tothom tingui un objecte diferent després d'una ronda de canvis si se situen 2017 persones en fila?
  2. Proposa una distribució de persones de manera que, independentment de la quantitat que siguin, tots puguin rebre un objecte diferent.
  3. Si tenim n persones formant una circumferència, quantes rondes caldran (com a mínim) perquè tots hagin tingut tots els objectes?
  4. Si volem que almenys un parell de persones intercanviïn els seus objectes, què hauran de fer els altres per tal de no quedar-se amb el mateix objecte que tenen? Mirar els casos en els quals es distribueixin en fila i circularment.
Dos problemes anàlegs
Una de les virtuts de les matemàtiques és desvetllar el que tenen de comú situacions aparent diferents. El problema dels intercanvis en fila és exactament igual a aquests dos que podem proposar a l'aula en un altre moment.
  • De quantes maneres diferents podem pujar una escala de n graons si sempre a cada pas pugem un graó o dos?
Les cinc formes de pujar quatre graons
  • De quantes maneres diferents podem fer enganxar el segells en línia per fer un franqueig de n cèntims si només disposem de segells d'un i dos cèntims?
Les cinc formes de fer un franqueig de 4 cèntims

Cap comentari:

Publica un comentari a l'entrada