):siano date due n-uple di reali $x_1\ge x_2\ge x_3...\ge x_n$ e $y_1\ge y_2\ge y_3...\ge y_n$. Sia inoltre $k(1),k(2),k(3)...k(n)$ una permutazione di $1,2,3...n$. Dimostrare che
$\displaystyle\sum_{i=1}^n |x_i-y_i|\le \sum_{i=1}^n |x_i-y_{k(i)}|$
sulla scia del riarrangiamento (own)
sulla scia del riarrangiamento (own)
non so se è un fatto noto o meno, però sono soddisfatto di averlo trovato quindi lo posto qui (non è affatto impossibile se conoscete la dimostrazione del riarrangiamento quindi provateci tutti! ):
siano date due n-uple di reali $x_1\ge x_2\ge x_3...\ge x_n$ e $y_1\ge y_2\ge y_3...\ge y_n$. Sia inoltre $k(1),k(2),k(3)...k(n)$ una permutazione di $1,2,3...n$. Dimostrare che
$\displaystyle\sum_{i=1}^n |x_i-y_i|\le \sum_{i=1}^n |x_i-y_{k(i)}|$
):siano date due n-uple di reali $x_1\ge x_2\ge x_3...\ge x_n$ e $y_1\ge y_2\ge y_3...\ge y_n$. Sia inoltre $k(1),k(2),k(3)...k(n)$ una permutazione di $1,2,3...n$. Dimostrare che
$\displaystyle\sum_{i=1}^n |x_i-y_i|\le \sum_{i=1}^n |x_i-y_{k(i)}|$
-
paga92aren
- Messaggi: 358
- Iscritto il: 31 lug 2010, 10:35
Re: sulla scia del riarrangiamento (own)
Risolvo per induzione su $n$
Passo base $n=1$ banale.
Passo induttivo: wlog $x_1\geq y_1$ e chiamo $S(n)$ la sommatoria di destra .
1) dimostro che $|x_1-y_1|+|x_j-y_i|\leq |x_1-y_i|+|x_j-y_1|$
- se $x_j\geq y_1 (\geq y_i)$ allora l'equazione diventa $x_1-y_1+x_j-y_i\leq x_1-y_i+x_j-y_1$ che è sempre vera
- se $y_1\geq x_j\geq y_i$ allora l'equazione diventa $x_1-y_1+x_j-y_i\leq x_1-y_i-x_j+y_1$ da cui $x_j\leq y_1$ che è vera
- se $x_j\leq y_i(\leq y_1)$ allora l'equazione diventa $x_1-y_1-x_j+y_i\leq x_1-y_i-x_j+y_1$ da cui $y_i\leq y_1$ che è vera
2) Se $\sigma (1)=1$ allora semplifico il primo termine dell'equazione iniziale e ottengo $\sum_2^n |x_i-y-i|\leq S(n-1)$ che è vera per l'ipotesi del passo induttivo
Altrimenti con il passo 1 scambio due valori delle $y$ ($y_1$ e la $y$ in corrispondenza di $x_1$) con il passo 1 e ottengo RHS$\geq |x_1-y_1|+S(n-1)\geq$LHS.
Che brutta soluzione...
Passo base $n=1$ banale.
Passo induttivo: wlog $x_1\geq y_1$ e chiamo $S(n)$ la sommatoria di destra .
1) dimostro che $|x_1-y_1|+|x_j-y_i|\leq |x_1-y_i|+|x_j-y_1|$
- se $x_j\geq y_1 (\geq y_i)$ allora l'equazione diventa $x_1-y_1+x_j-y_i\leq x_1-y_i+x_j-y_1$ che è sempre vera
- se $y_1\geq x_j\geq y_i$ allora l'equazione diventa $x_1-y_1+x_j-y_i\leq x_1-y_i-x_j+y_1$ da cui $x_j\leq y_1$ che è vera
- se $x_j\leq y_i(\leq y_1)$ allora l'equazione diventa $x_1-y_1-x_j+y_i\leq x_1-y_i-x_j+y_1$ da cui $y_i\leq y_1$ che è vera
2) Se $\sigma (1)=1$ allora semplifico il primo termine dell'equazione iniziale e ottengo $\sum_2^n |x_i-y-i|\leq S(n-1)$ che è vera per l'ipotesi del passo induttivo
Altrimenti con il passo 1 scambio due valori delle $y$ ($y_1$ e la $y$ in corrispondenza di $x_1$) con il passo 1 e ottengo RHS$\geq |x_1-y_1|+S(n-1)\geq$LHS.
Che brutta soluzione...