Blog d’en Xavi

Per temes que no vénen al cas, m’ha sorgit el problema de resoldre el següent sistema diofàntic:

amb s senar.

Alguna idea?.

Tenc un problema, ¿algú me pot ajudar?

Donats, a, b nombres naturals, existeixen x, y nombres sencers tals que

mcd(a,b) = ax + by.

A aquesta identitat se l’anomena identitat de Bézout, i si (x,y) compleixen la identitat de Bézout es diuen que nombres de Bézout.

Hi ha un algorisme per trobar una tupla (x,y) que es basa en l’Algorisme d’Euclides (anant cap a enrera)

Voldria un algorisme per trobar una tupla (x, y) basat en la factorització en nombres primers de a i de b. Algú sap si n’hi ha algun? Algú em pot ajudar per trobar-ne un?

Podem definir per a tot . De manera trivial tenim que , però quins són els coeficients de ? N’hi ha que són trivials (, ), però n’hi ha que no (per exemple ). Algú s’hi atreveix?

Una variació del problema del mínim de moviments per obtenir un conjunt apinyat al reticle amb aplicació:

Sigui A un conjunt de . Volem trobar el mínim de moviments pels quals cada element de A pot transformar-se en un únic punt a. O sigui, per a cada A conjunt de , trobar un punt (no té perquè ser únic ni estar a A) tal que sigui mínima.

Noteu que almenys un d’aquests sempre existirà. Si denotem la suma mínima com (i.e., ), aleshores és el nombre mínim de moviments (entesos com simplement els passos discrets per anar de qualsevol element de A a , aquí no compt res d’espais en blanc com en anteriors problemes) necessaris per a què tots els punts de A “convergeixin” a

Això té una aplicació òbvia: si tenim n persones (i identifiquem cada persona amb les seves coordenades cartesianes al Pla), aleshores és un punt on és més fàcil trobar-se (en conjunt la distància que ha de recorre cada persona per arribar-hi és menor (o igual) que per a qualsevol altre punt).

Quina seria la fórmula de e(A)?. Crec que es podria provar que si A i B són disjunts, (algú s’atreveix?; d’aquesta no n’estic tan segur com les anteriors). I llavors obtenir que

L’altre dia vaig veure un anunci d’un comptador de calories….

Això me va fer demanar una cosa: ¿què podem comptar els matemàtics en els objectes?. Els biòlegs podríen comptar nucleòtids; els químics mol·lecules (mols o reaccions); els físics particules elementals (o deformacions en l’espai temps). I els matemàtics? Vosaltres què comptaríeu a l’estructura dels objectes? Potser grups de simetries?

PS: Per cert, no he trobat el vídeo en català.

L’altre dia vos proposava un problema de tassons. He reflexionat un poc en aquest problema…. la meva modelització aniria sobre reticles i el nombre mínim de moviments per passar d’un conjunt determinat d’un reticle a un altre conjunt determinat dins el mateix reticle (amb l’única condició de que aquests conjunts han de tenir el mateix cardinal).

He pensat que la solució general a aquest problema per mi és bastant difícil, i la he intentat simplificar eliminant una variable (el conjunt d’arribada). Tot seguit vos oferesc el problema simplificat:

Tenim un conjunt de tassons disposats de la següent manera:

[]T[]T

T[]TT

[]T[]T

i volem saber el nombre mínim de moviments (només són permesos els moviments dels tassons a buits adjacents al lloc que ocupen) necessaris per a què els tassons estiguin tots apinyats (sense buits), de qualsevol forma.

La meva modelització seria amb reticles:

Sigui A un subconjunt de . Hauríem de definir què és ser apinyat i què no. I després hauríem de definir un moviment natural com aquell que passa un element d’un conjunt a un espai adjacent all lloc que ocupa aquest element. I després definir s(A) com el nombre mínim de moviments per passar de A a A* un conjunt apinyat.

Les definicions són difícils de formalitzar però tothom té la intuïció sobre els conceptes. Per això, tothom pot deduir que si A i B són disjunts, aleshores . Tenint en compte que si A té dos punts , on , llavors (una fita molt grollera)

Algú s’atreveix a trobar la fórmula exacta de s(A)?

PS: Al conjunt de l’exemple s(A) = 3 (els punts aïllats, tots a la dreta) i la meva fita dóna (!)

Actualització (16/03/08): El ser un conjunt apinyat es podria definir com que cada element està a distància mínima possible de tots els altres elements. Per exemple, el conjunt:

[][]A[]

[][][][]

[]B[]C

no seria apinyat

ni el conjunt

[][]A[]

[][]B[]

[][][]C

tampoc (C pot estar més aprop de A i de B)

però sí el conjunt

[][]A[]

[][]BC

[][][][]

ja que C es mogui o no ja no pot estar més aprop de A ni de B (i el mateix passa a A i a B)

O sigui, podríem definir l’apinyament de A, ap(A), com:

ap(A) =

i dir que A està apinyat si ap(A) és mínim (qualsevol reordenació dels Card(A) elements de A tendria major apinyament)

Serà vera que la matemàtica està per tot?, o almenys que la ment humana interpreta la natura (i altres problemes) de forma matemàtica?…. hem deia això quan escurant he volgut col·locar els tassons de l’eixugaplats i m’he demanat sobre els nombre mínim de moviments que havia de fer per col·locar-los en línia de dos. Vos explic:

Jo tenc tres línies on puc posar tassons a les quals hi caben exactament 7 tassons. A cada lloc (els suposem discrets) hi pot haver un tassó o un buit. Per exemple, podem tenir:

1: T[]TT[]TT

2: [][][]TT[][]

3: [][][]T[][][]

on [] denota buit i T un tassó

Aleshores vull passar d’aquesta configuració a:

1: [][][]TTTT

2: [][][]TTTT

3: [][][][][][][]

Quin és el nombre mínims de moviments que he de fer per aconseguir-ho (un moviment és un pas d’un tassó a un buit adjacent). I en general? Com modelitzaríeu aquesta situació?

Segurament recordau que en la carrera de Matemàtiques vos varen parlar sobre cardinals i sobre un teorema bastant trascendent: els nombres reals no són enumerables.

Segurament també recordeu que aquest teorema de fet demostrava que el conjunt [0, 1] no és enumerable. I supòs que segurament la demostració d’aquest fet es va fer utilitzant l’arxiconegut argument de la diagonal de Cantor.

I segurament n’hi ha haver alguns (una minoria, segurament) a la classe que no el varen acabar d’entendre o que no hi varen estar d’acord.

Almenys a la UIB hi havia un element d’aquest darrer grup (jo; i em pareix recordar que en Félix). L’argument per estar-hi en contra era molt simple: si per hipòtesi es suposa que R es pot enumerar amb , < … < < …. , ¿com es pot construir un amb ( no existiria per hipòtesi)?

Bé, fos o no aquesta raó o una altra que teníeu per estar-hi en contra, segurament vos vàreu quedar amb un dubte raonable de la validesa d’aquest teorema (fins a obtenir-ne una altra i “vertadera” demostració). Doncs bé, ahir llegint aquest llibre, en vaig trobar una altra (que de fet, he trobat reproduïda i aclarada a la Wikipedia):

The theorem

Suppose a set R

1. is linearly ordered, and
2. contains at least two members, and
3. is densely ordered, i.e., between any two members there is another, and
4. has the following least upper bound property. If R is partitioned into two nonempty sets A and B in such a way that every member of A is less than every member of B, then there is a boundary point c (in R), so that every point less than c is in A and every point greater than c is in B.

Then R is not countable.

The set of real numbers with its usual ordering is a typical example of such an ordered set R; other examples are real intervals of non-zero width, possibly with half-open gaps. The set of rational numbers (which is countable) has properties 1, 2, and 3 but does not have property 4.

The proof

The proof is by contradiction. It begins by assuming R is countable and thus that some sequence x₁, x₂, x₃, … has all of R as its range. Define two other sequences (a_n) and (b_n) as follows:

Pick a₁ < b₁ in R (possible because of property 2).

Let a_{n + 1} be the first element in the sequence x that is strictly between a_n and b_n (possible because of property 3).

Let b_{n + 1} be the first element in the sequence x that is strictly between a_{n + 1} and b_n.

The two monotone sequences a and b move toward each other. By the completeness of R, some point c must lie between them. (Define A to be the set of all elements in R that are smaller than some member of the sequence a, and let B be the complement of A; then every member of A is smaller than every member of B, and so property 4 yields the point c.) Since c is an element of R and the sequence x represents all of R, we must have c = x_i for some index i (i.e., there must exist an x_i in the sequence x, corresponding to c.) But, when that index was reached in the process of defining the sequences a and b, c would have been added as the next member of one or the other sequence, contrary to the fact that c lies strictly between the two sequences. This contradiction finishes the proof.

L’altra dia em demanava sobre els fonaments de les matemàtiques. Hi va haver molta retroacció entre els blogxeixers, i en Félix va apuntar sobre si es podia o no definir els conceptes matemàtics. Jo li vaig respondre que en la meva opinió no (a no ser amb l’ús d’un llenguatge extern) però sí que es podien descriure (trobar les propietats que compleixen aquestes objectes) o caracteritzar (aclarir que aquests objectes són els únics que compleixen certes propietats).

