不平等について $\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$

Question

与えられた $i,a_i,b_i\in\{1...n\},\space a_i\neq a_j,b_i\neq b_j,\forall i\neq j$ 証明してください $$\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$$ この問題は、新しい寄稿者@ user3458994によって提案され、5人のユーザーによって解決されました。やや難しいと思いますが（すぐには答えられません）、十分に適切な設定であり、実際、正しく答えることで解決できます。

多くの可能な合計があります $\sum_{i=1}^n|a_i-b_i|$; 実際には$n!$ 可能性（セットの順列の数 $\{1,2,\cdots,n\}$）。これらの合計の最小値は$0$ 単位順列に対応 $a_i\rightarrow b_i=a_i$その場合、不等式は簡単に検証されます。最大値を持つこれらの合計の1つを公開します$M$ 正確に等しい $\big\lfloor \frac{n^2}{2}\big\rfloor$。他の合計がより大きい値を持っているとは思わなかった$M$ その場合、問題は誤りになります（私は間違っていますか？）。

Answer 1

これがほぼ即時の答えです。

の各用語を拡張することによって $ |a_i - b_i|$ 対応するに $\pm (a_i - b_i)$、私たちはそれをge $$ \sum |a_i - b_i | = \sum c_i i, $$ どこ $c_i \in \{-2, 0, 2 \}$ そして $\sum c_i = 0 $。

注：これは必要条件ですが、十分条件ではありません。特に、すべての組み合わせが$c_i$絶対値から可能であるため、後でこれが満たされることを確認する必要があります。しかし、私たちはこれがうまくいくほど「幸運」です。

いつ $n=2m$ でさえ、最大 $\sum c_i i $ です $ -2\times 1 -2 \times 2 \ldots - 2 \times m + 2 \times (m+1) + 2\times (m+2) + \ldots + 2 \times (2m) = 2m^2$。
これは満足しています$a_i = i, b_i = n+1-i$、だからそれは最大です $ \sum |a_i - b_i|$。

いつ $n = 2m+1$ 奇数、最大値 $\sum c_i i $ です $ -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)$。
これは満足しています$a_i = i, b_i = n+1-i$、だからそれは最大です $ \sum |a_i - b_i|$。

注：必要十分条件は $ \sum_{i=1}^k c_{n+1-i} \geq 0$ すべてのために $ 1 \leq k \leq n$。それが満たされると、値を割り当てる非常に自然な方法があります。（考えてみてください。）

Answer 2

私はすでにその投稿で答えを出しました。ここにまた投稿します。これは、再配置の不等式にいくぶん似ています。$\{a_i\}$ そして $\{b_i=i\}$順序が逆の場合、絶対差の合計が最大になります（この最大値に達する他の場合もあります）。残りは簡単な計算です。

---

補題：もし$x>y,z>w$ その後 $|x-w|+|y-z|\geqslant |x-z|+|y-w|.$

想定できるWLOG $y\geqslant w$。次に$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|$$

これは三角不等式から生じます。

WLOGは仮定します $b_i=i$。次に、見出語から絶対差の合計が最大値を取得します。$a_i$ 減少している、すなわち $$\sum_{i=1}^n|a_i-i| \leqslant \sum_{i=1}^n |n+1-2i|.$$

場合 $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.$$

場合 $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$$

Answer 3

順列には、いくつかあります $1 \le k \le n$ の値 $i$ どこ

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

したがって、残りの $n - k$ の値 $i$ どこになります

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

簡単にするために、必要に応じて、の値を調整します $a_i$ そして $b_i$ だから $k$ \ eqref {eq1A}が成り立つ値は、 $1 \le i \le k$。これにより、

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

最後の行はから来ています $\sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n}b_i$ だから最後 $2$キャンセル前の行の条件。\ eqref {eq3A}では、最大値は$b_i$ 許可されている最大のものであること $k$ 値、すなわち、 $n - k + 1 \le b_i \le n$、および $a_i$ 許可される最小であること $k$ 値、すなわち、 $1 \le a_i \le k$。したがって、

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

注意 $f(k) = 2k(n - k)$ で最大値を持つ凹型のダウン放物線です $k = \frac{n}{2}$。でも$n$、この値の $k$ は整数であり、\ eqref {eq4A}の最大値を次のように与えます。

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

奇数の場合 $n$、同じ最大値が $k = \frac{n - 1}{2}$ そして $k = \frac{n + 1}{2}$。最初の値を使用して、\ 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}$$

これは、述べられた不等式が常に成り立つことを示しています。注意https://math.stackexchange.com/users/219998/piquitoの https://math.stackexchange.com/a/3924380/602049 偶数に対して可能な最大値に達する明示的な例を示します $n$。