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^{\prime }$ 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}|>\cdots >|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^{\prime }$ does not contain the distinguished $n$. Otherwise $B_n$ and $B_n^{\prime }$ have a common part $a_1,\dots ,a_m$, possibly empty; clearly $m<|B_n|$. Now $B_n^{\prime }$ starts with $a_1,\dots ,a_m,n$ and $B_n$ ends with $a_1,\dots ,a_m$. Since $B_n$ and $B_n^{\prime }$ 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^{\prime }$. 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^{\prime }$ ends with $B_{n-1}^{\prime }$. Since $B_n$ and $B_n^{\prime }$ are identical, $B_n$ ends with a block $B_{n-1}^{\prime \prime }$ identical to $B_{n-1}$ and $B_{n-1}^{\prime }$. Now we show that $B_{n-1}^{\prime \prime }$ 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}^{\prime \prime }$. Then $B_{n-1}$ and $B_{n-1}^{\prime \prime }$ have a common part $a_1,\dots ,a_m$, possibly empty, where $m<|B_{n-1}|$. Now $B_{n-1}^{\prime \prime }$ 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}^{\prime }$ and $B_{n-1}^{\prime \prime }$ 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^{\prime }$ 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^{\prime }$ 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.