gcd e lcm

[mod_2]

Prendete alcuni interi positivi, scegliete due di loro a e b, e sostituiteli con gcd(a,b) e lcm(a,b). Così facendo formate un nuovo insieme di numeri positivi in cui tutti i numeri sono uguali a quelli dell'insieme di partenza tranne a e b che sono stati cambiati. Prendete questo nuovo insieme e ripetete lo stesso processo, così fino all'infinito.
Dire se da un certo punto in poi i numeri smetteranno di cambiare.

Secondo me molto carino e semplice

[Sonner]

Si, smetteranno di cambiare. Solo ho qualche problema a generalizzare

[mod_2]

Se vuoi puoi sempre postare dove sei arrivato/a

[Thebear]

Allora... Provo a postare la prima idea che mi è venuta in mente: poichè $ GCD(a,b) \cdot LCM(a,b)= a \cdot b $, il prodotto dei numeri è un'invariante del problema.

Ok, è davvero poco però devo studiare quella dannata letteratura inglese, quindi cedo la palla!

[julio14]

Ok, l'invariante va bene... ora cerca una cosa che varia, ma varia bene

[Thebear]

Provo un'altra via.

Caso A: I numeri sono a due a due primi tra loro.
Dopo una certa serie di passaggi si otterranno tanti "uni" e un numero uguale al prodotto dei numeri iniziali.

Caso B: i numeri non sono a due a due primi tra loro.
Dopo un certo numero di passaggi avremo tanti numeri uguali al GCD di tutti i numeri e un numero uguale al LCM.

In entrambi i casi presa una qualunque coppia a questo punto si avrà sempre $ GCD(a,b)=GCD $ di tutti i numeri e $ LCM(a,b)=x $ dove x è il numero più grande che dicevo prima.

Soluzione molto sbrigativa e informale...
Sarà almeno corretta?

[julio14]

Caso B: i numeri non sono a due a due primi tra loro.
Dopo un certo numero di passaggi avremo tanti numeri uguali al GCD di tutti i numeri e un numero uguale al LCM.

Questo come lo giustifichi? (pensa per esempio a 6;6;12;12)

[pak-man]

Caso B: i numeri non sono a due a due primi tra loro.
Dopo un certo numero di passaggi avremo tanti numeri uguali al GCD di tutti i numeri e un numero uguale al LCM.

Questo come lo giustifichi? (pensa per esempio a 6;6;12;12)

Forse si può correggere dicendo che alcuni numeri saranno uguali al GCD, tutti gli altri al LCM

[julio14]

Dimostra che non ci sono altri casi
(cmq, se la soluzione che pensa mod_2 è la stessa che penso io, è molto più carina )

[SkZ]

si vede molto facilmente che dato un insieme di $ ~x_i $ operando quella trasformazione sia avra' sempre $ ~GCD(\{x_i\})\leq x_j\leq lcm(\{x_i\}) $

wlog $ ~GCD(\{x_i\})=1 $
la molteplicita' di un numero e' invariante: se alla partenza ho n numeri uguali allora anche alla fine avro' n numeri uguali. Simmetria

cmq una volta che $ ~x_j=lcm(\{x_i\}) $, si puo' escludere