Minimizzare la somma di quadrati di interi con somma fissa

[dario2994]

Alur... volevo chiedere se qualcuno aveva una dimostrazione elegante di questo fatto (alla fin fine andrebbe bene anche non elegante... ):
Dati m,n interi positivi; se n numeri interi hanno somma m e minimizzano la somma dei quadrati allora presi 2 a caso differiscono al massimo di 1.
Minimizzare la somma dei quadrati vuol dire che tra tutte le n-uple di interi con somma m nessuna ha somma dei rispettivi quadrati minore.

[Spammowarrior]

$ \displaystyle \frac{a_{1}^2 + a_{2}^2 + ... + a_{n}^2}{n} \geq \frac{(a_{1} + a_{2} + ... + a_{n})^2}{n^2} $

l'uguaglianza c'è solo quando gli a sono tutti uguali tra loro (QM-AM)

semplifico una n e ho a destra una costante:
$ \displaystyle \frac{m^2}{n} $

il lhs è sempre maggiore ed è uguale se sono tutti uguali, quindi è il minimo in questo caso.
quindi presi due a caso avranno sempre somma 0.

ok, visto che mi sembra facilino e ho dimostrato un risultato molto più forte, ho sbagliato da qualche parte missà :S

[dario2994]

Hai dimenticato che sono interi.

[pic88]

Va beh ma quella cosa vale anche se ce n'e' qualcuno di negativo, no?

[dario2994]

Quale cosa?

[tenaciousR]

ragioniamo in R.sappiamo,per la disuguaglianza delle medie,che la somma dei quadrati dei numeri aventi somma fissata è minima quando sono uguali (scaturisce da Q>o uguale ad A).In N,si dovrà approssimare all'unità più vicina,quindi la differenza massima sarà 1(questa è la soluzione poco elegante)

[pic88]

La disuguaglianza...
si puo' assumere m>0, quindi vale che $ (|a_1|+...+|a_n|)^2\geq m^2 $

EDIT: si, ok, ora ho capito cosa intendevi.

[dario2994]

No questa è la soluzione poco matematica.
EDIT: @Pic88 qua c'era scritta un'altra cosa, ma se tu hai capito cosa intendevo (o intendeva) meglio così xD

[Spammowarrior]

giusto

ok, allora prendiamo due numeri a caso, e dimostriamo che se hanno differenza maggiore di uno possiamo sostituirli con due numeri con differenza minore o uguale a uno che diminuiscono la somma dei quadrati (di conseguenza, se per assurdo due degli addendi differissero per più di uno la somma dei quadrati non sarebbe minima)

a+b devono avere somma fissa = k

prendiamo wlog b>=a
$ a = k - b $
$ f(x)= b^2 + k^2 + b^2 - 2kb $

f(x) è una parabola, che quindi è minima nel vertice, e ha come minimo intero l'ascissa intera più vicina al vertice:
$ x_{v}= - \frac {-2k}{4} $

se k pari allora b=k/2 e a = k/2
se k dispari allora b= (k+1)/2 e a=(k-1)/2

quindi se sostituisco ai due addendi ipotizzati i due addendi che ho trovato così, la somma non cambia e la somma dei quadrati diminuisce.

edit: sbagliato una cosina.
ero anche pronto a partire con derivate e studi di funzioni ma ho preferito rimanere sull'elementare

[pic88]

Piu' semplicemente, $ a^2+(a+n)^2 > (a+1)^2 + (a+n-1)^2 $, e usare $ a+1, a+n-1 $ riduce la distanza quando $ n>1 $.

Ad essere rigorosi tu hai mostrato che una configurazione con una distanza >1 non e' minima, andrebbe aggiunto che il minimo esiste per concludere che, nella configurazione minima, devono avere tutti ditanza al piu' 1.

[Spammowarrior]

beh, è abbastanza elementare, basta dire che la somma dei quadrati è un naturale, e non esistono successioni infinitamente decrescenti sui naturali.

no, beh, a dire il vero no:
io ho dimostrato che se per assurdo due numeri hanno distanza >1 allora la configurazione non è minima, che è un assurdo (è minima per ipotesi)

[pic88]

Si, ma fa perdere punti. Mica per altro lo dico!

[Spammowarrior]

ho editato il messaggio precedente, la mia dimostrazione era leggermente diversa da come l'hai intesa, era per assurdo

[pic88]

ho editato il messaggio precedente, la mia dimostrazione era leggermente diversa da come l'hai intesa, era per assurdo

Eh, ma partiva da "sia a_1,...,a_n" una configurazione minima. Va prima detto che esiste. So che e' elementare ma siamo pur sempre nel glossario.

[dario2994]

Uhm... si questa era la soluzione "non elegante", ma mi accontento, grazie :)