XXXV OM - III - Zadanie 2

Dla ustalonej liczby naturalnej $ n $ oraz każdego $ i = 1, 2, \ldots, n $, $ j = 1, 2, \ldots $ określamy

\[<br />
a_{j,i} = \begin{cases}<br />
1 &\text{ dla }j=i \\<br />
0 &\text{ dla }j\neq i<br />
\end{cases}<br />
\]

natomiast dla $ i = n + 1,\ldots, 2n $ $ j = 1,2,\ldots, n $

\[<br />
a_{j,i} = -\frac{1}{n}.<br />
\]

Udowodnić, że dla każdej permutacji $ p $ zbioru $ \{1, 2,\ldots, 2n\} $ spełniona jest nierówność

\[<br />
\sum_{j=1}^n \left| \sum_{k=1}^n a_{j, p(k)}\right| \geq \frac{n}{2}.<br />
\]

Rozwiązanie

Jeśli permutacja $ p $ liczbom $ 1,2,\ldots,n $ przyporządkowuje $ s $ wartości nie
większych od $ n $ oraz $ n-s $ wartości większych od $ n $, to suma $ \displaystyle \sum_{k-1}^n a_{j,p(k)} $ równa jest $ 1+(n - s) \cdot \frac{-1}{n} = \frac{s}{n} $ albo $ (n-s) \cdot \frac{-1}{n} $ w zależności od tego, czy istnieje $ k \leq \{1,2, \ldots,n \} $, dla którego $ j= p(k) $, czy też nie. Dla dokładnie $ s $ wartości $ j $ takie $ k $ istnieje, dla $ n-s $ wartości nie istnieje. Wobec tego

\[<br />
\begin{split}<br />
\sum_{j=1}^n \left| \sum_{k-1}^n a_{j,p(k)} \right| =<br />
s \cdot \left| \frac{s}{n} \right| +<br />
(n-s) \cdot \left| (n-s) \frac{-1}{n} \right|=\\<br />
\frac{s^2}{n} + \frac{(n-s)^2}{n} = \frac{(2s-n)^2+n^2}{2n} \geq \frac{n^2}{2n} = \frac{n}{2}.<br />
\end{split}<br />
\]

Komentarze

Dodaj nową odpowiedź