Blog d’en Xavi

Archive for the ‘problemes’ Category.

mcd(0,a)=….

24th Juny 2008, 04:24 pm

L’altre dia llegint un llibre, vaig veure aquest que definia el mcd(a,b) com “el màxim comú divisor estrictament positiu de a i de b si a i b eren tots dos distints de zero i 0 altrament”.

Me va sorprendre aquesta definició i vaig intentar justificar-la (òbviament el cas que algun dels arguments fos zero) de dues maneres:

1. Amb la definició de divisor comú

Donats $a, b\in \mathbb{Z}$ , podem definir que c és un divisor comú de a i de b $\Leftrightarrow$ c és un divisor de a i c és un divisor de b simultàniament, i.e. $a = c \cdot e$ i $b = c \cdot f$ per alguns $e, f \in \mathbb{Z}$ (nota: aquesta és la definició més general de divisor. Hi ha altres definicions que exigeixen que c sigui distint de zero, per a què el concepte de divisor en la divisor entera i aquest concepte coincideixin. Ara bé, si elegim que c sigui distint de zero, aleshores no hi ha una correspondència entre múltiples i divisors d’un nombre).

Per tant, tenim que donats, a, b sencers, podem definir el conjunt de divisors de a i b com

$\text{Div}(a,b) =\{ c \text{ divisor com\'u de } a \text{ i } b\}$

I per tant, definir el màxim comú divisor de a i de b com:

$\text{mcd}(a,b) = \max \text{Div}(a,b)$

Aleshores si a no és zero, el mcd(a,0) és igual a

$\text{mcd}(a,0) = \max \text{Div}(a,0)$ $= \max (\text{Div}(a) \cap \text{Div}(0)) = \max (\text{Div}(a) \cap \mathbb{Z}) = a$

(ja que qualsevol nombre és divisor de zero)

$\text{mcd}(0,0) = \max \text{Div}(0,0)$ $= \max (\text{Div}(0) \cap \text{Div}(0)) = \max (\mathbb{Z} \cap \mathbb{Z}) = \max \mathbb{Z}$ que no existeix

Per tant, amb una definició raonable del mcd, arribem a la conclusió de què mcd(0,a) = a si a no és zero i que mcd(0,0) no existeix.

2. Amb un poc d’àlgebra (ideals amagats)

Ara bé, facem servir un poc d’Àlgebra.

Notem per $(a) = \{ m | \text{m\'ultiples de a}\} = \{0, a, -a, \ldots \} = \{k\cdot a | k \in \mathbb{Z}\}$ , i de forma més general

$(a_1, \ldots, a_r) = \{k_1 \cdot a_1 + \ldots k_r \cdot a_r | k_i \in \mathbb{Z}\}$

O sigui $(a_1, \ldots, a_r)$ és l’ideal general pel conjunt $\{a_1, \ldots, a_r\}$ a $\mathbb{Z}$

Es pot veure que donats a, b enters, tenim que:

$(a, b) = (\text{mcd}(a,b))$
$(a) \cap (b) =(\text{mcm}(a,b))$

Si b =0 i a no és zero, tenim que (a, 0) = (a). Per tant, el mcd(0,a) hauria de ser a.

Si a i b són zero, llavors, (0,0) = {0} = (0). Per tant, el mcd(0,0) hauria de ser 0.

Conclusions

Aleshores, amb tot, trec que:

una bona definició per mcd(0,a) seria a
una bona definició per mcd(0,0) seria 0
El llibre “s’equivocava”: de totes totes el mcd(0,a) no és zero (tenc dos arguments per demostrar divergències amb aquesta definició).

Algú més s’atreveix a donar un altra argument? Per favor, animeu-vos!

Categoria: problemes, llibres, reflexions, matemàtiques | 4 comentaris

Una proposta per al quilo

29th Maig 2008, 04:16 pm

El quilogram és la única unitat bàsica del Sistema Internacional que encara es defineix amb l’ús d’un artefacte (o sigui un objecte físic fabricat com a patró).

Fins fa poc el metre encara es definia utilitzant el patró que es conservava a París, o almenys com a mesura pràctica: es prenia com a metre el patró de París envers de tornar a mesurar el meridià terrestre. Actualment el metre es defineix en termes de constants naturals (la distància que recorre la llum en 1/299 792 458 segons).

Hi ha diverses raons per voler defugir de definicions basades en artefactes i adoptar definicions basades en constants naturals: el deteriode dels artefactes, la reproducció universal de les unitats de mesura, etc. Actualment s’intenta adoptar una definició normalitzada de quilogram, i de fet, hi ha diverses propostes.

Des d’aquí en llanç una: per què no definir-la com la curvatura espai-temps unitària? Per poder definir què és una curvatura espai-temps unitària simplement hauríem d’estudiar geometria i mesurar-la, per exemple, amb la desviació de la llum que estigués “molt aprop” de l’objecte…..

A veure si algú la secunda i li enviam al Bureau International des Poids et Mesures

Categoria: problemes, ganyotes, reflexions | Comentari

La distribució normal a processos de convocatòria periòdica

12th Maig 2008, 07:09 pm

Aquí teniu la distribució per edats dels docents de les Illes Balears. Per exemple, la dels Professors d’Ensenyament Secundari al Centres Públics a l’Illa de Mallorca és:

Anys Persones

20-24 5

25-29 285

30-34 650

35-39 588

40-44 529

45-49 397

50-54 290

55-59 184

60-64 75

Més de 64 9

Aquesta és una dada interessant: per una part, interessa als docents, ja que permet vislumbrar contra qui “competim” i quantes places és probable que surtin a concurs de trasllats/oposició l’any que ve (places que ocupen els majors de 64 anys); i per una altra perquè pareix que les dades es reparteixen segons una corba normal.

Realment és així? Si la resposta és afirmativa, quins paràmetres $\mu, \sigma$ fan que $N(\mu, \sigma)$ estigui el més aprop possible a les dades?. Aquestes preguntes són fàcilment responibles.

El que probablement no és tan fàcil de respondre és per què dades que sorgeixen d’un procés periòdic s’acaben modelant en forma de corba normal (si és que al final és així). Vull dir, idealitzant-ho tot molt: al principi dels temps ningú era professor. Els primers professors degueren ser les primeres persones que acabaren la carrera i que varen aprovar les primeres oposicions. Per tant, la distribució d’edats era de professors entre 20-24 anys i la resta 0. Després de anys, es tornen a convocar unes altres oposicions (per la nova fornada de llicenciats més la gent que no va aprovar les primeres). La gent que aprova aquestes oposicicions és o bé de 20-24 (els novell) o bé de 20-24 + k anys (els que no varen aprovar). Per tant, després de k anys, tenim una distribució composta per aquesta gent que aprova les oposicions més la gent que va aprovar les oposicions anteriors, de 20-24 + k (que n’hi ha X)…..

Si suposem que cada cop surten les mateixes places, que transcorren els mateixos anys entre oposició i oposició, i que la gent que aprova cada oposició està distribuïda igualitàriament entre la gent recent llicenciada, la gent que ha suspès unes oposicions, la gent que n’ha suspeses dues, etc. (ho sigui, el fet que un aprovi és independent dels anys que duu estudiant), aleshores algú pot provar que surt una normal al llarg del temps?

Categoria: problemes, reflexions, matemàtiques | 6 comentaris

El dia de les matemàtiques (i 2)

28th Abril 2008, 07:17 pm

L’altre dia parlàvem sobre quin dia seria el millor per posar el dia de les Matemàtiques. En Fèlix, va apuntar una molt bona idea: que canviàs amb els anys. I en Xesc va insinuar que ell seguia el dia de pi.

Doncs per què no els fussionam?

Si agafem els digits en base 10 de pi: 3.14159265358979323846…

Podríem definir la funció “la data de les matemàtiques” com f:N–>N^2, que assignàs a cada any, un parell ordenat (mes, dia), de manera que el mes i el dia tenguessin el major nombre de dígits possible. O sigui,

f(1) = (3, 14); podríem collir f(1) = (3, 1), però no és maximal. I (31, 4) no es correspon a cap data.

f(2) = (1, 5),

f(3) = (9,26),

f(4) = (5, 3),

etc.

Com calcularíeu el valor f(n) per a n arbitrari. No es fàcil, crec jo, dir-li a f que culli el parell maximal i que a més tengui sentit com a data. Hi ha una fórmula tancada recurrent senzilla? Què seria f(2008)? I f(2009)?. Heu de tenir en compte els anys de traspàs (perquè podreu collir la ocurrència (2,29) si apareix).

Categoria: problemes, reflexions, matemàtiques | 1 comentari

Un sistema diofàntic a resoldre

12th Abril 2008, 03:35 pm

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

$\begin{cases}4(s+1)\lambda \equiv 2 \mod s^2\\ (2s+3) \lambda \equiv 1 \mod (s+1)^2\end{cases}$

amb s senar.

Alguna idea?.

Categoria: problemes, matemàtiques | 6 comentaris

Ajuda: identitat de Bézout factoritzant a i b…

2nd Abril 2008, 07:56 pm

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?

Categoria: problemes, matemàtiques | 17 comentaris

Els coeficients del “polinomi factorial”

2nd Abril 2008, 04:19 pm

Podem definir $p_n(x) = \prod_{i=0}^{n-1} (x-i) = x (x-1) \ldots (x-(n-1))$ per a tot $n \geq 1$ . De manera trivial tenim que p_n(n) = n! , però quins són els coeficients de p_n(x) ? N’hi ha que són trivials ( a_n = 1 , a_0 = n! ), però n’hi ha que no (per exemple a_3 ). Algú s’hi atreveix?

Categoria: problemes, matemàtiques | 4 comentaris

Mínim de moviments (i 3)

22nd Març 2008, 05:49 pm

Una variació del problema del mínim de moviments per obtenir un conjunt apinyat al reticle $\mathbb{Z} \times \mathbb{Z}$ amb aplicació:

Sigui A un conjunt de $\mathbb{Z} \times \mathbb{Z}$ . 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 $\mathbb{Z} \times \mathbb{Z}$ , trobar un punt (no té perquè ser únic ni estar a A) tal que $\sum_{x \in A} d(x, a_A)$ sigui mínima.

Noteu que almenys un d’aquests sempre existirà. Si denotem la suma mínima com (i.e., $e(A) = \sum_{x \in A} d(x, a_A)$ ), 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, $e(A \cup B) \leq e(A) + e(B)$ (algú s’atreveix?; d’aquesta no n’estic tan segur com les anteriors). I llavors obtenir que $e(A) \leq \frac{Card(A)}{2} \cdot \frac{diam(A)}{2}$

Categoria: problemes, matemàtiques | Comentari

Mínim de moviments… 2a part

13th Març 2008, 07:23 pm

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 $\mathbb{Z}\times \mathbb{Z}$ . 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 $s(A \cup B) \leq s(A) + s(B)$ . Tenint en compte que si A té dos punts , on $diam(A) = max \{d(x,y) | x, y \in A \}$ , llavors $s(A) \leq \frac{Card(A)}{2} (diam(A)-1)$ (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 $\frac{7}{2} \cdot (3-1) = 7$ (!)

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) = $\sum_{a \neq b, a, b \in A} d(a, b)$

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

Categoria: problemes, matemàtiques | 1 comentari

Mínim de moviments

5th Març 2008, 11:23 am

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ó?