Дано натуральное число n. Последовательность натуральных чисел a1, a2, …, ak (k≥n) назовем n-универсальной, если из нее можно получить

Постоянный пользователь нашего ресурса написал нам почту в 17:8 с просьбой предоставить развернутый ответ на его вопрос. Наши эксперты отнесли этот вопрос к разделу Разное. Для ответа был привлечен один из опытных специалистов, который занимается написанием студенческих работ.

Цитируем вопрос ваш вопрос

Дано натуральное число n. Последовательность натуральных чисел a1, a2, …, ak (k≥n) назовем n-универсальной, если из нее можно получить

Разбор вопроса и ответ на него

Раздел 'ЕГЭ (школьный)', к которому был отнесён этот вопрос является не простой рубрикой. Для подготовки ответа на вопросы из этой рубрики специалист должен обладать широкими познаниями в различных научных областях. Однако в нашей компании таковые имеются.

Вы спрашивали:

Дано натуральное число n. Последовательность натуральных чисел a1, a2, …, ak (k≥n) назовем n-универсальной, если из нее можно получить

Конечно этот ответ может полностью не раскрыть тему вопроса, но мы постарались сделать его максимально полным. Предлагаем ознакомиться с мнением эксперта по этой теме:

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

К нам на почту приходит много вопросов. Мы стараемся отвечать на все. Однако вы должны понимать, что большая загруженность увеличивает время ответа. Сейчас среднее время ответа равно 14:2.