Somma e divisori

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
mat94
Messaggi: 198
Iscritto il: 20 ago 2012, 10:29

Somma e divisori

Messaggio da mat94 »

Siano $a_1,...,a_n$ e $b_1,..,b_m$ interi positivi tali che per ogni intero positivo k si ha che il numero di $a_i$ divisibili per k è minore o uguale al numero di $b_j$ divisibili per k. Mostrare che $\sum a_i \leq \sum b_j$.
Avatar utente
Ratman98
Messaggi: 122
Iscritto il: 24 giu 2014, 13:52
Località: Battipaglia(Sa)

Re: Somma e divisori

Messaggio da Ratman98 »

Non scrivo la soluzione in maniera formale, perché senza LaTeX risulterebbe incomprensibile. Tuttavia, se ho ben ragionato, basta notare che ciascun 'a' è un 'k' e che quindi per ciascun 'a' esiste almeno un 'b' al minimo uguale ad 'a'. 8)
Ultima modifica di Ratman98 il 05 mar 2015, 13:18, modificato 1 volta in totale.
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Somma e divisori

Messaggio da Drago96 »

Penso che l'idea sia circa quella, ma ci sono dettagli fastidiosi da sistemare che si rivelano in realtà ardui...
Se ad $a_i$ associassi un $b_h$ e ad un altro $a_j$ associassi lo stesso $b_k$, ad esempio?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Avatar utente
Ratman98
Messaggi: 122
Iscritto il: 24 giu 2014, 13:52
Località: Battipaglia(Sa)

Re: Somma e divisori

Messaggio da Ratman98 »

Credo sia utile osservare che il numero di 'b' è maggiore o uguale al numero di 'a', poiché 1 è divisore comune di tutti gli 'a'. Per il resto, mi occorre tempo :lol:
Avatar utente
Ratman98
Messaggi: 122
Iscritto il: 24 giu 2014, 13:52
Località: Battipaglia(Sa)

Re: Somma e divisori

Messaggio da Ratman98 »

Scelgo un caso particolare, ma esemplare, per le ovvie difficoltà a scrivere senza LaTeX. Ammettiamo che sia: b=a*h=a**k=a***m ; dove gli asterischi servono ad identificare 'a' distinti tra loro . d=(a*,a**,a***) ≥ 1 , dove con d indico il massimo comune divisore. Poiché il massimo comune divisore divide i tre 'a', ci devono essere oltre al 'b' di prima, altri due 'b' al minimo uguali a d nella seconda somma, poiché il numero totale di 'b' deve essere maggiore o uguale al numero di 'a'. Ora mi piacerebbe dimostrare che a*+a**+a***≤b+ 2d o meglio che 3(a*+a**+a***)≤a*h+a**k+a***m+6d. Questa disugualianza mi pare sempre vera, ma qui mi fermo. Mi scuso per l'aver lasciato tutto nell'indefinito e nell'aleatorio(tra l'altro credo di essere lontano dalla soluzione). Confido nella vostra pazienza :lol:
Avatar utente
Ratman98
Messaggi: 122
Iscritto il: 24 giu 2014, 13:52
Località: Battipaglia(Sa)

Re: Somma e divisori

Messaggio da Ratman98 »

Viste le pecche colossali del mio ultimo post, per ora rispondo almeno al caso prospettato da drago96.Se un B è uguale al prodotto di n 'a' distinti, questo prodotto sarà sempre maggiore della somma di questi 'a', a meno che uno o più di questi 'a' siano uguali ad 1. Ma in tal caso possiamo associare alla somma di questi 'a', B insieme con (n-1) 'b' non necessariamente multipli degli altri 'a'(quelli che non dividono B) e maggiori o uguali ad 1(che esistono per la considerazione fatta due post fa). La prima quantità risulta sempre minore o uguale alla seconda. Se sono stato poco chiaro, ditelo apertamente. Non vorrei che a causa mia il topic di mat94 rimanesse"appeso".
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Somma e divisori

Messaggio da Drago96 »

Chiederei un hint, anche perché mi sono fissato con il polinomio $\sum x^{b_i}-\sum x^{a_i}$ cavandone fuori ben poco, e tutte le altre idee mi sembrano meno interessanti...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
mat94
Messaggi: 198
Iscritto il: 20 ago 2012, 10:29

Re: Somma e divisori

Messaggio da mat94 »

Testo nascosto:
prova a usare i polinomi ciclotomici
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Somma e divisori

Messaggio da Drago96 »

WOW! :D
Associamo alla prima sequenza il polinomio $\displaystyle A(x)=\prod(x^{a_i}-1)=(x^{a_1}-1)(x^{a_2}-1)\cdots(x^{a_n}-1)$ e alla seconda allo stesso modo il polinomio $\displaystyle B(x)=\prod(x^{b_i}-1)=(x^{b_1}-1)(x^{b_2}-1)\cdots(x^{b_m}-1)$.
Ora, sappiamo che esistono dei meravigliosi polinomi $\Phi_i(x)$ a coefficienti interi tali che $x^n-1=\prod_{d\mid n}\Phi_d(x)$ per ogni $n$.
Chiamiano $\alpha_i$ il numero di $a_j$ multipli di $i$, e $\beta_i$ il numero di $b_j$ multipli di $i$; l'ipotesi è che $\beta_i\ge\alpha_i$ per ogni $i$ (da $1$ al massimo delle due sequenze).
Bene, adesso la magia...
$\displaystyle A(x)=\prod_{i=1}^n(x^{a_i}-1)=\prod_{i=1}^n\prod_{d\mid i}\Phi_d(x)=\prod_{d\ge1}\Phi_d(x)^{\alpha_d}$ perché fissato un $d$, il polinomio $\Phi_d(x)$ compare nella fattorizzazione di tutti e soli gli $x^{a_i}-1$ con $d\mid a_i$, che sono esattamente $\alpha_i$
Similmente, vale $\displaystyle B(x)=\prod_{d\ge1}\Phi_d(x)^{\beta_d}$
Consideriamo ora $\displaystyle\frac{B(x)}{A(x)}=\prod_{d\ge1}\Phi_d(x)^{\beta_d-\alpha_d}$; per ipotesi ogni esponente è non negativo, quindi quella frazione algebrica è in realtà un polinomio vero e proprio, che quindi ha un suo grado $\ge0$ (potrebbe essere il polinomio costante $1$ se le due sequenze sono uguali).
Ma allora deve essere anche $\deg B\ge\deg A$; chi sono però i gradi? Dalla definizione abbiamo proprio $\deg A=\sum a_i$ e $\deg B=\sum b_i$, e quindi abbiamo finito. :)

Davevvero interessante questo problema! ;)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
mat94
Messaggi: 198
Iscritto il: 20 ago 2012, 10:29

Re: Somma e divisori

Messaggio da mat94 »

Esatto! E' quella la soluzione che ti dicevo ed è un problema molto interessante :D
Rispondi