Problem 1959

The answer are $n \in \{2, 3, 4\}$. We first show a solution for each $n \in \{2, 3, 4\}$. We will later show the impossibility of finding such a solution for $n \ge 5$.

For $n = 2$, take for example $(a_1, a_2) = (1, 3)$ and $r = 2$.

For $n = 3$, take the root $r > 1$ of $x^3 - x - 1 = 0$ (the golden ratio) and set $(a_1, a_2, a_3) = (0, r, r + r^2)$, then
$$(a_2 - a_1, a_3 - a_2, a_3 - a_1) = (r, r^2, r + r^2 = r^3).$$

For $n = 4$, take the root $r \in (1, 2)$ of $x^3 - x - 1 = 0$ (such a root exists because $1^3 - 1 - 1 < 0$ and $2^3 - 2 - 1 > 0$) and set $(a_1, a_2, a_3, a_4) = (0, r, r + r^2, r + r^2 + r^3)$, then
$$(a_2 - a_1, a_3 - a_2, a_4 - a_3, a_3 - a_1, a_4 - a_2, a_4 - a_1) = (r, r^2, r^3, r^4, r^5, r^6).$$

For $n \ge 5$, we will proceed by contradiction. Suppose that there exist numbers $a_1 < a_2 < \dots < a_n$ and $r > 1$ satisfying the conditions of the problem. We start with a lemma:

Lemma. We have $r^{n-1} > 2$.
Proof. There are only $n-1$ differences $a_j - a_i$, with $j = i + 1$, so there exists an exponent $e \le n$ and a difference $a_j - a_i$ with $j \ge i + 2$ such that $a_j - a_i = r^e$. This implies that
$$r^n \ge r^e = a_j - a_i = (a_j - a_{j-1}) + (a_{j-1} - a_i) > r + r = 2r,$$
thus $r^{n-1} > 2$ as desired. To illustrate the general approach, we first briefly sketch the idea behind the argument in the special case $n = 5$. In this case, we clearly have $a_5 - a_1 = r^{10}$. Note that there are 3 ways to rewrite $a_5 - a_1$ as a sum of two differences, namely
$$(a_5 - a_4) + (a_4 - a_1), (a_5 - a_3) + (a_3 - a_1), (a_5 - a_2) + (a_2 - a_1).$$
Using the lemma above and convexity of the function $f(n) = r^n$, we argue that those three ways must be $r^{10} = r^9 + r^1 = r^8 + r^4 = r^7 + r^6$. That is, the “large” exponents keep dropping by 1, while the “small” exponents keep increasing by $n-2, n-3, \dots, 2$. Then comparing any two such equations to get a contradiction unless $n \le 4$.

Now we go back to the full proof for any $n \ge 5$. Denote $b = \frac{1}{2}n(n-1)$. Clearly, we have $a_n - a_1 = r^b$. Consider the $n-2$ equations of the form:
$$a_n - a_1 = (a_n - a_i) + (a_i - a_1) \text{ for } i \in \{2, \dots, n-1\}.$$
In each equation, one of the two terms on the right-hand side must be at least $\frac{1}{2}(a_n - a_1)$. But from the lemma we have
$$r^{b-(n-1)} = r^b/r^{n-1} < \frac{1}{2}(a_n - a_1),$$
so there are at most $n-2$ sufficiently large elements in $\{r^k|1 \le k < b\}$, namely $r^{b-1}, \dots, r^{b-(n-2)}$ (note that $r^b$ is already used for $a_n - a_1$). Thus, the “large” terms must be, in some order, precisely equal to elements in
$$L = r^{b-1}, \dots, r^{b-(n-2)}.$$
Next we claim that the “small” terms in the $n-2$ equations must be equal to the elements in
$$S = \{r^{b-(n-2)-\frac{1}{2}i(i+1)} | 1 \le i \le n-2\},$$
in the corresponding order (the largest “large” term with the smallest “small” term, etc.). Indeed, suppose that
$$r^b = a_n - a_1 = r^{b-i} + r^{\alpha_i} \text{ for } i \in \{1, \dots, n-2\},$$
where $1 \le \alpha_1 < \dots < \alpha_{n-2} \le b - (n-1)$. Since $r > 1$ and $f(r) = r^n$ is convex, we have
$$r^{b-1} - r^{b-2} > r^{b-2} - r^{b-3} > \dots > r^{b-(n-3)} - r^{b-(n-2)},$$
implying $r^{\alpha_2} - r^{\alpha_1} > r^{\alpha_3} - r^{\alpha_2} > \dots > r^{\alpha_{n-2}} - r^{\alpha_{n-3}}$. Convexity of the function $f(r) = r^n$ further implies
$$\alpha_2 - \alpha_1 > \alpha_3 - \alpha_2 > \dots > \alpha_{n-2} - \alpha_{n-3}.$$
Note that $\alpha_{n-2} - \alpha_{n-3} \ge 2$: Otherwise we would have $\alpha_{n-2} - \alpha_{n-3} = 1$ and thus
$$r^{\alpha_{n-3}} \cdot (r-1) = r^{\alpha_{n-2}} - r^{\alpha_{n-3}} = r^{b-(n-3)} - r^{b-(n-2)} = r^{b-(n-2)} \cdot (r-1),$$
implying that $\alpha_{n-3} = b - (n - 2)$, a contradiction. Therefore, we have
$$\begin{aligned} \alpha_{n-2} - \alpha_1 &= (\alpha_{n-2} - \alpha_{n-3}) + \dots + (\alpha_2 - \alpha_1) \\ &\ge 2 + 3 + \dots + (n-2) = \frac{1}{2}(n-2)(n-1) - 1 = \frac{1}{2}n(n-3). \end{aligned}$$
On the other hand, from $\alpha_{n-2} \le b - (n - 1)$ and $\alpha_1 \ge 1$ we get
$$\alpha_{n-2} - \alpha_1 \le b - n = \frac{1}{2}n(n-1) - n = \frac{1}{2}n(n-3),$$
implying that equalities must occur everywhere and the claim about the small terms follows. Now assuming $n-2 \ge 2$, we have the two different equations:
$$r^b = r^{b-(n-2)} + r^{b-(n-2)-1} \quad \text{and} \quad r^b = r^{b-(n-3)} + r^{b-(n-2)-3},$$
which can be rewritten as
$$r^{n-1} = r + 1 \text{ and } r^{n+1} = r^4 + 1.$$
Simple algebra now gives
$$r^4 + 1 = r^{n+1} = r^{n-1} \cdot r^2 = r^3 + r^2 \longrightarrow (r-1)(r^3 - r - 1) = 0.$$
Since $r \ne 1$, using (1) we conclude $r^3 = r + 1 = r^{n-1}$, thus $n = 4$, which gives a contradiction. □