.

An arithmetic progression is a set of the form $\{a, a+d, \ldots, a+k d\}$, where $a, d, k$ are positive integers and $k \geqslant 2$. Thus an arithmetic progression has at least three elements and the successive elements have difference $d$, called the common difference of the arithmetic progression.

Let $n$ be a positive integer. For each partition of the set $\{1,2, \ldots, 3 n\}$ into arithmetic progressions, we consider the sum $S$ of the respective common differences of these arithmetic progressions. What is the maximal value $S$ that can attain?

(A partition of a set $A$ is a collection of disjoint subsets of $A$ whose union is $A$.)
The maximum value is $n^{2}$, which is attained for the partition into $n$ arithmetic progressions $\{1, n+1,2 n+1\}, \ldots,\{n, 2 n, 3 n\}$, each of difference $n$.

Suppose indeed that the set has been partioned into $N$ progressions, of respective lengths $\ell_{i}$, and differences $d_{i}$, for $1 \leqslant i \leqslant N$. Since $\ell_{i} \geqslant 3$,

$$
2 \sum_{i=1}^{N} d_{i} \leqslant \sum_{i=1}^{N}\left(\ell_{i}-1\right) d_{i}=\sum_{i=1}^{N} a_{i}-\sum_{i=1}^{N} b_{i}
$$

where $a_{i}$ and $b_{i}$ denote, respectively, the largest and smallest elements of progression $i$. Now

$$
\begin{aligned}
& \sum_{i=1}^{N} b_{i} \geqslant 1+2+\cdots+N=N(N+1) / 2 \\
& \sum_{i=1}^{N} a_{i} \leqslant(3 n-N+1)+\cdots+3 n=N(6 n-N+1) / 2
\end{aligned}
$$

and thus

$$
2 \sum_{i=1}^{N} d_{i} \leqslant N(3 n-N) \leqslant 2 n^{2}
$$

as $N(3 n-N)$ is an increasing of $N$ on the interval $[0,3 n / 2]$ and since $N \leqslant n$. This completes the proof.

Remark. The maximising partition is in fact unique: from the above, it is immediate that all maximal partitions must have $n_{i}=3$ and hence $n=N$. It follows that the minimal and maximal elements of the arithmetic progressions of a maximal partition are precisely $1,2, \ldots, n$ and $2 n+1,2 n+2, \ldots, 3 n$, respectively. Consider the progression $\{n+1-d, n+1, n+1+d\}$ of difference $d$. Then $n+1-d \geqslant 1$ and $n+1+d \geqslant 2 n+1$,
which implies $d=n$, and hence $\{1, n+1,2 n+1\}$ is an element of any maximal partition. By induction, it follows similarly that $\{k, n+k, 2 n+k\}$ is an element of any maximal partition for $1 \leqslant k \leqslant n$, since integers allowing for smaller or larger differences have already been used up. This proves the partition $\{1, n+1,2 n+1\}, \ldots,\{n, 2 n, 3 n\}$ is the unique maximising partition, as claimed.