Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ the product ordering on $\mathbb{R}_+^m$. That is, $\leq_m$ is the partial ordering on $\mathbb{R}_+^m$ defined for all $V_1, V_2 \in \mathbb{R}_+^m$ as $V_1 \leq_m V_2$ if and only if for every $i \in \{1, \dots, m\}$, $V_1(i) \leq V_2(i)$, where $\leq$ is the standard ordering over real numbers. Lastly, given a vector $V = (V(1), \dots, V(m)) \in \mathbb{R}^m$ we denote $d(V)$ the unbalance degree of $V$ defined as $d(V) = \sum_{i=1}^m{|V(i) - \mathrm{avg}(V)|}$ where $\mathrm{avg}(V) = \frac1m \sum_{i=1}^m{V(i)}$. Intuitively, $d(V)$ represents the Manhattan distance between $V$ and the average line $\{(x_1, \dots, x_m) \in \mathbb{R}_+^m \mid x_1 = \dots = x_m\}$.My problem is as follows: given two vectors $V, V' \in \mathbb{R}^m_+$ such that $V \leq_m V'$, I would like to characterize a vector from $\mathrm{argmax}_{V \leq W \leq V'}\,d(W)$. Intuititvely, such a vector is one of the most unbalanced ones between $V$ and $V'$. For instance, if $V = (0, 0, 0, 0, 0)$ and $V' = (4, 10, 2, 10, 4)$, such a vector is $W = (0, 10, 0, 10, 0)$, with $d(W) = 24$.My conjecture is as follows. Let $avg(V, V') = \frac{1}{2m}{\sum_{i=1}^m{V(i) + V'(i)}}$. We build the vector $W$ for every $k \in \{1, \dots, m\}$ as follows:$$W(k) = \left\lbrace\begin{array}{ll}V(k) & \mbox{ if } (\tfrac12\big(V(k) + V'(k)\big) < \mathrm{avg}(V, V')),\\V'(k) & \mbox{ if } (\tfrac12\big(V(k) + V'(k)\big) > \mathrm{avg}(V, V')).\\\end{array}\right.$$We define the remaining components of $W$ (i.e., the $W(k)$ such that $\tfrac12\big(V(k) + V'(k)\big) = \mathrm{avg}(V, V'))$) as follows. Let $K = \{k \in \{1, \dots, m\} \mid \tfrac12\big(V(k) + V'(k)\big) = \mathrm{avg}(V, V'))\}$ and denote the elements of $K$ as $\{k_1, \dots, k_n\}$. Then $\forall k_i \in K$,$$W(k_i) = \left\lbrace\begin{array}{ll}V(k_i) & \mbox{ if $i$ is an odd number},\\V'(k_i) & \mbox{otherwise.}\end{array}\right.$$So far, I could just prove that there is a vector $W \in \mathrm{argmax}_{V \leq W \leq V'}\,d(W)$ such that for every $k \in \{1, \dots, m\}$, $W(k) \in \{V(k), V'(k)\}$. But this leaves a search space of size $2^m$, and does not provide me a polytime algorithm to solve the problem. Proving the conjecture above would do so.
What is the most unbalanced vector between two given vectors of numbers?
co.combinatorics;optimization;polynomial time