Mentres deia tot això estava pensant en els sistemes formals i en caracteritzar els objectes amb l’ajuda de fórmules (p.e. “R és l’únic grup commutatiu que compleix….”). Bé, doncs ara afegeix un altre element a la discussió: caracteritzar-los mitjançant els morfismes entre aquests.

Qualsevol estructura té uns morfismes que preserven les propietats entre aquests (els homeomorfismes són els morfismes entre espais topològics, els morfismes de grups preserven l’estructura de grup, les funcions monòtones preserven l’ordre, etc.). Per tant es pot estudiar l’estructura estudiant els seus morfismes. I comparar estructures comparant els morfismes entre aquests.

Aquesta és la idea de la Teoria de Categories (Xesc, corregeix-me si m’equivoc!). I hi ha tendències a la lògica que volen fonamentar-la en la teoria de categories: Teoria de Conjunts Algebraica, Institucions (generalitzacions de la lògica mitjançant categories), Topos, etc.

No he tengut molt de temps de llegir els detalls tècnics, encara que l’important és que tenim una altra eina per descriure els objectes. Si algú té temps i ganes pot contribuir fent-nos 4 cèntims? O bé dir-nos on podem començar a llegir per entendre una mica de tot?

Xavi

PS: Un llibre que està prou bé (cobriria just les ensenyances d’en Joan Torrens a Àlgebra III de l’extingit pla d’estudis de la Llicenciatura de Matemàtiques però és accessible i planer) és “Basic Category Theory for Computer Scientists” de Benjamin C. Pierce (no el cerqueu a la biblioteca, el tenc fins dia 10 de març! ;-))

Algú s’ha demanat per què és tan difícil d’entendre la llei de proporcionalitat inversa (per part dels alumnes de ESO)? Voldria fer dues reflexions sobre això:

1. En primer lloc, la hem d’explicar. Vull dir:
   • Hi ha un salt qualitatiu entre la llei de proporcionalitat directa i inversa, i sempre se té la sensació que hi ha molta gent que en el tema de Proporcionalitat no entén ni el concepte ni el procediment (que per cert és molt artificial).
   • No s’hauria d’esperar un poc per explicar aquesta llei (quan sapiguessin el concepte de funció i estiguessin familiaritzats amb les funcions f(x) = k/x), sobre 4t d’ESO?
   • Realment fa falta explicar-la?: quantes aplicacions coneixeu de les magnituds inversament proporcionals a nivell d’ESO (tant a la vida real com al propi temari de les matemàtiques: on més s’usa?)?. De fet a mi no me la varen ensenyar mai. Me va bastar saber la proporcionalitat directa i saber que inversament proporcional = va amb la llei f(x) = k/x (que per cert, me varen ensenyar a física de segon de BUP)
2. En segon lloc, no la podríem reduir a un problema de proporcionalitat directa?. Com ho faríeu de forma natural? Se m’ocorr fer-ho amb puntuacions. Per concretar, podríem fer servir aquest problema:

Una associació de Matemàtics (!) decideix donar un premi al millor docent. Decideix repartir 240 euros en 3 premis de manera inversament proporcional a la posició del docent. Quants de doblers se’n pot endur un docent segons el lloc que ocupi?

Com a problema de proporcionalitat inversa, el problema és clar (ho poso a nivell formal):

Sigui f(x) = doblers que se’n dur una persona si queda en el lloc x.

Aleshores f(1) + f(2) + f(3) = 240

Com que f(x) és inversament proporcional, f(2) = f(1)/2, f(3) = f(1)/3. Per tant, (1+1/2+1/3) f(1) = 240, pel que f(1) = 240/11.

D’aquí f(2) = 120/11, f(3) = 240/33

Però podríem veure el problema com puntuar els docents. Suposem que a cada docent se li dóna una sèrie de punts (positius o zero) en funció de la posició on quedi: per quedar primer tenim molta puntuació, per quedar segon n’hem de tenir menys, i per quedar segon, molt menys. Si deim P(x) = punts que assignam per quedar a la posició x, tenim que l’assignació de P(1), P(2) i P(3) es fa per la llei de proporcionalitat inversa, però el problema, com a problema de punts, ja es veu com a directa (”si tens tots els punts, te’n duus tot el premi, aleshores si tens, 10 punts, …”) que crec que és més fàcil d’entendre que abans (com explicaríeu que f(1) + f(2) + f(3) = 240 en una frase?).

Per cert, com assignar P(1)?

No sé, què trobau de tot plegat?

Actualització: Realment, allà on diu “proporcionalitat inversa”, hauria de dir “repartiments inversament proporcional” (el problema dels obrers serveix per qualque cosa)