RU-ALLRUSSIAN 1976 Problem 12

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, ..., 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$ .]