Permutazioni

[giannirecanati]

Sia \(\displaystyle \sigma \) una permutazione dell'insieme dei numeri \(\displaystyle 1,2,.... n \)(cioè un'applicazione biunivoca nell'insieme in sé). Poniamo \(\displaystyle N(\sigma)=\sum_{i=1}^{n} \left| \sigma(i)-i \right| \). Si determini il massimo valore che può assumere \(\displaystyle N(\sigma) \).

Problema delle olimpiadi, ma non so proprio come approcciarlo.

[perplesso1]

Non è una soluzione, è solo un'idea

Ho cercato di costruire una permutazione di $ S_n $ che in qualche modo "massimizzasse" le differenze, in questo modo:

Se n è pari allora considero la permutazione $ \delta = (1n)(2(n-1))(3(n-2))...((n/2)(n/2 + 1)) $ in questo caso si ha $ N(\delta) = 2[ (n-1)+(n-3)+(n-5)+...+(n-(n-1)) ]=2[{n^2}/2-(n/2)^2] = {n^2}/2 $

Se n è dispari invece $ \delta = (1n)(2(n-1))(3(n-2))...(({n-1}/2)({n+1}/2)) $ e con analogo procedimento $ N(\delta) = {n^2-1}/2 $

Se questo è giusto significa solo che $ maxN(\delta) >= {n^2}/2 $

[DMNQ]

"giannirecanati":Sia \(\displaystyle \sigma \) una permutazione dell'insieme dei numeri \(\displaystyle 1,2,.... n \)(cioè un'applicazione biunivoca nell'insieme in sé). Poniamo \(\displaystyle N(\sigma)=\sum_{i=1}^{n} \left| \sigma(i)-i \right| \). Si determini il massimo valore che può assumere \(\displaystyle N(\sigma) \).

Problema delle olimpiadi, ma non so proprio come approcciarlo.

Ciao .
Qualche idee ... nondimeno a verificare !

Per $ n in NN , n>=1 $ , pongo $ M_n= \frac{n^2}{2} $ se n è pari e $ M_n= \frac{n^2-1}{2} $ se n è dispari .

1/

Esiste $\sigma in Perm(n)$ tale che $ N(\sigma) = M_n $ dunque $ Max{ N(\sigma) | \sigma in Perm(n)} >=M_n $ .
( già detto da perplesso )

2/

Qualsiasi $ \sigma in Perm(n) $ posso trovare $\sigma_+ in Perm(n) $ tale che $ \sigma_+{1 ; n} = { 1 ; n } $
e $ N(\sigma ) <= N(\sigma_+) $.
Per esempio , con $ n=9 $ se $ \sigma = ((1,2,3,4,5,6,7,8,9),(5,3,7,9,2,8,1,4,6)) $
prenderei $ \sigma_+ = ((1,2,3,4,5,6,7,8,9),(9,3,7,6,2,8,5,4,1)) $

3/

Per ogni n , $ n >=3 $ , la disuguaglianza $ M_(n-2)+ 2(n-1) <= M_n $ è sempre vera .

4/

Perfino , propongo di dimostrare la disuguaglianza $ N(\sigma) <= M_n $ qualsiasi $ \sigma in Perm(n) $
per induzione sull'intero $ n $ .
La proprietà è giusta per $ n = 0 , 1 , 2 $
Suppongo che la proprietà sia giusta per tutti interi $ < n $ .
Prendo $ \sigma in Perm(n) $ .
Con $ \sigma_+ $ , ho $ N(\sigma_+ ) = \sum_{i!=1,n } |\sigma_+(i)- i | + 2(n-1) <= M_(n-2) + 2(n-1) $
dunque $ N(\sigma_+ ) <= M_n $ e cosi $ N(\sigma ) <= M_n $ . Ottengo la proprietà per $ n $


Conclusione : $ Max{ N(\sigma) | \sigma in Perm(n)} =M_n $

[giannirecanati]

Grazie mille! Adesso ho capito!