The problem has $n$ spears and $n$ soldiers. Spears and soldiers have heights. We want to assign spears to soldiers such that the total height difference of spears and their assigned soldiers is minimum. More precisely, we want to minimize $\sum_{1 \leq i \leq n} |a_{i} - b_{i}|$ where spear $b_{i}$ is assigned to soldier $a_{i}$. A friend of mine proposed the following greedy lemma:
Lemma: There exists an optimal solution where a spear with a minimal height $b_{i} = \min_{1 \leq j \leq n}{ \{ b_{j} \}}$ is assigned to a soldier with a minimal height $a_{j} = \min_{1 \leq j \leq n}\{ a_{j}\}$.
It seems to be the case that for many examples of this problem this lemma holds. However, my friend and I could not prove why. My current knowledge is as follows.
We have the property $\forall_{1 \leq i \leq n}[a_{i} \leq a_{i-1} \land b_{i} \leq b_{i-1}]$ holding in an optimal solution, because the lemma idea is to basically sort the set of spears and soldiers and assign them in parallel in increasing order (i.e. $b_{1}$ to $a_{1}$, $b_{2}$ to $a_{2}$, etc.).
My proof idea is to assume that a solution for this problem does not match spears to soldiers as the lemma describes, but in another way. Then, in such a solution, spear $b_{1}$ would be assigned to soldier $a_{j}: j > 1$ and some other spear $b_{j}$ would be assigned to soldier $a_{1}$. Then, to prove the lemma, I need to prove that $|b_{1} - a_{1}| + |b_{j} - a_{j}| \geq |b_{1} - a_{j}| + |b_{j} - a_{1}|$ holds, i.e., the new sum is at most the old sum. However I am not sure if this inequality can be proven. I think it sometimes does not hold.
Your friend is right, and your idea how to prove it is on the right track. There are two problems with your inequality, though: It’s the wrong way around (the left-hand side is the new sum, and it’s supposed to be at most, i.e. less than or equal to, the old sum, which is the right-hand side), and you can’t assume that $a_j$ and $b_j$ have the same index (at least if what you mean by that is what you wrote in the preceding paragraph, that they have the same rank in order of increasing height), but that doesn’t matter; I’ll just denote them by $a$ and $b$ to simplify the notation. So what we want to prove is
$$ |b_1-a_1|+|b-a|\le|b_1-a|+|b-a_1|\;. $$
Without loss of generality, assume $a_1\le b_1$. Then there are only three possible orders: $a_1ab_1b$, $a_1b_1ab$ and $a_1b_1ba$, and they respectively lead to the following satisfied inequalities:
\begin{eqnarray*} b_1-a_1+b-a\le b_1-a+b-a_1\;,\\ b_1-a_1+b-a\le a-b_1+b-a_1\;,\\ b_1-a_1+a-b\le a-b_1+b-a_1\;. \end{eqnarray*}