Question

Aceste exercițiu. Vă mulțumesc pentru ajutor!D2 este exercițiul.​

Answer 1

Răspuns:

a) Notăm cu $S_{\sigma}$ suma din enunț.

Fie $\sigma$ permutarea pentru care se obține suma maximă.

Fie $\sigma_1=\sigma\cdot (i,j), \ i < j$, unde $(i,j)$ este transpoziție. Atunci

$S_{\sigma_1}\le S_{\sigma}$. Rezultă

$\displaystyle\sum_{k=1, \ k\ne i,j}^n\dfrac{1}{a_ka_{\sigma(k)}}+\dfrac{1}{a_ia_{\sigma(j)}}+\dfrac{1}{a_ja_{\sigma(i)}}\le \displaystyle\sum_{k=1, \ k\ne i,j}^n\dfrac{1}{a_ka_{\sigma(k)}}+\dfrac{1}{a_ia_{\sigma(i)}}+\dfrac{1}{a_ja_{\sigma(j)}}$

Rezultă

$\dfrac{1}{a_ia_{\sigma(j)}}+\dfrac{1}{a_ja_{\sigma(i)}}\le \dfrac{1}{a_ia_{\sigma(i)}}+\dfrac{1}{a_ja_{\sigma(j)}}$

Din calcule rezultă

$(a_i-a_j)(a_{\sigma(j)}-a_{\sigma(i)})\le 0$

Cum $a_i < a_j\Rightarrow a_{\sigma(i)} < a_{\sigma(j)}\Rightarrow \sigma(i) < \sigma(j)$

Deci $\sigma$ nu are nici o inversiune, deci este permutarea identică.

Pentru suma minimă se obține permutarea cu numărul maxim de inversiuni

$\sigma=\begin{pmatrix}1 & 2 & \ldots & n\\n & n-1 & \ldots & 1\end{pmatrix}$

Analog se face la b)

Explicație pas cu pas: