Über die Ungleichheit $\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$

Nov 26 2020

Gegeben $i,a_i,b_i\in\{1...n\},\space a_i\neq a_j,b_i\neq b_j,\forall i\neq j$ Beweise das $$\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$$ Dieses Problem wurde vom neuen Mitwirkenden @ user3458994 vorgeschlagen und von fünf Benutzern geschlossen. Ich finde es etwas herausfordernd (es gibt keine unmittelbare Antwort), aber es ist ausreichend gut gestellt und kann tatsächlich durch richtige Antwort gelöst werden.

Es gibt viele mögliche Summen $\sum_{i=1}^n|a_i-b_i|$;; in der Tat gibt es$n!$ Möglichkeiten (Anzahl der Permutationen der Menge $\{1,2,\cdots,n\}$). Das Minimum für diese Beträge ist$0$ entsprechend der Identitätspermutation $a_i\rightarrow b_i=a_i$In diesem Fall wird die Ungleichung trivial überprüft. Wir legen eine dieser Summen mit einem Maximalwert offen$M$ genau gleich $\big\lfloor \frac{n^2}{2}\big\rfloor$. Ich glaubte, keine andere Summe hat einen Wert größer als$M$ In diesem Fall wäre das Problem falsch (irre ich mich?).

Antworten

1 CalvinLin Nov 27 2020 at 02:03

Hier ist eine fast sofortige Antwort.

Durch die Erweiterung jedes Begriffs von $ |a_i - b_i|$ in die entsprechende $\pm (a_i - b_i)$, wir ge das $$ \sum |a_i - b_i | = \sum c_i i, $$ wo $c_i \in \{-2, 0, 2 \}$ und $\sum c_i = 0 $.

Hinweis: Dies ist eine notwendige, aber nicht ausreichende Bedingung. Insbesondere nicht alle Kombinationen von$c_i$sind vom absoluten Wert möglich, daher müssten wir später sicherstellen, dass dies erfüllt werden kann. Wir haben jedoch das "Glück", dass dies für uns funktioniert.

Wann $n=2m$ ist gerade, das Maximum von $\sum c_i i $ ist $ -2\times 1 -2 \times 2 \ldots - 2 \times m + 2 \times (m+1) + 2\times (m+2) + \ldots + 2 \times (2m) = 2m^2$.
Damit ist zufrieden$a_i = i, b_i = n+1-i$, also ist es das Maximum von $ \sum |a_i - b_i|$.

Wann $n = 2m+1$ ist ungerade, das Maximum von $\sum c_i i $ ist $ -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)$.
Damit ist zufrieden$a_i = i, b_i = n+1-i$, also ist es das Maximum von $ \sum |a_i - b_i|$.

Hinweis: Die notwendige und ausreichende Bedingung ist $ \sum_{i=1}^k c_{n+1-i} \geq 0$ für alle $ 1 \leq k \leq n$. Sobald dies erfüllt ist, gibt es eine ziemlich natürliche Möglichkeit, die Werte zuzuweisen. (Denken Sie darüber nach.)

1 NeatMath Nov 27 2020 at 05:05

Ich habe in diesem Beitrag bereits eine Antwort gegeben. Ich werde es hier wieder posten. Es ist der Ungleichung der Umlagerung etwas ähnlich: Wann$\{a_i\}$ und $\{b_i=i\}$Bei entgegengesetzter Reihenfolge erreicht die Summe der absoluten Differenz das Maximum (es kann auch andere Fälle geben, die dieses Maximum erreichen). Der Rest ist nur eine einfache Berechnung.


Lemma: Wenn$x>y,z>w$ dann $|x-w|+|y-z|\geqslant |x-z|+|y-w|.$

WLOG können wir annehmen $y\geqslant w$. Dann$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|$$

was aus der Dreiecksungleichung folgt.

WLOG annehmen $b_i=i$. Dann erhält aus dem Lemma die Summe der absoluten Differenzen ihren Maximalwert, wenn$a_i$ nimmt ab, dh $$\sum_{i=1}^n|a_i-i| \leqslant \sum_{i=1}^n |n+1-2i|.$$

Wenn $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.$$

Wenn $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$$

JohnOmielan Nov 27 2020 at 02:08

Für jede Permutation gibt es einige $1 \le k \le n$ Werte von $i$ wo

$$a_i - b_i \lt 0 \tag{1}\label{eq1A}$$

Also die restlichen $n - k$ Werte von $i$ wird wo sein

$$a_i - b_i \ge 0 \tag{2}\label{eq2A}$$

Passen Sie zur Vereinfachung bei Bedarf die Werte von an $a_i$ und $b_i$ so die $k$ Werte, bei denen \ eqref {eq1A} gilt, sind diejenigen, bei denen $1 \le i \le k$. Dies gibt dann

$$\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}$$

Die letzte Zeile kommt von $\sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n}b_i$ also der letzte $2$Bedingungen der Linie vor dem Abbruch. In \ eqref {eq3A} kommt der Maximalwert von der$b_i$ das größte erlaubt sein $k$ Werte, dh $n - k + 1 \le b_i \le n$, und $a_i$ das kleinste erlaubt sein $k$ Werte, dh $1 \le a_i \le k$. So,

$$\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}$$

Hinweis $f(k) = 2k(n - k)$ ist eine konkave Daunenparabel mit einem Maximum bei $k = \frac{n}{2}$. Für gerade$n$, dieser Wert von $k$ ist eine Ganzzahl, die einen Maximalwert von \ eqref {eq4A} as ergibt

$$\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}$$

Für ungerade $n$wird der gleiche Maximalwert erreicht mit $k = \frac{n - 1}{2}$ und $k = \frac{n + 1}{2}$. Mit dem ersten Wert erhalten wir aus \ eqref {eq4A} das

$$\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}$$

Dies zeigt, dass die angegebene Ungleichung immer gilt. Hinweis Die Antwort von Piquito gibt ein explizites Beispiel, bei dem der maximal mögliche Wert für gerade erreicht wird$n$.