Komentarz

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 /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz