Disuguaglianza di riordinamento

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Gi.
Messaggi: 153
Iscritto il: 18 dic 2012, 16:45

Disuguaglianza di riordinamento

Messaggio da Gi. » 07 mar 2013, 10:07

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 :lol:

Avatar utente
Drago96
Messaggi: 1138
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Disuguaglianza di riordinamento

Messaggio da Drago96 » 07 mar 2013, 15:59

Innanzitutto, di solito si chiama riarrangiamento, però vabbè... :D
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 :)
Ultima modifica di Drago96 il 07 mar 2013, 17:01, modificato 1 volta in totale.
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Disuguaglianza di riordinamento

Messaggio da ndp15 » 07 mar 2013, 16:26

Drago96 ha scritto: che sommate danno la tesi
Che infatti è $ roba\ge 6 $ e non di $ 3/2 $ :wink:

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.
Messaggi: 153
Iscritto il: 18 dic 2012, 16:45

Re: Disuguaglianza di riordinamento

Messaggio da Gi. » 07 mar 2013, 16:54

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 :mrgreen:

Avatar utente
Drago96
Messaggi: 1138
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Disuguaglianza di riordinamento

Messaggio da Drago96 » 07 mar 2013, 16:56

Oddio, epic fail! :oops:
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 :D
$$\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
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Gi.
Messaggi: 153
Iscritto il: 18 dic 2012, 16:45

Re: Disuguaglianza di riordinamento

Messaggio da Gi. » 08 mar 2013, 09:45

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
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: Disuguaglianza di riordinamento

Messaggio da ma_go » 08 mar 2013, 14:15

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.
Messaggi: 153
Iscritto il: 18 dic 2012, 16:45

Re: Disuguaglianza di riordinamento

Messaggio da Gi. » 08 mar 2013, 14:52

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
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: Disuguaglianza di riordinamento

Messaggio da ma_go » 08 mar 2013, 16:17

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).
soluzione da 7 punti ha scritto: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.
Messaggi: 153
Iscritto il: 18 dic 2012, 16:45

Re: Disuguaglianza di riordinamento

Messaggio da Gi. » 08 mar 2013, 16:47

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 :)

Rispondi