Minimi comuni multipli grossi, ma non troppo

[Simo_the_wolf]

Molto carino, dalle EGMO di quest'anno

(i) Dimostrare che, dati $ 6n $ numeri naturali distinti, c'è almeno una coppia in essi il cui minimo comune multiplo è più grande di $ 9n^2 $

(ii) Dimostrare che esistono $ 6n $ naturali, tali che qualunque coppia di numeri tra essi abbia minimo comune multiplo minore di $ 32n^2 $

[mat94]

Per il momento ho fatto solo il punto ii). Infatti basta prendere tutti i numeri da 1 a 4n e tutti i pari da 4n a 8n, così si ha che il minimo comune multiplo tra due di essi è minore di $32n^2$ e abbiamo considerato 6n numeri.

[dario2994]

Per il momento ho fatto solo il punto ii). Infatti basta prendere tutti i numeri da 1 a 4n e tutti i pari da 4n a 8n, così si ha che il minimo comune multiplo tra due di essi è minore di $32n^2$ e abbiamo considerato 6n numeri.

Giusto

Per dare un senso a questo messaggio aggiungo: una versione appena un po' più forte (ma in realtà solo più bruttina e dalla dimostrazione analoga) del punto i) era il problema 6 di un tst cinese di non so che anno. (questo non vuol dire che è impossibile!)
Aggiungo anche che è proprio figo il punto i).

[Ouroboros]

Spero di aver beninteso il problema... ecco la soluzione parziale che propongo del punto I
Per semplicità considero sei numeri (n=1): ovviamente devo cercare di considerare numeri che abbiano molti divisori in comune... infatti, se non faccio così posso verificare facilmente che almeno una coppia dà come risultato almeno 9 (ad esempio, se prendo i primi sei numeri naturali, 5x4 = 20)
Quindi considero 0, 1, m, 2m, 3m e 6m. Affinché tutti i numeri siano distinti, n è diverso da 1 (e ovviamente da 0), quindi prendendo il caso più semplice (m=2), ho 0, 1, 2, 4, 6, 12: ovviamente esiste almeno una coppia il cui mcm è maggiore di 9. Lo stesso vale per ogni m > 2 (suppongo che sia una funzione crescente...).
Non sono del tutto sicuro per n>1: non so se ho intuito il metodo corretto di costruire sequenze "scaltre", per esempio per n=2 potrei avere i sei già detti e in più 12m, 18m, 24m, 36m, 48m, 54m (mcm alto 72m) oppure esistono sequenze con un mcm più basso? (ho provato con i primi sei e 4m, 8m, 9m, 12m, 16m e 18m ma l'mcm più alto è 144m, se introduco il 5 posso scrivere 4m, 5m, 8m, 9m, 10m, 12m, mcm 60m, quindi più basso, ma ancora soddisfa la mia richiesta poiché m=2)...
Sono ben accetti chiarimenti e correzioni

[mat94]

Proviamo la parte i). Consideriamo $a_1<..<a_{6n}$ la 6n-upla di elementi distinti da considerare. Se uno degli $a_i$ è maggiore di $9n^2$ si ha banalmente la tesi. Ora supponiamo che il massimo tra tutti gli mcm tra le coppie di $a_i$ sia minore o al più uguale di $9n^2$ e che tutti gli $a_i$ siano minori $9n^2$. Siano x e y due qualsiasi degli $a_i$. Dato che $lcm(x,y)\cdot gcd(x,y)=xy$ si ottiene $9n^2\geq lcm(x,y)=\frac{xy}{gcd(x,y)}\geq \frac{xy}{|x-y|}$ dove nell'ultima disuguaglianza abbiamo sfruttato il fatto che il gcd tra due numeri divide la loro differenza quindi può essere al massimo tale differenza. Posto x>y si ha $\frac{1}{y}-\frac{1}{x}\geq \frac{1}{9n^2}$. A questo punto sommiamo la differenza delle coppie degli inversi consecutivi degli $a_i$ per i che va da 3n a 6n e otteniamo: $\frac{1}{a_{3n}}-\frac{1}{a_{3n+1}}+-...-\frac{1}{a_{6n}}=\frac{1}{a_{3n}}-\frac{1}{a_{6n}}\geq \frac{3n}{ 9n^2}=\frac{1}{3n}$ dove abbiamo applicato il risultato ottenuto in precedenza alle $3n$ coppie di inversi consecutivi da 3n a 6n-1. Ma dato che $a_{3n}$ è almeno 3n si ha che $\frac{1}{a_{3n}}-\frac{1}{a_{6n}}< \frac{1}{3n}$, un assurdo dato che $\frac{1}{a_{3n}}\leq \frac{1}{3n}$. Allora è il caso che almeno una coppia abbia mcm maggiore di $9n^2$.

[dario2994]

Proviamo la parte i). Consideriamo $a_1<..<a_{6n}$ la 6n-upla di elementi distinti da considerare. Se uno degli $a_i$ è maggiore di $9n^2$ si ha banalmente la tesi. Ora supponiamo che il massimo tra tutti gli mcm tra le coppie di $a_i$ sia minore o al più uguale di $9n^2$ e che tutti gli $a_i$ siano minori $9n^2$. Siano x e y due qualsiasi degli $a_i$. Dato che $lcm(x,y)\cdot gcd(x,y)=xy$ si ottiene $9n^2\geq lcm(x,y)=\frac{xy}{gcd(x,y)}\geq \frac{xy}{|x-y|}$ dove nell'ultima disuguaglianza abbiamo sfruttato il fatto che il gcd tra due numeri divide la loro differenza quindi può essere al massimo tale differenza. Posto x>y si ha $\frac{1}{y}-\frac{1}{x}\geq \frac{1}{9n^2}$. A questo punto sommiamo la differenza delle coppie degli inversi consecutivi degli $a_i$ per i che va da 3n a 6n e otteniamo: $\frac{1}{a_{3n}}-\frac{1}{a_{3n+1}}+-...-\frac{1}{a_{6n}}=\frac{1}{a_{3n}}-\frac{1}{a_{6n}}\geq \frac{3n}{ 9n^2}=\frac{1}{3n}$ dove abbiamo applicato il risultato ottenuto in precedenza alle $3n$ coppie di inversi consecutivi da 3n a 6n-1. Ma dato che $a_{3n}$ è almeno 3n si ha che $\frac{1}{a_{3n}}-\frac{1}{a_{6n}}< \frac{1}{3n}$, un assurdo dato che $\frac{1}{a_{3n}}\leq \frac{1}{3n}$. Allora è il caso che almeno una coppia abbia mcm maggiore di $9n^2$.

Corretto (all'ultima riga forse una disuguaglianza è invertita)