Sostituzione con gcd e lcm

[jordan]

Fissiamo un po' di interi positivi $a_1,a_2,\ldots,a_n$ non necessariamente distinti. Una mossa consiste nello scegliere due di essi e sostituirli con il loro massimo comun divisore e il loro minimo comune multiplo. Mostrare che da un certo punto in poi non potremmo piu' cambiare alcun numero.

[auron95]

Chiamo A l'insieme delle coppie $\{a_i,a_j\}$ tali che uno degli elementi divide l'altro. Se una coppia appartiene ad A, allora non posso sostituirli: il più piccolo è gcd e il più grande è il lcm. Se dimostro che a ogni sostituzione il numero di coppie $\in A$ aumenta, dopo un numero finito di sostituzioni tutte le $\binom n2$ apparterrano ad A e si verificherà la tesi.

Sostituiamo la coppia $\{a_x,a_y\}$ non appartenente ad A con il lcm e il gcd. Tutte le coppie che non includono $a_x$ o $a_y$ ovviamente non cambiano, quindi non modificano la cardinalità di A. Ovviamente, poiche $\gcd \mid lcm$ allora $\{a_x,a_y\}$, allora questa coppia adesso appartiene ad A, quindi se altre coppie non escono dall'insieme allora la cardinalità aumenterà.
Dobbiamo controllare cosa succede alle coppie del tipo $\{a_i,a_x\}$ o $\{a_i,a_y\}$.
Se nessuna delle due coppie apparteneva ad A, allora la cardinalità al peggio resta uguale.
Se una sola apparteneva ad A (wlog $\{a_i,a_x\}\in A$)allora sicuramente è stata sostituita da $\{a_i,lcm(a_x,a_y)\}$, in quanto $a_i \mid a_x \mid lcm(a_x,a_y)$.
Se entrambe appartenevano ad A allora sono state sostituite da $\{a_i,\gcd(a_x,a_y)\}$ e $\{a_i, lcm(a_x,a_y)\}$, poichè se un numero ne divide altri due, allora ne divide il massimo comun divisore e quindi anche il minimo comune multiplo.
Ma allora ho finito, perchè la cardinalità di A aumenta sempre: infatti aggiungo sempre ad A la coppia sostituita e le altre coppie che sono coinvolte nella sostituzione vengono almeno rimpiazzate da altrettante coppie.

[jordan]

Sostituiamo la coppia $\{a_x,a_y\}$ non appartenente ad A con il lcm e il gcd.[/tex]

Dovresti specificare che $1\le x < y \le n$

Dobbiamo controllare cosa succede alle coppie del tipo $\{a_i,a_x\}$ o $\{a_i,a_y\}$.

Con $i \in \{1,\ldots,n\} \setminus \{x,y\}$

Se nessuna delle due coppie apparteneva ad A, allora la cardinalità al peggio resta uguale.

Giusto

Se una sola apparteneva ad A (wlog $\{a_i,a_x\}\in A$)allora sicuramente è stata sostituita da $\{a_i,lcm(a_x,a_y)\}$, in quanto $a_i \mid a_x \mid lcm(a_x,a_y)$.

Non è completo: se wlog $\{a_i,a_x\} \in A$ allora non è vero necessariamente che $a_i \mid a_x$..

Se entrambe appartenevano ad A allora sono state sostituite da $\{a_i,\gcd(a_x,a_y)\}$ e $\{a_i, lcm(a_x,a_y)\}$, poichè se un numero ne divide altri due, allora ne divide il massimo comun divisore e quindi anche il minimo comune multiplo.

Anche qui, non è completo: se $\{a_i, a_x\} \in A$ e $\{a_i,a_y \} \in A$, allora potrebbe anche essere che $a_x \mid a_i \mid a_y$..

Ps. La mia soluzione è del tutto diversa..

[auron95]

Eh sì, ho scritto un po' frettolosamente.

