HMMT, 2014

Solution:

We actually prove a more general result via strong induction on $n$.

First, we state the more general result we wish to prove.

For $n > 0$, define a great sequence to be a sequence of integers $(a_{0}, \ldots, a_{n})$ such that

1. $0 = |a_{0}| < |a_{1}| < \cdots < |a_{n-1}| < |a_{n}|$

2. Let $(b_{1}, b_{2}, \ldots, b_{n})$ be a set of positive integers such that $3b_{i} \leq b_{i+1}$ for all $i$. The sets $\{ |a_{1} - a_{0}|, |a_{2} - a_{1}|, \ldots, |a_{n} - a_{n-1}| \}$ and $\{ b_{1}, b_{2}, \ldots, b_{n} \}$ are equal.

Then, the number of great sequences is $(n+1)!$.

If we prove this statement, then we can just consider the specific case of $b_{1} = 1$, $3b_{i} = b_{i+1}$ to solve our problem.

Before we proceed, we will prove a lemma.

Lemma: Let $(b_{1}, b_{2}, \ldots, b_{n})$ be a set of positive integers such that $3b_{i} \leq b_{i+1}$ for all $i$. Then $b_{i} > 2 \sum_{k=1}^{i-1} b_{k}$.

Proof: $\frac{b_{i}}{2} = \frac{b_{i}}{3} + \frac{b_{i}}{9} + \cdots \geq \sum_{k=1}^{i-1} b_{k}$. Equality only occurs when the sequence $b_{i}$ is infinite, which is not the case, so the inequality holds.

We can now proceed with the induction. The base case is obvious. Assume it is true up to $n = j-1$. Next, consider some permutation of the set $B = \{ b_{1}, b_{2}, b_{3}, \cdots, b_{j} \}$. Denote it as $C = \{ c_{1}, c_{2}, \ldots, c_{j} \}$. Find the element $c_{k} = b_{j}$. For the first $k-1$ elements of $C$, we can put them in order and apply the inductive hypothesis. The number of great sequences such that the set of differences $\{ |a_{1} - a_{0}|, \ldots, |a_{k-1} - a_{k-2}| \}$ is equal to $\{ c_{1}, c_{2}, \ldots, c_{k-1} \}$ is $k!$.

Then, $a_{k}$ can be either $a_{k-1} + c_{k}$ or $a_{k-1} - c_{k}$. This is because, by the lemma, $c_{k} > 2 \sum_{m=1}^{k-1} c_{m} = 2 \sum_{m=1}^{k-1} |a_{m} - a_{m-1}| \geq 2|a_{k-1} - a_{k-2} + a_{k-2} - a_{k-3} + \cdots + a_{1} - a_{0}| = 2|a_{k-1}|$. It is easy to check that for either possible value of $a_{k}$, $|a_{k}| > |a_{k-1}|$. After that, there is only one possible value for $a_{k+1}, \ldots, a_{j}$ because only one of $a_{i} \pm c_{i+1}$ will satisfy $|a_{i}| > |a_{i-1}|$.

There are $\binom{j-1}{k-1}$ possible ways to choose $c_{1}, c_{2}, \ldots, c_{k-1}$ from $B$. Given those elements of $C$, there are $k!$ ways to make a great sequence $(a_{0}, a_{1}, \ldots, a_{k-1})$. Then, there are 2 possible values for $a_{k}$. After that, there are $(j-k)!$ ways to order the remaining elements of $C$, and for each such ordering, there is exactly 1 possible great sequence $(a_{0}, a_{1}, \ldots, a_{j})$.

Now, counting up all the possible ways to do this over all values of $k$, we get that the number of great sequences is equal to
$$\sum_{k=1}^{j} \binom{j-1}{k-1} k! 2 (j-k)! = \sum_{k=1}^{j} 2 (j-1)! (k) = 2 (j-1)! \frac{j(j+1)}{2} = (j+1)!.$$
The induction is complete, and this finishes the proof.

Alternate solution:

Another method of performing the induction is noting that any acceptable sequence $(a_{0}, \ldots, a_{n})$ can be matched with $n+2$ acceptable sequences of length $n+2$ because we can take $(3a_{0}, \ldots, 3a_{n})$ and add an element with a difference of 1 in any of $n+2$ positions.