Mathematical Olympiad Rioplatense

The minimum length in question is $2^n$.

Delete the last term of a given universal sequence and consider the shortened sequence $\alpha$. For each $i = 1, \dots, n$ the hypothesis implies that $\alpha$ starts with a block $B_i$, followed by a term $i$ which we called distinguished, and ends with a block $B'_i$ identical with $B_i$. Choose the blocks $B_i$ to be shortest possible; they are uniquely determined and different. By relabeling if necessary one may ensure $|B_n| > |B_{n-1}| > \dots > |B_1|$. (Under this assumption $\alpha$ starts with a $1$ and the shortest block $B_1$ is empty: $|B_1| = 0$.)

We claim that block $B'_n$ does not contain the distinguished $n$. Otherwise $B_n$ and $B'_n$ have a common part $a_1, \dots, a_m$, possibly empty; clearly $m < |B_n|$. Now $B'_n$ starts with $a_1, \dots, a_m, n$ and $B_n$ ends with $a_1, \dots, a_m$. Since $B_n$ and $B'_n$ are identical, $\alpha$ starts with $a_1, \dots, a_m, n$ and ends with $a_1, \dots, a_m$. But then $m < |B_n|$ contradicts the minimum choice of $B_n$. So the distinguished $n$ is not in $B'_n$. Consequently the length $\ell$ of $\alpha$ satisfies $\ell \ge 2|B_n| + 1$.

A similar argument applies to blocks $B_n$ and $B_{n-1}$ and shows that $|B_n| \ge 2|B_{n-1}| + 1$. Indeed $B_n$ starts with $B_{n-1}$, which is followed by the distinguished $n-1$, and $B'_n$ ends with $B'_{n-1}$. Since $B_n$ and $B'_n$ are identical, $B_n$ ends with a block $B''_{n-1}$ identical to $B_{n-1}$ and $B'_{n-1}$. Now we show that $B''_{n-1}$ does not contain the distinguished $n-1$; this will ensure $|B_n| \ge 2|B_{n-1}| + 1$.

Suppose on the contrary that the distinguished $n-1$ is in $B''_{n-1}$. Then $B_{n-1}$ and $B''_{n-1}$ have a common part $a_1, \dots, a_m$, possibly empty, where $m < |B_{n-1}|$. Now $B''_{n-1}$ starts with $a_1, \dots, a_m, n-1$ and $B_{n-1}$ ends with $a_1, \dots, a_m$. Since $B_{n-1}$, $B'_{n-1}$ and $B''_{n-1}$ are identical, $\alpha$ starts with $a_1, \dots, a_m, n-1$ and ends with $a_1, \dots, a_m$; but then $m < |B_{n-1}|$ contradicts the minimum choice of $B_{n-1}$. The claimed $|B_n| \ge 2|B_{n-1}| + 1$ follows.

By the same reasoning $|B_i| \ge 2|B_{i-1}| + 1$ for all $i = 2, \dots, n$. Combined with $\ell \ge 2|B_n| + 1$ this leads to $\ell \ge 2^n - 1$. Hence the initial universal sequence has length $\ell + 1 \ge 2^n$.

On the other hand for each $n$ there are universal sequences $\beta_n$ with terms in $\{1, 2, \dots, n\}$ and length $2^n$. If $n = 1$ set $\beta_1 = 1, 1$ (the length is $2 = 2^1$). Suppose that $\beta_{n-1}$ is a universal sequence with terms in $\{1, 2, \dots, n-1\}$ and length $2^{n-1}$. Write $n$ in front of every term of $\beta_{n-1}$. The obtained sequence $\beta_n$ has terms in $\{1, 2, \dots, n\}$ and length $2^n$. In addition $\beta_n$ is universal. Indeed replacing the final $1$ by $n$ yields a smooth sequence (starting and ending with $n$). Replace the final $1$ by $i \in \{1, \dots, n - 1\}$; let $\beta'_n$ be the new sequence. Suppose that the final $1$ in $\beta_{n-1}$ is also replaced by $i$. Then the resulting sequence would start and end with a block $a_1, a_2, \dots, a_m, i$ with $a_j \in \{1, \dots, n - 1\}$. By the definition of $\beta_n$ then $\beta'_n$ starts and ends with $n, a_1, n, a_2, \dots, n, a_m, n, i$, meaning that it is smooth. This completes the inductive construction and the proof.