Only approximately $10^{605}$ cases

Claim: $\max{(a_i,b_i)} \in \{1010,1011,...,2018\}$ and $\min{(a_i,b_i)} \in \{1, 2, …, 1009\}$ for all $i$ .

Proof of Claim: Assume not. Then there is an $1 \leq m \leq 1009$ such that (1) $a_m > 1009, b_m > 1009$ or (2) $a_m \leq 1009, b_m \leq 1009$ .

Case (1): $1009 < a_m < a_{m+1} < … < a_{1009} \leq 2018, 1009 < b_m < b_{m-1} < … < b_1 \leq 2018$ , so there are $1010$ distinct integers ( $b_1,..., b_m, a_m, …, a_{1009}$ ) between $1010$ and $2018$ inclusive, contradiction by Pigeonhole principle.

Case (2): similar to (1)

so the claim holds and the desired sum must be $1010+1011+...+2018-(1+2+...+1009)$ for any partition of $\{1,2,...,2018\}$ .

They asked for the sum of all possible values so I supposed that the result would be the same no matter how you divide the groups. Then I choosed the a group [1,1009] and the b group [1010,2018] b1 being 2018 and so on. Divided this way, the sum of a-b for all the elements will be 1009. so the result will be 1009 times 1009 equal 1018081.

Sorry this is my first contribution here so I didn't express well my solution but I hope you understood me!

We induct on $N(\mathbf{a},\mathbf{b}) = \Big|\{(i,j)\, :\, a_i < b_j, 1\leq i,j \leq 1009 \}\Big|$

First note that if $N(\mathbf{a},\mathbf{b})=0$ , then $a_1 > b_1$ so $b_{1009} < b_{1008} < \cdots < b_2 < b_1 < a_1 < a_2 < \cdots < a_{1008} < a_{1009}$ which implies $a_i - b_i = 2i-1$ for all $1\leq i\leq 1009$ , so $\sum_{i=1}^{1009} |a_i-b_i| = \sum_{i=1}^{1009} (2i-1) = 1009^2 = 1018081.$

