불평등에 관하여 $\sum_{i=1}^n|a_i-b_i|\le\big\lfloor \frac{n^2}{2}\big\rfloor$
주어진 $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$이 경우 불평등은 간단하게 확인됩니다. 이 합계 중 하나를 최대 값으로 노출합니다.$M$ 정확히 같음 $\big\lfloor \frac{n^2}{2}\big\rfloor$. 나는 다른 합이$M$ 어떤 경우에는 문제가 거짓입니다 (내가 틀렸습니까?).
답변
여기에 거의 즉각적인 답변이 있습니다.
각 용어를 확장하여 $ |a_i - b_i|$ 해당하는 $\pm (a_i - b_i)$, 우리는 $$ \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$. 만족 스러우면 값을 할당하는 매우 자연스러운 방법이 있습니다. (생각해보십시오.)
나는 이미 그 게시물에서 답변을주었습니다. 여기에 다시 게시하겠습니다. 재배치 불평등과 다소 유사합니다.$\{a_i\}$ 과 $\{b_i=i\}$순서가 반대이면 절대 차이의 합이 최대 값에 도달합니다 (이 최대 값에 도달하는 다른 경우도있을 수 있음). 나머지는 간단한 계산입니다.
정리 : If$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$$
모든 순열에 대해 몇 가지 $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}$$
이것은 명시된 불평등이 항상 유지된다는 것을 보여줍니다. 참고 Piquito 의 답변 은 가능한 최대 값에 도달하는 명시적인 예를 제공합니다.$n$.