AoPS - Problem

Source: Benelux Mathematical Olympiad 2015, Problem 4

Tags: combinatorics, arithmetic sequence

Lepuslapis

10.05.2015 12:18

Let $n$ be a positive integer. For each partition of the set $\{1,2,\dots,3n\}$ into arithmetic progressions, we consider the sum $S$ of the respective common differences of these arithmetic progressions. What is the maximal value that $S$ can attain? (An arithmetic progression is a set of the form $\{a,a+d,\dots,a+kd\}$, where $a,d,k$ are positive integers, and $k\geqslant 2$; thus an arithmetic progression has at least three elements, and successive elements have difference $d$, called the common difference of the arithmetic progression.)

The maximum value is $n^2$. Basically, take $a, a+n, a+2n$ as your arithmetic progressions. Basically, each arithmetic progression has a minimum $x$ and a maximum $y$, and the common difference $d \le \frac{y-x}{2}$. We show that the above sequence minimizes $S' = \sum y-x$ (and since equality holds with $d = \frac{y-x}{2}$, it then must optimize $S$. There are at most $n$ sequences, so for any $k \le n$ the number of sequences, we take the largest $k$ numbers to be the $y$s and the smallest $k$ to be the $x$s to maximize $S'$ with fixed $k$, and this is maximized when $k = n$. This is what happens in the aforementioned sequence. Yay.