а) Нужный пример дает последовательность из 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. Ввиду произвольности рассматриваемой последовательности, утверждение доказано.
б) Выпишем 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. Ввиду произвольности рассматриваемой последовательности, утверждение доказано.