Дано естественное число n. Последовательность естественных чисел a1, a2, , ak

а) Подходящий пример дает последовательность из n подряд идущих блоков (1, 2, 3, , n); i-ю цифру хоть какой перестановки можно брать из i-го блока.
б) Выпишем n-1 раз попорядку блок (1, 2, 3, , n) и потом 1. В этой последовательности n2-n+1 членов. Проверим, что она n-универсальна. В самом деле, если в перестановке (k1, k2, , kn) хоть одна пара примыкающих чисел kj, kj+1 стоит в порядке возрастания, то их можно брать из одного блока (1, 2, 3, , n) (j-го по порядку), при этом заключительная 1 даже не пригодится. Если это не так, то перестановка совпадает с
(n, n-1, , 2, 1); тогда из j-го блока необходимо брать n-j+1, и пригодится заключительная 1.
в) Докажем утверждение методом математической индукции. Для n=1 утверждение, явно, выполнено, так как n(n+1)/2=1, и неважно какая 1-универсальная последовательность должна содержать, по наименьшей мере, 1 член.
Пусть теперь утверждение выполнено для всех естественных чисел, наименьших n. Осмотрим произвольную n-универсальную последовательность. Отметим для каждого числа k (от 1 до n) первое его вхождение в нее. Одно из отмеченных чисел встречается на n-ом месте от начала или даже далее. Пусть для определенности таким числом будет n. Перед ним стоит по крайней мере n-1 чисел. После него стоит последовательность, которая должна быть (n-1)-универсальной для перестановок чисел 1, 2, , n-1. По индуктивному предположению ее длина не меньше, чем
(n-1)((n-1)+1)/2=n(n-1)/2. Потому длина рассматриваемой n-универсальной последовательности не меньше, чем
n+n(n-1)/2=n(n+1)/2. Ввиду произвольности рассматриваемой последовательности, утверждение доказано.