Replacing numbers
Inviato: 11 nov 2009, 03:13
Fissiamo n>1 interi positivi e sostuiamo a ogni passo due di essi a,b con gcd(a,b) e lcm(a,b). Mostrare che dopo un numero finito di passi gli n numeri restano definitivamente costanti.
Ci provo.
È noto che $ $\gcd(a,b) \cdot \text{lcm}(a,b) = a \cdot b$ $ (vedi qui, formula 14), da cui il prodotto di tutti gli interi scelti è invariante rispetto ad un qualunque passo.
Inoltre per due interi qualsiasi $ $a \geq b$ $ vale $ $\gcd(a,b) \leq b \leq a \leq \text{lcm}(a,b)$ $, e le uguaglianze ai lati solo se a è un multiplo intero di b.
Allora, se per ogni (a,b) che andiamo a scegliere abbiamo che a è multiplo di b, gli n numeri rimangono costanti, dato che a = lcm(a,b) e b = gcd(a,b) per qualunque scelta di (a,b).
Altrimenti, dato che il prodotto di tutti gli interi è costante e per la disuguaglianza sopracitata a cresce e b decresce ad ogni passo, arriveremo infine ad avere una serie di 1 ed un solo numero maggiore di 1; e si vede che anche in questo caso gli n rimangono costanti.
