Разделы 
Дополнительно
Задача по математике - 3752
2019-06-16 
Дано натуральное число $n$. Последовательность натуральных чисел $a_1, a_2, \cdots, a_k (k \geq n)$ назовем универсальной для данного $n$, если из нее можно получить вычеркиванием части членов любую перестановку чисел $1, 2, \cdots, n$ (т. е. любую последовательность из $n$ чисел, в которую каждое из чисел 1, 2, входит по одному разу). Например, последовательность (1, 2, 3, 1, 2, 1, 3) является универсальной для $n = 3$, а последовательность (1, 2, 3, 2, 1, 3, 1) не универсальна, так как из нее никаким вычеркиванием нельзя получить перестановку (3, 1, 2). Цель этой задачи - получить оценку числа членов самой короткой универсальной последовательности (для данного $n$).
а) Приведите пример универсальной последовательности из $n^2$ членов.
б) Приведите пример универсальной последовательности из $n^2 - n + 1$ членов.
в) Докажите, что любая универсальная последовательность состоит не менее чем из $n(n+1) /2$ членов.
г) Докажите, что при $n = 4$ самая короткая универсальная последовательность состоит из 12 членов.
д) Попробуйте найти для данного $n$ как можно более короткую универсальную последовательность. (Жюри умеет строить универсальную последовательность из $n^2 - 2n + 4$ членов.)
Решение:
Пример а) очевиден: достаточно выписать $n$ раз подряд «блок» $1 2 3 \cdots n$; $i$-ю цифру любой перестановки можно взять из $i$-го блока. В качестве примера б) годится последовательность
$\underbrace{ \underbrace{1 2 \cdots n}_{} \underbrace{1 2 \cdots n}_{} \cdots \underbrace{1 2 \cdots n}}_{n - 1} 1$.
В самом деле, если в перестановке $(k_1, k_2, \cdots, k_n)$ хоть одна пара соседних чисел $k_j, k_{j+1}$ стоит в порядке возрастания, то их можно взять из одного блока $1 2 \cdots n$ ($j$-го по порядку); при этом последняя 1 даже не понадобится. Если это не так, то перестановка обязательно совпадает с $(n, n - 1, n - 2, \cdots, 2, 1)$; тогда из $j$-го блока нужно взять $n - j$, и пригодится последняя 1.
в) Отметим для каждого числа $k$ (от 1 до $n$) первое его вхождение в универсальную последовательность. Одно из отмеченных чисел встречается на $n$-м месте от начала или даже дальше. Пусть для определенности таким числом будет $n$. Перед ним стоит по крайней мере $n - 1$ чисел. После него стоит последовательность, которая должна быть универсальной для перестановок чисел $(1, 2, \cdots, n - 1)$, и по индукции мы можем считать доказанным, что ее длина не меньше $n(n-1)/2$. Поэтому длина м-универсальной последовательности не меньше $n + \frac{ n(n - 1)}{2} = \frac{n(n + 1)}{2}$.
г) Заметим, что если число $n$ входит в $n$-универсальную последовательность лишь один раз, то до него и после него должна стоять $(n-1)$-универсальная последовательность. Это дает возможность получить более точную оценку снизу, чем в пункте в).
Пусть $l_n$ - длина минимальной $n$-универсальной последовательности. Тогда $l_2 = 3$. Докажем, что $k = 7$. Пример: 1213121 или 1231231. Если какое-то число (скажем, 3) входит в последовательность лишь один раз, то ее длина не меньше $1 + 2l_2 \leq 7$. В другом случае рассмотрим число, которое впервые встретится на 3-м месте или доз же (пусть это будет 3). За ним встретится еще раз 3, а также 2-универсальная последовательность, так что общая длина не меньше $2 + 1 + 1 + l_2 = 4 + l_2 = 7$. Аналогично убеждаемся в том, что $l_4 = 12$. Пример: 123412314231 или 412341243142. Оценки: если некоторое число входит в последовательность лишь один раз, то ее длина не меньше $1 + 2l_3 = 15$, в другом случае она не меньше $3 + 1 + 1 + l_2 = 12$.
То же рассуждение показывает, что $l_n \geq \frac{n(n+ 1)}{2} + n - 2$,
д) Можно доказать, что $n$-универсальной является такая последовательность длины $n^2 - 2n + 4$:
$n \underbrace{1 2 \cdots (n-1)n} \underbrace{1 2 \cdots (n-2)n(n-1)} \cdots \underbrace{1 2 n 3 \cdots (n-1)} 1 n 2$ (*),
где в каждый из $n - 2$ блоков $1 2 \cdots (n - 2)$ вставлено $n$ (после $n-1$, затем после $n - 2, \cdots$, наконец, после 2), кроме того, $n$ стоит в начале и в конце, имеющем вид $1 n 2$. (Так изготовлен второй пример для $n = 4$.) Для этого достаточно убедиться в том, что слева от 6-го вхождения $n$ в (*) можно вычеркиванием получить любую последовательность из $k-1$ различных чисел (среди $1, 2, n-1$), а справа-любую из $n - k$ таких чисел; дело в том, что обе эти части - левая и правая - после вычеркивания всех вхождений $n$ (правая - также после циклической перенумерации) имеют такой тип:
$\underbrace{\underbrace{ 1 2 \cdots m}_{} \underbrace{1 2 \cdots m} \cdots \underbrace{1 2 \cdots m}_{} }_{r-1 \: раз} 1 2 \cdots r$, где $r \leq m = n - 1$.
А эта последовательность обладает следующим свойством "$(m, r)$-универсальности": из нее вычеркиванием можно получить любую последовательность $r$ разных чисел (среди $1, 2, \cdots, m$).
Дано натуральное число $n$. Последовательность натуральных чисел $a_1, a_2, \cdots, a_k (k \geq n)$ назовем универсальной для данного $n$, если из нее можно получить вычеркиванием части членов любую перестановку чисел $1, 2, \cdots, n$ (т. е. любую последовательность из $n$ чисел, в которую каждое из чисел 1, 2, входит по одному разу). Например, последовательность (1, 2, 3, 1, 2, 1, 3) является универсальной для $n = 3$, а последовательность (1, 2, 3, 2, 1, 3, 1) не универсальна, так как из нее никаким вычеркиванием нельзя получить перестановку (3, 1, 2). Цель этой задачи - получить оценку числа членов самой короткой универсальной последовательности (для данного $n$).
а) Приведите пример универсальной последовательности из $n^2$ членов.
б) Приведите пример универсальной последовательности из $n^2 - n + 1$ членов.
в) Докажите, что любая универсальная последовательность состоит не менее чем из $n(n+1) /2$ членов.
г) Докажите, что при $n = 4$ самая короткая универсальная последовательность состоит из 12 членов.
д) Попробуйте найти для данного $n$ как можно более короткую универсальную последовательность. (Жюри умеет строить универсальную последовательность из $n^2 - 2n + 4$ членов.)
Решение:
Пример а) очевиден: достаточно выписать $n$ раз подряд «блок» $1 2 3 \cdots n$; $i$-ю цифру любой перестановки можно взять из $i$-го блока. В качестве примера б) годится последовательность
$\underbrace{ \underbrace{1 2 \cdots n}_{} \underbrace{1 2 \cdots n}_{} \cdots \underbrace{1 2 \cdots n}}_{n - 1} 1$.
В самом деле, если в перестановке $(k_1, k_2, \cdots, k_n)$ хоть одна пара соседних чисел $k_j, k_{j+1}$ стоит в порядке возрастания, то их можно взять из одного блока $1 2 \cdots n$ ($j$-го по порядку); при этом последняя 1 даже не понадобится. Если это не так, то перестановка обязательно совпадает с $(n, n - 1, n - 2, \cdots, 2, 1)$; тогда из $j$-го блока нужно взять $n - j$, и пригодится последняя 1.
в) Отметим для каждого числа $k$ (от 1 до $n$) первое его вхождение в универсальную последовательность. Одно из отмеченных чисел встречается на $n$-м месте от начала или даже дальше. Пусть для определенности таким числом будет $n$. Перед ним стоит по крайней мере $n - 1$ чисел. После него стоит последовательность, которая должна быть универсальной для перестановок чисел $(1, 2, \cdots, n - 1)$, и по индукции мы можем считать доказанным, что ее длина не меньше $n(n-1)/2$. Поэтому длина м-универсальной последовательности не меньше $n + \frac{ n(n - 1)}{2} = \frac{n(n + 1)}{2}$.
г) Заметим, что если число $n$ входит в $n$-универсальную последовательность лишь один раз, то до него и после него должна стоять $(n-1)$-универсальная последовательность. Это дает возможность получить более точную оценку снизу, чем в пункте в).
Пусть $l_n$ - длина минимальной $n$-универсальной последовательности. Тогда $l_2 = 3$. Докажем, что $k = 7$. Пример: 1213121 или 1231231. Если какое-то число (скажем, 3) входит в последовательность лишь один раз, то ее длина не меньше $1 + 2l_2 \leq 7$. В другом случае рассмотрим число, которое впервые встретится на 3-м месте или доз же (пусть это будет 3). За ним встретится еще раз 3, а также 2-универсальная последовательность, так что общая длина не меньше $2 + 1 + 1 + l_2 = 4 + l_2 = 7$. Аналогично убеждаемся в том, что $l_4 = 12$. Пример: 123412314231 или 412341243142. Оценки: если некоторое число входит в последовательность лишь один раз, то ее длина не меньше $1 + 2l_3 = 15$, в другом случае она не меньше $3 + 1 + 1 + l_2 = 12$.
То же рассуждение показывает, что $l_n \geq \frac{n(n+ 1)}{2} + n - 2$,
д) Можно доказать, что $n$-универсальной является такая последовательность длины $n^2 - 2n + 4$:
$n \underbrace{1 2 \cdots (n-1)n} \underbrace{1 2 \cdots (n-2)n(n-1)} \cdots \underbrace{1 2 n 3 \cdots (n-1)} 1 n 2$ (*),
где в каждый из $n - 2$ блоков $1 2 \cdots (n - 2)$ вставлено $n$ (после $n-1$, затем после $n - 2, \cdots$, наконец, после 2), кроме того, $n$ стоит в начале и в конце, имеющем вид $1 n 2$. (Так изготовлен второй пример для $n = 4$.) Для этого достаточно убедиться в том, что слева от 6-го вхождения $n$ в (*) можно вычеркиванием получить любую последовательность из $k-1$ различных чисел (среди $1, 2, n-1$), а справа-любую из $n - k$ таких чисел; дело в том, что обе эти части - левая и правая - после вычеркивания всех вхождений $n$ (правая - также после циклической перенумерации) имеют такой тип:
$\underbrace{\underbrace{ 1 2 \cdots m}_{} \underbrace{1 2 \cdots m} \cdots \underbrace{1 2 \cdots m}_{} }_{r-1 \: раз} 1 2 \cdots r$, где $r \leq m = n - 1$.
А эта последовательность обладает следующим свойством "$(m, r)$-универсальности": из нее вычеркиванием можно получить любую последовательность $r$ разных чисел (среди $1, 2, \cdots, m$).
