, 2020

Note that if we shift all numbers in the set by the same value, the errors will remain the same. Hence we can consider the partitions of the set $\{1, 2, \ldots, 2019\}$, moreover, we will solve the generalized problem by changing $2019$ with an arbitrary number $3n$, $n \in \mathbb{N}$.

Consider the partition of the set $\{1, 2, \ldots, 3n\}$, which provides the maximal sum of all errors. Let's say that the triple $a < b < c$ is left if $b \le (a+c)/2$, otherwise let's say that it's right.

We start with the following

Step 1. Suppose the triple $a < b < c$ is right and $b \le c - 2$. Choose a triple $x < y < z$ such that $b+1 \in \{x, y, z\}$ and swap the numbers $b$ and $b+1$ in these triples. Since the error of the first triple will increase by $1$ and we started from the partition with the maximal sum of errors, it follows that $b+1 = y$ and $x < y < z$ is left (otherwise the sum of errors will increase). Similarly, if the triple $a < b < c$ is left and $a \le b - 2$ then there exists a right triple $x < b - 1 < y$ and we will swap $b$ and $b-1$ in these triples. We will perform such operation while it's possible. Clearly, this process is finite, since the middle numbers in the right triples increase while in the left triples they decrease and the triples doesn't change their type. The final partition will satisfy the

Property 1. Each right triple has the form $a < b < b+1$ and each left triple has the form $a < a+1 < c$.

Step 2. Consider any two triples $x < y - 1 < y$ and $a < a + 1 < b$ of different types. The sum of errors of these two triples equals $\frac{b+y-a-x}{2} - 2$.

Suppose $y < a$. Replace these triples with $x < a < a+1$ and $y - 1 < y < b$, then the new sum of errors will become equal to $\frac{b+a-y-x}{2} - 2 > \frac{b+y-a-x}{2} - 2$, which contradicts the maximality of our partition. Hence $a > y$.

Suppose $b < x$. Replace these triples with $b < y - 1 < y$ and $a < a + 1 < x$, then the new sum of errors will become equal to $\frac{y+x-b-a}{2} - 2 > \frac{b+y-a-x}{2} - 2$, which contradicts the maximality of our partition. Hence $b > x$.

Consider two triples $x < y - 1 < y$ and $t < z - 1 < z$ of the same (without loss of generality, right) type. The sum of errors of these two triples equals $\frac{z+y-t-a}{2} - 2$. Suppose $y < t$ and swap $x$ and $t$ in these triples. Then we get triples $y - 1 < y < t$ and $x < z - 1 < z$ of different types with their sum of errors $\frac{z+t-x-y+1}{2} - 2 > \frac{z+y-t-a}{2} - 2$, which contradicts the maximality of our partition. Hence $y > t$.

Therefore the partition satisfy

Property 2. The maximal element of each triple is greater than the minimal element of any other triple.

Step 3. Suppose there exist triples $x < y - 1 < y$ and $a < a+1 < b$ such that $a < x$, and choose such triples with minimal possible $x$ and (for that value of $x$) maximal possible $a$. Consider the number $a+2$: due to the property 2 it cannot be the maximal element of any triple and due to our choice of the pair $(x, a)$ it cannot be the minimal element of any triple except $x < y - 1 < y$. Thus we have found triples

$a < a + 1 < b$ and $a + 2 < y - 1 < y$ with the sum of errors $\frac{b+y-2a-2}{2} - 2$. Consider the triples $a+1 < a+2 < b$ and $a < y-1 < y$: their sum of errors equals $\frac{b+y-2a-1}{2} - 2 > \frac{b+y-2a-2}{2} - 2$, which contradicts the maximality of our partition. Hence $x > a$. Replacing each number $t$ with $3n-t$ we get the inequality $b > y$. Hence we proved the final

Property 3. The minimal element of each right triple is smaller than the minimal element of each left triple. The maximal element of each left triple is greater than the maximal element of each right triple.

Combining the properties 1–3 we obtain the following description of the partition with the maximal sum of errors: there exist $k, \ell \in \mathbb{N}$ with $k + \ell = n$ such that the numbers $1, 2, \dots, k$ are minimal in the right triples, $k+1, k+3, \dots, k+2\ell-1$ are minimal in the left triples, $k+2\ell+2, k+2\ell+4, \dots, 3k+2\ell$ are maximal in the right triples, $3k+2\ell+1, 3k+2\ell+1, \dots, 3k+3\ell$ are maximal in the left triples. In such partition the sum of errors equals

$$\begin{align*} & \frac{(k+2\ell+2) + (k+2\ell+4) + \dots + (3k+2\ell) - 1 - 2 - \dots - k}{2} - k + \\ & \qquad + \frac{(3k+2\ell+1) + (3k+2\ell+2) + \dots + (3k+3\ell) - (k+1) - (k+3) - \dots}{2} \\ & \qquad \dots - \frac{(k+2\ell-1)}{2} - \ell = \frac{(k+2\ell)k + 2 \cdot \frac{k(k+1)}{2} - \frac{k(k+1)}{2}}{2} + \\ & \qquad + \frac{(3k+2\ell)\ell + \frac{\ell(\ell+1)}{2} - (k-1)\ell - 2 \cdot \frac{\ell(\ell+1)}{2}}{2} - k - \ell = \\ &= \frac{3k(k-1) + 3\ell(\ell-1) + 8k\ell}{4} = \frac{3(k+\ell)^2 - 3(k+\ell) + 2k\ell}{4} = \frac{3n^2 - 3n + 2k\ell}{4}. \end{align*}$$

The expression $2k\ell = 2k(n-k)$ attains its maximal value at $k = \left\lfloor \frac{n}{2} \right\rfloor$, hence we get the answer

$$\frac{3n^2 - 3n + 2 \lfloor \frac{n}{2} \rfloor \lfloor \frac{n}{2} \rfloor}{4}.$$