BMO Shortlist, 2010

Let $\lfloor x \rfloor$ be the largest integer less than or equal to $x$ and $\lceil x \rceil$ the smallest integer greater than or equal to $x$. The smallest number $S$ that can be represented in the given form is $n-1$, while the largest number is $\lfloor \frac{n^2}{4} \rfloor$.
Since $a_2 a_3 \ge a_3$, $a_3 a_4 \ge a_4$, $\dots$, $a_{k-1} a_k \ge a_k$, it follows
$$S \ge a_1 a_2 + a_3 + a_4 + \dots + a_k = n + a_1 a_2 - a_1 - a_2 = n-1 + (a_1-1)(a_2-1) \ge n-1.$$
The equality holds if and only if $a_2 = a_3 = \dots = a_{k-1} = 1$. Indeed, for $a_2 = a_3 = \dots = a_{k-1} = 1$ we have $n = a_1 + \underbrace{1+1+\dots+1}_{n-2} + a_k$, and
$$S = a_1 \cdot 1 + \underbrace{1 \cdot 1 + 1 \cdot 1 + \dots + 1 \cdot 1}_{n-3} + 1 \cdot a_k = n-1.$$
If
$$S = a_1 a_2 + a_2 a_3 + \dots + a_{k-1} a_k = n-1,$$
then
$$S = a_1 a_2 + a_2 a_3 + \dots + a_{k-1} a_k = \\ a_1 + a_2 + \dots + a_k - 1 \Leftrightarrow \\ \Leftrightarrow a_1(a_2-1) + a_2(a_3-1) + \dots + a_{k-1}(a_k-1) - (a_k-1) = 0 \Leftrightarrow \\ \Leftrightarrow a_1(a_2-1) + a_2(a_3-1) + \dots + (a_k-1)(a_{k-1}-1) = 0$$
Since $a_j \ge 1$ for all $j \in \{1, 2, \dots, n\}$, we have $a_2 = a_3 = \dots = a_{k-1} = 1$.
From the arithmetic-geometric mean inequality for $k=2$ and $k=3$, we have
$$S = a_1 a_2 \le \lfloor \left( \frac{a_1 + a_2}{2} \right)^2 \rfloor = \lfloor \frac{n^2}{4} \rfloor$$
and
$$S = a_1 a_2 + a_2 a_3 = a_2(a_1 + a_3) \le \lfloor \frac{n^2}{4} \rfloor.$$
Let $a_i$ be the maximal element among $a_1, a_2, \dots, a_k$. It follows
$$S = a_1 a_2 + a_2 a_3 + \dots + a_{k-1} a_k = \\ a_1 a_2 + a_2 a_3 + \dots + a_{i-1} a_i + a_i^2 + a_i a_{i+1} + \dots + a_{k-1} a_k - a_i^2 \le \\ \le a_1 a_i + a_2 a_i + \dots + a_{i-1} a_i + a_i^2 + a_i a_{i+1} + a_i a_{i+2} + \dots + a_i a_k - a_i^2 = \\ = a_i(a_1 a_2 + a_2 a_3 + \dots + a_{k-1} a_k) - a_i^2 + a_i n - a_i^2 = a_i(n-a_i) \le \lfloor \frac{n^2}{4} \rfloor.$$
The equality holds for $k=2$ if and only if $|a_1 - a_2| \le 1$ or for $k=3$ if and only if $|(a_1 + a_3) - a_2| \le 1$. Indeed, for arbitrary positive integer numbers $a, b$ such that $a \le b$, $a+b=n$, $n > 2$ there exists an integer number $\alpha$ such that $b = a + \alpha$. Then
$$ab = \lfloor \frac{n^2}{4} \rfloor \Leftrightarrow ab = \lfloor \frac{(a+b)^2}{4} \rfloor \Leftrightarrow a(a+\alpha) = \lfloor \frac{(2a+\alpha)^2}{4} \rfloor \Leftrightarrow \\ a^2 + \alpha a = \lfloor \frac{4a^2 + 4\alpha a + \alpha^2}{4} \rfloor \Leftrightarrow a^2 + \alpha a = a^2 + \alpha a + \lfloor \frac{\alpha^2}{4} \rfloor \Leftrightarrow \lfloor \frac{\alpha^2}{4} \rfloor = 0$$
$$\Leftrightarrow 0 \le \frac{\alpha^2}{4} < 1 \Leftrightarrow 0 \le \alpha^2 < 4 \Leftrightarrow 0 \le \alpha^2 \le 1 \Leftrightarrow |a-b| \le 1.$$
We will prove by induction that all numbers from the interval
$$\lfloor n - 1, \lfloor \frac{n^2}{4} \rfloor \rfloor$$
can be represented using only the partitions with $a_1 = 1$. The cases $n = 3$ and $n = 4$ can be easily verified. Suppose it is true for $n-1$ and will prove for $n$. According to the step of induction we generate all numbers $S' = a'_1 a'_2 + a'_2 a'_3 + \dots + a'_{k-1} a'_k$ such that
$$S' \in \lfloor n - 2, \lfloor \frac{(n-1)^2}{4} \rfloor \rfloor$$
and $a'_1 + a'_2 + \dots + a'_{k-1} + a'_k = n-1$.
Now, adding 1 as first element to every representation of $S'$ we obtain all representations $S$ ($S = S' + 1$) of $n$ such that
$$S \in \lfloor n - 1, \lfloor \frac{(n-1)^2}{4} \rfloor + 1 \rfloor,$$
where
$$\lfloor \frac{(n-1)^2}{4} \rfloor + 1 = \lfloor \frac{n^2}{4} - \frac{n}{2} + \frac{1}{4} \rfloor + 1.$$
Therefore, we only need to construct the numbers from $\lfloor \frac{n^2}{4} - \frac{n}{2} + \frac{1}{4} \rfloor + 2$ to $\lfloor \frac{n^2}{4} \rfloor - 1$.
Set $k = 4$ and $a_1 = 1$, $a_2 = x$, $a_3 = \lfloor \frac{n}{2} \rfloor - 1$, $a_4 = \lfloor \frac{n}{2} \rfloor - x$, with $1 \le x \le \lfloor \frac{n}{2} \rfloor - 1$. It follows
$$S = x + x \left( \lfloor \frac{n}{2} \rfloor - 1 \right) + \left( \lfloor \frac{n}{2} \rfloor - 1 \right) \left( \lfloor \frac{n}{2} \rfloor - x \right) = x + \lfloor \frac{n}{2} \rfloor \lfloor \frac{n}{2} \rfloor - x = x + \lfloor \frac{n^2}{4} \rfloor - \lfloor \frac{n}{2} \rfloor.$$
The equality
$$x + \lfloor \frac{n}{2} \rfloor \lfloor \frac{n}{2} \rfloor - x = x + \lfloor \frac{n^2}{4} \rfloor - \lfloor \frac{n}{2} \rfloor$$
can be proved considering both cases $n$ odd, and respectively $n$ even.
For $x = 1, 2, \dots, \lfloor \frac{n}{2} \rfloor - 1$ we get all numbers from $1 + \lfloor \frac{n^2}{4} \rfloor - \lfloor \frac{n}{2} \rfloor$ to $\lfloor \frac{n^2}{4} \rfloor - 1$. Since
$$\lfloor \frac{n^2}{4} - \frac{n}{2} + \frac{1}{4} \rfloor + 2 \ge 1 + \lfloor \frac{n^2}{4} \rfloor - \lfloor \frac{n}{2} \rfloor,$$
this completes the proof. $\square$