Se una sola apparteneva ad A (wlog $\{a_i,a_x\}\in A$)allora sicuramente è stata sostituita da $\{ai,lcm(a_x,a_y)\}$, in quanto $a_i\mid a_x\mid lcm(a_x,a_y)$.

Non è completo: se wlog $\{a_i,a_x\}∈A$ allora non è vero necessariamente che $a_i\mid a_x$.

Devo dividere due casi:
$a_i\mid a_x \mid lcm(a_x,a_y)$ quindi $\{a_i,lcm(a_x,a_y)\} \in A$
oppure
$a_x\mid a_i$ ma $\gcd(a_x,a_y) \mid a_x$ quindi $\{\gcd(a_x,a_y),a_i\}\in A$

Se entrambe appartenevano ad A allora sono state sostituite da {ai,gcd(ax,ay)} e {ai,lcm(ax,ay)}, poichè se un numero ne divide altri due, allora ne divide il massimo comun divisore e quindi anche il minimo comune multiplo.

Anche qui, non è completo: se {ai,ax}∈A e {ai,ay}∈A, allora potrebbe anche essere che ax∣ai∣ay..

Si presentano tre casi

• $a_x\mid a_i \mid a_y$ (o viceversa, scambiando x e y) contraddice le ipostesi perchè $a_x\nmid a_y$.
  $a_i \mid a_x,\ a_i \mid a_y \Rightarrow a_i \mid \gcd(a_x,a_y) \mid lcm (a_x,a_y)$
  $a_x \mid a_i, \ a_y\mid a_i \Rightarrow \gcd(a_x,a_y)\mid lcm(a_x,a_y)\mid a_i$

In tutti i casi le due nuove coppie che coinvolgono $a_i$ sono sostituite da altre in $A$

Con queste aggiunte dovrebbe funzionzare meglio.
Se vuoi postare la tua soluzione (o mandarmela via mp) sono curioso di vedere un altro metodo (spero di riuscire a capirla, da buon novellino, perchè quando cominciano a esserci funzioni generatrici o altre cose mi perdo )

[xXStephXx]

Io avevo pensato ad un'induzione che non so quanto sia corretta...
Passo base: se ci sono solo due numeri ci si blocca dopo la prima mossa.
Ipotesi induttiva: ci si blocca con $n$ numeri.
Tesi induttiva: ci si blocca con $n+1$ numeri.
Dimostrazione:
Metto da parte un numero $a_{n+1}$. Ora se opero solo con i primi $n$ numeri mi blocco per ipotesi induttiva, quindi prima o poi devo coinvolgere anche $a_{n+1}$. Affinchè questa mossa abbia senso, devo applicarla tra $a_{n+1}$ ed un altro numero $a_x$ che non divide $a_{n+1}$ e a sua volta non viene diviso da $a_{n+1}$. Il risultato sarà che compare un nuovo numero che vale $mcm(a_{n+1}, a_{x})$ che sarà il "nuovo $a_{n+1}$ " ovvero l'elemento che sostituisce quello che prima era $a_{n+1}$. Questo nuovo numero contiene sicuramente qualche fattore in più rispetto al "vecchio" $a_{n+1}$. Dopodichè ripeto il "ciclo". Se opero solo con i primi $n$ numeri mi blocco di nuovo e prima o poi dovrò coinvolgere di nuovo l'ultimo elemento. Quest'ultimo elemento guadagnerà sempre qualche fattore che prima non aveva e il massimo a cui può arrivare dopo diversi cicli sarà $mcm(a_1,a_2,...,a_{n+1})$ in quanto operando con la mossa consentita i fattori presenti all'inizio si "conservano" e non possono comparire fattori che prima non erano presenti in alcun numero. Ma una volta che $a_{n+1}$ acquisisce tutti i fattori presenti tra i vari numeri, non è più possibile operare con $a_{n+1}$ poichè è divisibile per tutti gli altri numeri e quindi la mossa non ha più senso. Da questo momento in poi sarà necessario usare solo i primi $n$ numeri bloccandosi prima o poi per ipotesi induttiva.

