Disuguaglianza di riordinamento

[Gi.]

Non so se ho capito bene come funziona, per cui chiedo.
In pratica se abbiamo due n-uple $ (x_1,x_2,...,x_n) $ e $ (y_1,y_2,...,y_n) $ risulta che la somma delle coppie del tipo $ (x_i *y_k) $ è minima quando moltiplico il più piccolo con il più piccolo, il secondo più piccolo con il secondo più piccolo, ecc. ed è massima quando moltiplico il più grande con il più piccolo, il secondo più grande con il secondo più piccolo, ecc.. In generale un qualsiasi accoppiamento a caso risulta $ \ge $ dell' accoppiamento più piccolo con più piccolo, ecc. e $ \le $ di quello più grande con più piccolo, ecc.
Ho capito bene? Potreste mostrarmi qualche problema che si risolve con tale metodo?

p.s. scusate il linguaggio brutale

[Drago96]

Innanzitutto, di solito si chiama riarrangiamento, però vabbè...
Ma c'è una cosa ben più grave del nome: il verso, direi abbastaza fondamentale in una disuguaglianza.
Infatti riarrangiamento è:
Date due $n$-uple di reali $(a_1,\dots,a_n)$ e $(b_1,\dots,b_n)$ con $a_1\le a_2\le\dots\le a_n$ e $b_1\le b_2\le\dots\le b_n$ e $\sigma(\cdot)$ permutazione di $\{1,2,\dots,n\}$ allora vale $$\displaystyle\sum_{i=1}^na_ib_{n-i+1}\le\sum_{i=1}^na_ib_{\sigma(i)}\le\sum_{i=1}^na_ib_i$$ In parole povere, hai il massimo quando accoppi il più grande con il più grande, ecc... mentre hai il minimo quando accoppi il più grande con il più piccolo, ecc... Proprio il contrario di quello che hai detto tu.

Esempio banale: ti danno un tot di cifre e ti chiedono di scrivere il più grande ed il più piccolo numero possibile. Tu allora le scrivi in ordine decrescente per il massimo (ovvero, la cifra più alta è la più a sinistra) e in ordine crescente per il minimo; ebbene, stai applicando inconsciamente riarrangiamento sulla $n$-upla delle cifre e su quella delle potenze di 10

Esempio classico: Vedi post più in basso...

Nascondo questo esempio che è un nesbitt al contrario e direi ben poco istruttivo

Testo nascosto:

Dati $a,b,c$ reali positivi, allora vale
$$\displaystyle\frac{a+b}c+\frac{b+c}a+\frac{c+a}b\ge\frac3 2$$
E' simmetrica (perchè se scambi due variabili non cambia), quindi puoi imporre WLOG (without loss of generality) $a\ge b\ge c$ e di conseguenza $\displaystyle\frac1 c\ge\frac1 b\ge\frac 1 a$ (perchè sono positivi).
Per riarrangiamento il minimo è $\displaystyle a\cdot\frac1 a+b\cdot\frac1 b+c\cdot\frac1 c=3$; in paricolare $\displaystyle\frac a c+\frac b a+\frac c b\ge3$ e $\displaystyle\frac b c+\frac c a+\frac a b\ge3$, che sommate danno la tesi

Spero ti sia chiaro!
Anche se sembra banale, in realtà è molto potente, anche perchè non ha bisogno di vincoli di positività per essere usata, al contrario delle disuguaglianze sulle medie

[ndp15]

che sommate danno la tesi

Che infatti è $ roba\ge 6 $ e non di $ 3/2 $

P.S specifichiamo: chiaramente se dimostri che è maggiore di 6 mostri che è maggiore di 3/2, solo che 6 è il migliore bound possibile mentre con 3/2 la disuguaglianza si dimostra facilmente anche senza ricorrere alla disuguaglianza di riarrangiamento.

[Gi.]

Ok, tutto chiaro, adesso non mi resta che rispolverare la sezione Algebra alla ricerca di qualche problema con cui sperimentare questa tecnica.
Grazie $ 10^3 $ Drago

[Drago96]

Oddio, epic fail!
Quella cosa che ho scritto si fa effettivamente molto semplicemente con $\displaystyle\frac x y+\frac y x\ge2$ (e viene fuori lo stesso il 6), ma io intendevo scrivere Nesbitt... -.-"

Bene allora, esempio classico vero
$$\displaystyle\frac a{b+c}+\frac b{c+a}+\frac c{a+b}\ge\frac3 2$$
Le sequenze $a,b,c$ e $\displaystyle\frac 1{b+c},\frac 1{c+a},\frac 1{a+b}$ sono ordinate nello stesso modo (sempre perchè positivi), quindi la somma massima è quella del testo, e in particolare $\displaystyle\frac a{b+c}+\frac b{c+a}+\frac c{a+b}\ge\frac b{b+c}+\frac c{c+a}+\frac a{a+b}$ e $\displaystyle\frac a{b+c}+\frac b{c+a}+\frac c{a+b}\ge\frac c{b+c}+\frac a{c+a}+\frac b{a+b}$ e qua sommando si ottiene veramente la tesi

[Gi.]

Sorgono i primi dubbi.
Prendiamo questo problema ed in particolare la risposta di thematrix che lo risolve con il riarrangiamento.

La prima parte l' ho capita, considero le due terne $ (x^3,y^3,z^3) $ e $ (\frac{1}{yz} \frac{1}{zx} \frac{1}{xy}) $, impongo WLOG $ x\ge y\ge z $ ed il massimo ce l' ho per $ \displaystyle \frac{x^3}{yz}+\frac{y^3}{zx}+\frac{z^3}{xy} $ (il testo del problema).
Adesso ho $ \displaystyle \frac{x^3}{yz}+\frac{y^3}{zx}+\frac{z^3}{xy} \ge \frac{x^3}{xy}+\frac{y^3}{zx}+\frac{z^3}{yz} $ (cioè $ MAX \ge MIN $), bene, non capisco perchè il RHS è uguale a $ \displaystyle \frac{x^2}{y}+\frac {y^2}{z}+\frac{z^2}{x} $

[ma_go]

il RHS *non* è uguale a quello che vuoi. ma in particolare MAX $\ge$ qualunque altra scelta, e la scelta di accoppiare $x^3$ con $1/xy$, $y^3$ con $1/yz$ e $z^3$ con $1/zx$ ti dà la disuguaglianza che ti serve. suppongo che fosse quello che thematrix voleva dire, anche se non ho la palla di cristallo e non posso saperlo.

[Gi.]

Quindi, come prima considero le due terne $ (x^3,y^3,z^3) $ e $ (\frac{1}{yz}, \frac{1}{zx}, \frac{1}{xy}) $, suppongo WLOG $ x \ge y \ge z $ e risulta

$ \displaystyle \frac{x^3}{yz}+\frac{y^3}{zx}+\frac{z^3}{xy} \ge \frac{x^3}{xy}+\frac{y^3}{yz}+\frac{z^3}{zx}=\frac{x^2}{y}+\frac{y^2}{z}+\frac{z^2}{x} $

adesso considero le due terne $ (x^2,y^2,z^2) $ e $ (\frac{1}{y}, \frac{1}{z}, \frac{1}{x}) $ e risulta

$ \displaystyle \frac{x^2}{y}+\frac{y^2}{z}+\frac{z^2}{x} \ge \frac{x^2}{x}+\frac{y^2}{y}+\frac{z^2}{z}=x+y+z $

ed ho la tesi.

[ma_go]

sì, mi sembra tornare. però se volessi avere una soluzione "completa e pulita" dovresti aggiungere qualcosina.
prendo la tua dimostrazione e aggiungo dei pezzi (in grassetto) e sposto il WLOG all'inizio (l'alternativa è dire che lo riusi dopo).

Suppongo WLOG $ x \ge y \ge z $. Considero le due terne $ (x^3,y^3,z^3) $ e $ (\frac{1}{yz}, \frac{1}{zx}, \frac{1}{xy}) $, e risulta che $\frac1{yz}\ge\frac1{zx}\ge\frac1{xy}$, quindi per la disuguaglianza di riarrangiamento abbiamo
$ \displaystyle \frac{x^3}{yz}+\frac{y^3}{zx}+\frac{z^3}{xy} \ge \frac{x^3}{xy}+\frac{y^3}{yz}+\frac{z^3}{zx}=\frac{x^2}{y}+\frac{y^2}{z}+\frac{z^2}{x} $
adesso considero le due terne $ (x^2,y^2,z^2) $ e $ (\frac{1}{y}, \frac{1}{z}, \frac{1}{x}) $ e risulta che $\frac1{z}\ge\frac1{y}\ge\frac1{x}$, quindi per la disuguaglianza di riarrangiamento abbiamo
$ \displaystyle \frac{x^2}{y}+\frac{y^2}{z}+\frac{z^2}{x} \ge \frac{x^2}{x}+\frac{y^2}{y}+\frac{z^2}{z}=x+y+z $
ed ho la tesi.

chiaro che dal contesto (di questo thread) si capiva cosa stavi facendo, volevo solo precisare che la stesura di una soluzione da gara dev'essere più dettagliata e precisa. (e sì, lo so che sono pedante).

[Gi.]

Ma che pedante, anzi, ti ringrazio tantissimo, essendo impossibilitato a partecipare a qualsiasi tipo di stage per me questi aiuti sul forum sono fondamentali per imparare qualcosa e migliorarmi