BxMO

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Benelux Mathematical Olympiad

Problem:

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$ .)

Solution

Solution:

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 partitioned 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 increasing in $N$ on the interval $[0,3 n / 2]$ and since $N \leqslant n$ . This completes the proof.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.