Now suppose $N(\mathbf{a},\mathbf{b})>0$ . Then there must be some $1\leq n,m\leq 1009$ such that $a_n < b_m.$ Let $n$ be the maximum such value and then, subject to this $n$ , let $m$ be the maximum such value. That is, $b_{m+1} < a_n < b_m < b_{m-1} < \cdots < b_2 < b_1 < a_{n+1}$ (See the note below for a comment on one possible issue). We now consider the new sequences $a'_i = \begin{cases}a_i & i\neq n \\ b_m & i=n\end{cases}, \qquad b'_i = \begin{cases}b_i & i\neq m \\ a_n & i=m\end{cases}$ It's easy to see that these satisfy $a'_1 < a'_2 < \cdots < a'_{1009}, \qquad b'_1 > b'_2 > \cdots > b'_{1009}$ and $N(\mathbf{a'}, \mathbf{b'}) = N(\mathbf{a}, \mathbf{b})-1,$ so we now turn to the task of evaluating $|a'_1-b'_1| + |a'_2-b'_2| + \cdots + |a'_{1009} - b'_{1009}|.$ Immediately, we see that $|a'_i-b'_i| = |a_i-b_i|$ for all $i \neq n,m$ . For the remaining term(s), we consider the following cases:

• Case 1: $n=m$ Then $|a'_n - b'_n| = |b_n - a_n| = |a_n-b_n|$
• Case 2: $n<m$ Then $b_m < a_{n+1} \leq a_m$ and $a_n < b_m < b_n$ , so $|a'_n - b'_n| + |a'_m - b'_m| = |b_m - b_n| + |a_m-a_n| = b_n - b_m + a_m - a_n = |a_n - b_n| + |a_m - b_m|$
• Case 3: $n>m$ Then $a_m < a_n < b_m$ and $b_n \leq b_{m+1} < a_n$ , so $|a'_n - b'_n| + |a'_m - b'_m| = |b_m - b_n| + |a_m-a_n| = b_m - b_n + a_n - a_m = |a_n - b_n| + |a_m - b_m|$

Therefore, we see that $\sum_{i=0}^{1009} |a_i - b_i| = \sum_{i=0}^{1009} |a'_i - b'_i|$ so by induction, $\sum_{i=0}^{1009} |a_i - b_i| = 1009^2 = 1018081$

We can conclude that the only possible value of $|a_1-b_1| + |a_2-b_2| + \cdots + |a_{1009}-b_{1009}|$ is $1018081$ , so trivially the sum of all possible values is also $\boxed{1018081}.$

---

Note : When I'm defining $n,m$ for the inductive step, I reference $b_{m+1}$ and $a_{n+1}$ in the following inequality. Of course, if either of $m,n$ equals $1009$ , then the corresponding value isn't defined. However, this doesn't effect the rest of the proof, as it's only important when the corresponding term does exist to show that the $\mathbf{a'}, \mathbf{b'}$ sequences are increasing and decreasing, respectively.

Taking the first few partial sums we get:

|1 - 2018| = 2017,

|2 - 2017| = 2015,

|3 - 2016| = 2013, and so on

Thus it is deduced that we are being asked to sum the consecutive odd integers $\leq$ 2017. There is a theorem that states that sum of consecutive odd integers is equal to the square of the number of integers summed. Don't feel like giving a detailed proof because it is fairly intuitive when looking at the first few cases:

1 + 3 = 4,

1 + 3 + 5 = 9,

1 + 3 + 5 + 7 =16 and so on.

Therefore the sum is equal to $1009^2$ = 1018081

I will first prove that, for any even number $N$ , if the numbers from 1 to $N$ are divided into two groups $a_1 < ... < a_{\frac{N}{2}}$ and $b_1 > ... > b_{\frac{N}{2}}$ , then the sum $\sum_{k = 1}^{\frac{N}{2}} |a_k - b_k|$ is the same regardless of the grouping. To see this, imagine the numbers from 1 to $N$ as being stretched out in a line and half of them bolded. The bolded numbers are in the $b$ group, and the non-bolded ones are in the $a$ group. For $N = 4$ , it might look like: 1 2 3 4 . Notice that any possible grouping can be created from any other by repeatedly switching which of two adjacent numbers in different groups is bolded. For example, the grouping 1 2 3 4 can be created from 1 2 3 4 with three such swaps:

1 2 3 4 $\rightarrow$ 1 2 3 4 $\rightarrow$ 1 2 3 4 $\rightarrow$ 1 2 3 4.

I now claim that performing a swap as defined above does not change the value of $\sum_{k = 1}^{\frac{N}{2}} |a_k - b_k|$ . To see this, consider the configuration 1 ... $x$ $\mathbf{x + 1}$ ... N. Here, $x = a_i$ and $x + 1 = b_j$ . If $i = j$ , their contribution to the sum is $|x + 1 - x| = 1$ , and swapping would simply make it $|x - (x + 1)| = |-1| = 1$ , which is the same. If $i \neq j$ , then these two and their partners ( $b_i$ and $a_j$ ) in their opposite groups make a contribution to the sum of $|x - b_i| + |a_j - (x + 1)|$ . Now perform a swap to get 1 ... $\mathbf{x}$ $x + 1$ ... N. After the swap, $x = b_j$ and $x + 1 = a_i$ . Their new contribution to the sum is $|(x + 1) - b_i| + |a_j - x| = |(x - b_i) + 1| + |(a_j - (x + 1)) + 1|$ . To show that the the new contribution is identical to the old, two situations must be considered:

• If $x > b_i$ , meaning that $x - b_i$ is positive, then $a_j - (x + 1)$ must be negative. This is true because $x + 1$ is larger than $b_i$ , and, since it's part of the $b$ group, must therefore be matched with a member of the $a$ group smaller than $x$ .
• If $x < b_i$ , meaning that $x - b_i$ is negative, then $b_i > x + 1$ , so $a_j - (x + 1)$ must be positive since $x + 1$ , as a member of the $b$ group that is less than $b_i$ , will be matched to a member of the $a$ group that is greater than $x$ .This reasoning might seem flawed but it's not because the case where $x = a_j$ and $x + 1 = b_i$ has already been ruled out by specifying that $i \neq j$ .

The cases above show that the two expressions within the absolute values will always have opposite sign. Therefore, adding one within the absolute value signs to both expressions, as is done by the swapping, will have opposite effects on each, adding 1 to one of the absolute values and subtracting 1 from the other. The net effect is zero, so a swap with the number on the right beginning in the $b$ group does not alter the contribution of the two numbers and their partners to the sum. A swap with the number on the right beginning in the $a$ group is just the reverse, so the net effect of this is zero as well. It's pretty easy to see that a swap doesn't change the values of any other pairs $|a_k - b_k|$ . This means swaps do not alter the sum at all. Since any grouping can be transformed to any other through swaps, all groupings have the same sum. A convenient grouping can be chosen to calculate it. Making all the numbers from 1 to $\frac{N}{2}$ part of the $a$ group and all the remaining numbers part of the $b$ shows that the sum is equal to the sum of the first $\frac{N}{2}$ odd numbers, or $(\frac{N}{2})^2$ . For $N = 2018$ , this is $1009^2 = 1018081$ .

Let $A$ be the set of all $a_n$ and let $B$ be the set of all $b_n$ .

For all $1 \leq n \leq 1009$ , if $a_n \leq 1009$ , then there must be at least $n$ members of $A$ that are less than or equal to 1009. By the lemma, there are at least $n$ members of $B$ that are greater than 1009. That means $b_n \gt 1009$ . Since the converse also holds, we can conclude $a_n \leq 1009 \Leftrightarrow b_n \gt 1009$ .

After removing absolute values and rearranging terms, the sum is $\boxed{1009^2}$ .

Lemma: $|\{x \in A \mid x \leq 1009\}| = |\{x \in B \mid x \gt 1009\}|$
This can be proved by combining the following two statements:
$|\{x \in A \mid x \leq 1009\}| + |\{x \in B \mid x \leq 1009\}| = 1009$
$|\{x \in B \mid x \leq 1009\}| + |\{x \in B \mid x \gt 1009\}| = 1009$

First, set:

$a_{1}=1, a_{2}=2, ... , a_{1009}=1009, b_{1009}=1010, ... , b_{1}=2018.$

Trivially, the sum is

$\sum_{n=1}^{1009} 2n-1 = 1009^2 = 1018081$ .

Then show that any other configuration change doesn't produce any different sum value: any configuration can be reached switching an a with a b (you cannot switch a with a or b with b, because of the order) and any a-b switch makes one element of the sum +1 and another one -1. Configuration change is an invariance for the total sum. So there is only one possible value for the sum, 1009^2, and the sum of all possible values is 1009^2.

Carl Friedrich Gauss as an elementary student (1700s) amazed his teacher when he quickly found sum of the integers from 1 to 100 to be 5,050. Gauss recognized he had fifty pairs of numbers when he added the first and last number in the series, the second and second-last number in the series, and so on. For example: (1 + 100), (2 + 99), (3 + 98), . . . , and each pair has a sum of 101.

Following the steps of this great man: 1-1010=-1009; 2-1011=-1009; 3-1012=-1009... So, (-1009)(1009 pairs)=-1018081 Absolute value= 1018081

From the text it is clear that you could choose any such sequence. I chose 1 to 1009 and 1010 to 2018. The elements of the sum are then 1, 3, 5, ... 1009 so the sum is 1009^2.

For the numbers $1,2,3,4$ there are only $\binom{4}{2}=6$ possible groups and the process gives 4 for all of them.

For the numbers $1,2,3,4,5,6$ there are only $\binom{6}{3}=20$ possible groups and the process gives 9 for all of them.

Beyond this, there are too many to write them all out, but the structure is already apparent in these small examples.

It is pretty clear that the process for the numbers $1,2,3,...,2n$ always gives the value $n^{2}$ but I don't quite have a proof.

It seems like the best way would be to show that swapping any value from $a$ with one from $b$ doesn't change the value. This is complicated by the fact that some $a_{i}$ will have to shift position and the point where the $a_{j}$ begins to exceed $b_{j}$ might also switch.

I will need to give this more thought.