A positive integer $n (\ge 4)$ is given. Let $a_1, a_2, \cdots ,a_n$ be $n$ pairwise distinct positive integers where $a_i \le n$ for all $1 \le i \le n$. Determine the maximum value of $$\sum_{i=1}^{n}{|a_i - a_{i+1} + a_{i+2} - a_{i+3}|}$$where all indices are modulo $n$
Problem
Source: 2024 FKMO P5
Tags: inequalities
24.03.2024 09:57
The answer is $\boxed{n^2}$ if $n$ is even, $\boxed{n^2 - 5}$ otherwise. To prove the upper bound, we will perform "double-counting" in the following set: $$S = \left\{(x, i) \mid x \in \left[\min(a_i, a_{i+1}), \max(a_i, a_{i+1})\right), x = 1, 2, \dots, n \right\}$$Obviously, $|S| = \sum_{i = 1}^{n}|a_i - a_{i+1}|$. For each $x$, the condition $x \geq a_i \lor x \geq a_{i + 1}$ and $x < a_i \lor x < a_{i+1}$ must hold. There are at most $2\min(x, n - x)$ such $i$. Case 1: $n$ is even. We have $\sum_{i = 1}^{n}|a_i - a_{i+1}| \leq \sum_{x = 1}^{n}2\min(x, n - x) = \frac{n^2}{2}$. Therefore, \begin{align*} \sum_{i=1}^{n}{|a_i-a_{i+1}+a_{i+2}-a_{i+3}|} &\leq \sum_{i=1}^{n}{\left(|a_i-a_{i+1}|+|a_{i+2}-a_{i+3}|\right)} \\ &= 2\sum_{i=1}^{n}|a_i-a_{i+1}| = n^2. \end{align*} Let $n = 2k$, equality holds if $\mathcal{A} = (1, k + 1, 2, k + 2, \dots, k, 2k)$. Case 2: $n$ is odd. If $\textrm{sgn}(a_i - a_{i+1}) = \textrm{sgn}(a_{i + 2} - a_{i + 3})$ for all $i$, then we have $\textrm{sgn}(a_1 - a_2) = \textrm{sgn}(a_2 - a_3) = \dots = \textrm{sgn}(a_n - a_1)$ which is cleary a contradiction. So, there exists $k$ such that $\textrm{sgn}(a_k - a_{k+1}) \neq \textrm{sgn}(a_{k+2} - a_{k+3})$. WLOG let $a_k > a_{k + 1}, a_{k + 2} < a_{k + 3}$. We have two cases, either $a_{k+1} < a_{k+2}$ or $a_{k+1} > a_{k+2}$. WLOG let $a_{k + 1} < a_{k+2}$, since we can reverse the permutation. Remark $a_k > a_{k+1} < a_{k+2} < a_{k+3}$. Let's go back to the beginning (double counting), if $a_{k+1} \leq x < a_{k+2}$ then $(x, k + 2) \notin S$, so there at most $2\min(x, n - x) - 1$ such $i$. Therefore, $\sum_{i = 1}^{n}|a_i - a_{i+1}| \leq \sum_{x = 1}^{n}2\min(x, n - x) - (a_{k+2} - a_{k+1}) = \frac{n^2-1}{2} + a_{k+1} - a_{k+2}$ and hence \begin{align*} \sum_{i=1}^{n}{|a_i-a_{i+1}+a_{i+2}-a_{i+3}|} &\leq \sum_{i\neq k}{\left(|a_i-a_{i+1}|+|a_{i+2}-a_{i+3}|\right)} + |a_k-a_{k+1}+a_{k+2}-a_{k+3}| \\ &= 2\sum_{i=1}^{n}|a_i-a_{i+1}| - (a_k - a_{k+1} + a_{k+3} - a_{k+2}) + |a_k-a_{k+1}+a_{k+2}-a_{k+3}| \\ &= n^2 - 1 - a_k + 3a_{k + 1} - a_{k+2} - a_{k+3} + |a_k-a_{k+1}+a_{k+2}-a_{k+3}|.\end{align*} Notice that the value of $- a_k + 3a_{k + 1} - a_{k+2} - a_{k+3} + |a_k-a_{k+1}+a_{k+2}-a_{k+3}|$ is either $2a_{k+1}-2a_{k+3}$ or $-2a_k+4a_{k+1}-2a_{k+2}$. Both are less than or equal to $-4$, so $$\sum_{i=1}^{n}{|a_i-a_{i+1}+a_{i+2}-a_{i+3}|} \leq n^2 - 5$$ Let $n = 2k + 1$, equality holds if $\mathcal{A} = (\textcolor{red}{k, k + 1, k + 2}, 1, k + 3, 2, k + 4, \dots, k - 1, 2k + 1)$. $\ \blacksquare$ Remark. Here, $\textrm{sgn}(P)$ is sign function.
24.10.2024 12:16
I think the first inequality in the odd case is wrong, consider n=5 and (2,3,4,1,5).