Дано натуральное число n. Последовательность натуральных чисел a1, a2, …, ak (k≥n) назовем n-универсальной, если из нее можно получить
Вопрос пользователя
Дано натуральное число n. Последовательность натуральных чисел a1, a2, …, ak (k≥n) назовем n-универсальной, если из нее можно получить вычеркиванием членов любую перестановку чисел 1, 2, …, n (т.е. любую последовательность из n чисел, в которую каждое из чисел 1, 2, …, n входит по одному разу). Например, последовательность (1, 2, 3, 1, 2, 1, 3) является 3-универсальной, а (1, 2, 3, 2, 1, 3, 1) не 3-универсальна, так как из нее никаким вычеркиванием нельзя получить перестановку (3, 1, 2).
а) Приведите пример n-универсальной последовательности из n2 членов.
б) Приведите пример n-универсальной последовательности из n2-n+1 членов.
в) Докажите, что любая n-универсальная последовательность состоит не менее чем из n(n+1)/2 членов.
Ответ эксперта
а) Нужный пример дает последовательность из 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. Ввиду произвольности рассматриваемой последовательности, утверждение доказано.
