La sezione potrebbe essere sbagliata

[Fenu]

Ringrazio il caro "1729" per avermi consigliato questo problema davvero simpatico.
Siano $(a_i)$ e $(b_i)$ due sequenze di interi positivi rispettivamente lunghe $n$ ed $m$ tali che per ogni $k$, il numero di $a_i$ divisibili per $k$ sia minore o uguale al numero di $b_i$ divisibili per $k$.
Dimostrare che la somma degli $a_i$ è minore o uguale alla somma dei $b_i$.

[Parmenide]

Siccome $(a_i)$ e $(b_i)$ sono sequenze finite, allora esiste sicuramente $M=\max\lbrace a_i, b_i\rbrace$.
Ora $M\in (b_i)$ in quanto, se non vi appartenesse, allora si avrebbe $M\in(a_i)$, ma questo è assurdo in quanto scegliendo $k=M$ si ha che il numero degli $a_i$ divisibili per $M$ è uno, mentre il corrispondente per i $b_i$ è zero, contraddicendo l'ipotesi.

A questo punto sia $m=max\lbrace \lbrace a_i,b_i\rbrace \setminus \lbrace M\rbrace\rbrace$. Si hanno due casi:

Caso 1: $m$ non divide $M$. In questo caso si ha necessariamente $m\in(b_i)$, altrimenti scegliendo $k=m$ si contraddirebbe l'ipotesi, come prima.

Caso 2: $m|M$. Se $m\in(a_i)$ allora o $m\in(b_i)$ oppure $M\in(b_i)$ ma $M\not\in(a_i)$, per cui abbiamo già una differenza tra i due termini maggiori delle due sequenze a favore dei $(b_i)$

Considerando che $k=1$ implica $n\leq m$, ripetendo lo stesso procedimento appena descritto è chiaro che ad ogni passaggio si crea una differenza in favore dei $(b_i)$ o al massimo si aggiunge lo stesso elemento in entrambe. Da questo segue la tesi $\displaystyle{\sum_{i=1}^n a_i\leq \sum_{i=1}^m b_i}$

Aspetto correzioni

[Fenu]

A me sembra vada bene! Lascio anche quella che conosco io. Consideriamo $F_{a_i}$ (e similmente $F_{b_i}$)come l'insieme di tutti i $\varphi(d)$ per $d|a_i$ (in questo modo, per esempio, $F_9=\{\varphi(1), \varphi(3), \varphi(9)\}$). Notiamo anzitutto che la somma degli elementi di $F_{a_i}$ vale proprio $a_i$ (questa è una nota proprietà che si dimostra in mille modi). Le ipotesi del problema diventano ora "dato un $\varphi(k)$, allora la molteplicità di $\varphi(k)$ negli $F_{a_i}$ è minore o uguale alla molteplicità negli $F_{b_i}$" dato che un elemento $\varphi(k)$ è presente in un certo insieme $F_{a_i}$ se e solo se $k$ divide $a_i$ (e similmente per i $b_i$) per come lo abbiamo costruito. La somma di tutti gli $a_i$ corrisponde dunque alla somma di tutti i $\varphi(k) \cdot m_k$ dove $m_k$ corrisponde alla molteplicità (ossia quante volte è presente) di $\varphi(k)$. Dato che le molteplicità della sequenza $b_i$ valgono almeno quanto le molteplicità della sequenza $a_i$, segue che la somma dei $b_i$ vale almeno quanto la somma degli $a_i$.

[bern-1-16-4-13]

Siccome $(a_i)$ e $(b_i)$ sono sequenze finite, allora esiste sicuramente $M=\max\lbrace a_i, b_i\rbrace$.
Ora $M\in (b_i)$ in quanto, se non vi appartenesse, allora si avrebbe $M\in(a_i)$, ma questo è assurdo in quanto scegliendo $k=M$ si ha che il numero degli $a_i$ divisibili per $M$ è uno, mentre il corrispondente per i $b_i$ è zero, contraddicendo l'ipotesi.

A questo punto sia $m=max\lbrace \lbrace a_i,b_i\rbrace \setminus \lbrace M\rbrace\rbrace$. Si hanno due casi:

Caso 1: $m$ non divide $M$. In questo caso si ha necessariamente $m\in(b_i)$, altrimenti scegliendo $k=m$ si contraddirebbe l'ipotesi, come prima.

Caso 2: $m|M$. Se $m\in(a_i)$ allora o $m\in(b_i)$ oppure $M\in(b_i)$ ma $M\not\in(a_i)$, per cui abbiamo già una differenza tra i due termini maggiori delle due sequenze a favore dei $(b_i)$

Considerando che $k=1$ implica $n\leq m$, ripetendo lo stesso procedimento appena descritto è chiaro che ad ogni passaggio si crea una differenza in favore dei $(b_i)$ o al massimo si aggiunge lo stesso elemento in entrambe. Da questo segue la tesi $\displaystyle{\sum_{i=1}^n a_i\leq \sum_{i=1}^m b_i}$

Aspetto correzioni

Se ho ben capito stai cercando di applicare un’induzione. Tuttavia devi assicurarti che le ipotesi del testo siano nuovamente rispettate dopo che hai eliminato i due termini massimi, cosa che è falsa.

Un controesempio sono gli insiemi {30,2,3,5} e {15,10,6,1}}