असमानता पर $\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 द्वारा प्रस्तावित की गई थी और इसे पांच उपयोगकर्ताओं द्वारा बंद कर दिया गया था। मुझे यह कुछ चुनौतीपूर्ण लगता है (इसका तत्काल उत्तर नहीं है), लेकिन यह पर्याप्त रूप से अच्छी तरह से सामने आया है और वास्तव में, इसका सही उत्तर देकर हल किया जा सकता है।
कई संभावित रकम हैं $\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\}$विपरीत क्रम होने पर, पूर्ण अंतर का योग अधिकतम तक पहुँच जाता है (ऐसे अन्य मामले भी हो सकते हैं जो इस अधिकतम तक पहुँचते हैं)। बाकी सिर्फ आसान गणना है।
लेम्मा: यदि$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|$$
जो त्रिभुज असमानता से होता है।
डब्ल्यूएलओजी मान लेते हैं $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$।