[Simo_the_wolf]

Salve, mi permetto di rispondere anch'io perché secondo me c'è una soluzione più "generale". Innanzitutto osservo che, dati due naturali $a \leq b$, detti $c=gcd(a,b)$ e $d=lcm(a,b)$, si ha che $ab=cd$. Inoltre si ha anche $c \leq a \leq b \leq d$; A questo punto è semplice vedere che $a+b \leq c+d$ infatti si ha $a+b-c-d=-(d-b)(d-a)/d \leq 0$ con uguaglianza se e solo se $d=b$, che implica anche $c=a$.

Ora sappiamo che, nel nostro gioco i numeri non eccederanno mai $lcm(a_1, \ldots , a_n)$; consideriamo ora la somma dei numeri. Essa cresce, per quanto osservato prima, ma è limitata da $nlcm(a_1, \ldots , a_n)$. Quindi vuol dire che da un certo punto in poi la somma è costante e quindi, sempre per quanto detto prima, se sto facendo mosse, esse non cambiano nulla.

[jordan]

La mia soluzione si basa sull'idea di Simo, sopra:

Just for definition we start we integers $a_1,a_2,\ldots,a_n$ and at $m$-th step (with $m \in \mathbb{N}\setminus \{0\}$) we have integers $a_{m,1},a_{m,2},\ldots,a_{m,n}$. Notice that if we have integers $a_{m,1} \le a_{m,2} \le \ldots \le a_{m,n}$ at some step $m$ such that $a_{m,i} \mid a_{m,i+1}$ for all $i=1,2,\ldots,n-1$, then noone integer will be changed. We can also show that this is the unique way to end this algorithm. It's clear that $\text{gcd}(a_i,a_j)\text{lcm}(a_i,a_j)=a_ia_j$ for some $1\le i<j\le n$, so that $$\prod_{1\le i\le n}{a_i}=\prod_{1\le i \le n}{a_{m,i}}\text{ for all }m \in \mathbb{N}\setminus \{0\}.$$ In particular, since the product is constant then there exists a positive integer $M$ such that $\sum_{1\le i\le n}{a_{m,i}} \le M$, indipendently from the value of $m$. Define $M_0:=\sum_{1\le i\le n}{a_i}$, and $M_m:=\sum_{1\le i\le n}{a_{m,i}}$. We claim finally that there exist $1\le i<j\le n$ and $m \in \mathbb{N}\setminus \{0\}$ such that $a_{m,i} \le a_{m,j}$ and $a_{m,i}\nmid a_{m,j}$ then $M_{m+1}>M_m$, i.e. we have to show that $$M_{m+1}-M_m=\text{gcd}(a_{m,i},a_{m,j})+\text{lcm}(a_{m,i},a_{m,j})-a_{m,i}-a_{m,j}$$
is strictly positive. Define $x:=a_{m,i}$, $y:=a_{m,j}$, $g:=\text{gcd}(a_{m,i},a_{m,j})$ and $P:=a_{m,i}a_{m,j}$. Then we have to show that $$\left(g+\frac{P}{g}\right)-\left(x+\frac{P}{x}\right)>0$$ under the assumption that $0<g<x<\sqrt{P}<y<\frac{P}{g}<P$. But the function $f(x)=x+Px^{-1}$ is strictly decreasing in $[0,\sqrt{P})$, and that's enough to conclude. Assuming that the algorithm will never stop, we created a strictly increasing sequence of positive integers $M_0<M_1<M_2<\ldots$ such that $M_m \le M$ for all $m \in \mathbb{N} \setminus \{0\}$, and that's a contradiction.

[jordan]

Bien, funzionano sia quella di auron che quella di Steph!