XXXV OM - III - Zadanie 2

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

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

$ a_{j,i} = \begin{cases} 1 &\text{ dla }j=i \\ 0 &\text{ dla }j\neq i \end{cases} $

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

$ a_{j,i} = -\frac{1}{n}. $

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

$ \sum_{j=1}^n \left| \sum_{k=1}^n a_{j, p(k)}\right| \geq \frac{n}{2}. $

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

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