O nierównościach $\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$
Dany $i,a_i,b_i\in\{1...n\},\space a_i\neq a_j,b_i\neq b_j,\forall i\neq j$ Udowodnij to $$\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$$ Ten problem został zaproponowany przez nowego współpracownika @ user3458994 i został zamknięty przez pięciu użytkowników. Uważam, że jest to trochę trudne (nie ma natychmiastowej odpowiedzi), ale jest wystarczająco dobrze postawione i rzeczywiście można to rozwiązać, udzielając poprawnej odpowiedzi.
Istnieje wiele możliwych kwot $\sum_{i=1}^n|a_i-b_i|$; w rzeczywistości są$n!$ możliwości (liczba permutacji zbioru $\{1,2,\cdots,n\}$). Minimum dla tych sum wynosi$0$ odpowiadające permutacji tożsamości $a_i\rightarrow b_i=a_i$w takim przypadku nierówność jest trywialnie weryfikowana. Ujawniamy, że jedna z tych sum ma wartość maksymalną$M$ dokładnie równe $\big\lfloor \frac{n^2}{2}\big\rfloor$. Uważałem, że żadna inna suma nie ma wartości większej niż$M$ w takim przypadku problem byłby fałszywy (czy się mylę?).
Odpowiedzi
Oto prawie natychmiastowa odpowiedź.
Rozszerzając każdy okres $ |a_i - b_i|$ do odpowiedniego $\pm (a_i - b_i)$, mamy to $$ \sum |a_i - b_i | = \sum c_i i, $$ gdzie $c_i \in \{-2, 0, 2 \}$ i $\sum c_i = 0 $.
Uwaga: jest to warunek konieczny, ale niewystarczający. W szczególności nie wszystkie kombinacje$c_i$są możliwe z wartości bezwzględnej, więc musielibyśmy następnie upewnić się, że można to spełnić. Jednak mamy „szczęście”, że to działa.
Gdy $n=2m$ jest parzysta, maksymalna $\sum c_i i $ jest $ -2\times 1 -2 \times 2 \ldots - 2 \times m + 2 \times (m+1) + 2\times (m+2) + \ldots + 2 \times (2m) = 2m^2$.
To jest zadowalające$a_i = i, b_i = n+1-i$, więc jest to maksimum $ \sum |a_i - b_i|$.
Gdy $n = 2m+1$ jest nieparzyste, maksymalna liczba $\sum c_i i $ jest $ -2\times 1 -2\times 2 \ldots - 2\times m + 2\times (m+2) + 2\times (m+3) + \ldots + 2 \times (2m+1) = 2m(m+1)$.
To jest zadowalające$a_i = i, b_i = n+1-i$, więc jest to maksimum $ \sum |a_i - b_i|$.
Uwaga: Warunkiem koniecznym i wystarczającym jest $ \sum_{i=1}^k c_{n+1-i} \geq 0$ dla wszystkich $ 1 \leq k \leq n$. Gdy jest to spełnione, istnieje całkiem naturalny sposób przypisywania wartości. (Pomyśl o tym.)
Odpowiedziałem już w tym poście. Wrzucę to ponownie tutaj. Jest to trochę podobne do nierówności związanej z przegrupowaniem: kiedy$\{a_i\}$ i $\{b_i=i\}$mają przeciwną kolejność, suma bezwzględnej różnicy osiąga maksimum (mogą istnieć inne przypadki, które również osiągną to maksimum). Reszta to proste obliczenia.
Lemat: Jeśli$x>y,z>w$ następnie $|x-w|+|y-z|\geqslant |x-z|+|y-w|.$
WLOG możemy założyć $y\geqslant w$. Następnie$x>w$.
$$|x-w|+|y-z|\geqslant |x-z|+|y-w| \iff x-w+|y-z| \geqslant |x-z|+y-w \\ \iff |x-y|+|y-z|\geqslant |x-z|$$
co wynika z nierówności trójkąta.
Załóż WLOG $b_i=i$. Wtedy z lematu suma bezwzględnych różnic uzyskuje swoją maksymalną wartość kiedy$a_i$ maleje, tj $$\sum_{i=1}^n|a_i-i| \leqslant \sum_{i=1}^n |n+1-2i|.$$
Jeśli $n=2m$, $$\sum_{i=1}^n |n+1-2i|=2(2m-1) + 2(2m-3)+\cdots + 2(1)=2m^2 = \lfloor \frac{n^2}{2} \rfloor.$$
Jeśli $n=2m+1$, $$\sum_{i=1}^n |n+1-2i|=2(2m) + 2(2m-2)+\cdots + 2(0)=2m(m+1) = \lfloor \frac{n^2}{2} \rfloor.\blacksquare$$
Dla każdej permutacji jest kilka $1 \le k \le n$ wartości $i$ gdzie
$$a_i - b_i \lt 0 \tag{1}\label{eq1A}$$
Tak więc pozostałe $n - k$ wartości $i$ będzie gdzie
$$a_i - b_i \ge 0 \tag{2}\label{eq2A}$$
Dla uproszczenia, jeśli to konieczne, dostosuj wartości $a_i$ i $b_i$ więc $k$ wartości, gdzie \ eqref {eq1A} hold to te, w których $1 \le i \le k$. To daje
$$\begin{equation}\begin{aligned} \sum_{i = 1}^{n}|a_i - b_i| & = \sum_{i = 1}^{k}|a_i - b_i| + \sum_{i = k + 1}^{n}|a_i - b_i| \\ & = \sum_{i = 1}^{k}(b_i - a_i) + \sum_{i = k + 1}^{n}(a_i - b_i) \\ & = 2\sum_{i = 1}^{k}(b_i - a_i) - \sum_{i = 1}^{k}(b_i - a_i) + \sum_{i = k + 1}^{n}(a_i - b_i) \\ & = 2\sum_{i = 1}^{k}(b_i - a_i) + \sum_{i = 1}^{k}(a_i - b_i) + \sum_{i = k + 1}^{n}(a_i - b_i) \\ & = 2\sum_{i = 1}^{k}(b_i - a_i) + \sum_{i = 1}^{n}a_i - \sum_{i = 1}^{n}b_i \\ & = 2\sum_{i = 1}^{k}(b_i - a_i) \end{aligned}\end{equation}\tag{3}\label{eq3A}$$
Ostatni wiersz pochodzi z $\sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n}b_i$ więc ostatni $2$warunki linii przed anulowaniem. W \ eqref {eq3A} maksymalna wartość pochodzi z$b_i$ bycie największym dozwolonym $k$ wartości, tj. $n - k + 1 \le b_i \le n$, i $a_i$ najmniejszy dozwolony $k$ wartości, tj. $1 \le a_i \le k$. A zatem,
$$\begin{equation}\begin{aligned} 2\sum_{i = 1}^{k}(b_i - a_i) & \le 2\left(\sum_{i = n - k + 1}^{n}i - \sum_{i = 1}^{k}i \right) \\ & = 2\left(\frac{k((n - k + 1) + n)}{2} - \frac{k(k + 1)}{2}\right) \\ & = k(n - k + 1 + n - k - 1) \\ & = 2k(n - k) \end{aligned}\end{equation}\tag{4}\label{eq4A}$$
Uwaga $f(k) = 2k(n - k)$ to wklęsła parabola o maks $k = \frac{n}{2}$. Nawet$n$, ta wartość $k$ jest liczbą całkowitą, która daje maksymalną wartość \ eqref {eq4A} as
$$\begin{equation}\begin{aligned} 2k(n - k) & \le 2\left(\frac{n}{2}\right)\left(n - \frac{n}{2}\right) \\ & = n\left(\frac{n}{2}\right) \\ & = \left\lfloor \frac{n^2}{2} \right\rfloor \end{aligned}\end{equation}\tag{5}\label{eq5A}$$
Na dziwne $n$, ta sama maksymalna wartość jest osiągana z $k = \frac{n - 1}{2}$ i $k = \frac{n + 1}{2}$. Używając pierwszej wartości, otrzymujemy to z \ eqref {eq4A}
$$\begin{equation}\begin{aligned} 2k(n - k) & \le 2\left(\frac{n - 1}{2}\right)\left(n - \frac{n - 1}{2}\right) \\ & = (n - 1)\left(\frac{n + 1}{2}\right) \\ & = \frac{n^2 - 1}{2} \\ & = \left\lfloor \frac{n^2}{2} \right\rfloor \end{aligned}\end{equation}\tag{6}\label{eq6A}$$
To pokazuje, że stwierdzona nierówność zawsze obowiązuje. Uwaga Piquito „s odpowiedź daje wyraźny przykład, w którym maksymalna możliwa wartość zostanie osiągnięta nawet$n$.