Question 21
$n$ is a positive integer. A universal sequence of length $m$ is a sequence of $m$ integers each between $1$ and $n$ such that one can obtain any permutation of $1, 2, \ldots, n$ by deleting suitable members of the sequence. For example, $1, 2, 3, 1, 2, 1, 3$ is a universal sequence of length $7$ for $n = 3$. But $1, 2, 3, 2, 1, 3, 1$ is not universal, because one cannot obtain the permutation $3, 1, 2$.
Show that one can always obtain a universal sequence for $n$ of length $n^2 - n + 1$.
Show that a universal sequence for $n$ must have length at least $n(n + 1) / 2$.
Show that the shortest sequence for $n = 4$ has $12$ members.
[You are told, but do not have to prove, that there is a universal sequence for $n$ of length $n^2 - 2n + 4$.]
Show that one can always obtain a universal sequence for $n$ of length $n^2 - n + 1$.
Show that a universal sequence for $n$ must have length at least $n(n + 1) / 2$.
Show that the shortest sequence for $n = 4$ has $12$ members.
[You are told, but do not have to prove, that there is a universal sequence for $n$ of length $n^2 - 2n + 4$.]