Bulgarian Mathematical Competitions

Solution:

Answer: there is such a sequence. We shall define the required sequence inductively. We set $a_{1}=1$, $a_{2}=2$ and assume that $a_{1}, a_{2}, \ldots, a_{2k}$ are already determined. Denote by $m$ the smallest positive integer which cannot be represented as $a_{j}-a_{i}$, $1 \leq i < j \leq 2k$. Since the number of such differences is $d = k(2k-1)$, we have $m \leq d+1$.

Set $a_{2k+2} = a_{2k+1} + m$, where $a_{2k+1}$ is such that
$$\begin{aligned} & a_{2k+1} \neq a_{l},\quad a_{2k+1} \pm m \neq a_{l} \\ & a_{2k+1} - a_{l} \neq a_{j} - a_{i},\quad a_{2k+1} + m - a_{l} \neq a_{j} - a_{i} \end{aligned}$$
for $1 \leq l \leq 2k$, $1 \leq i < j \leq 2k$. This implies that $a_{1}, a_{2}, \ldots, a_{2k+2}$ are all distinct and every integer between $1$ and $m$ can be written in a unique way as $a_{j}-a_{i}$, $1 \leq i < j \leq 2k+2$.

Since there are exactly $6k + 4kd$ "forbidden" values for $a_{2k+1}$, we can choose $a_{2k+1}$ with the above properties and such that $a_{2k+1} \leq 6k + 4kd + 1$. Then
$$a_{2k+1} < a_{2k+2} = a_{2k+1} + m \leq 6k + 4kd + 1 + d + 1 < (2k+1)^{3}$$
and it remains to put the numbers $a_{1}, a_{2}, \ldots, a_{2k+2}$ in increasing order (check that the inequality $a_{n} \leq n^{3}$ is still valid).