Разделы 
Дополнительно
Задача по математике - 3214
2019-05-27 
Для какого наибольшего $n$ можно придумать две бесконечные в обе стороны последовательности $A$ и $B$ такие, что любой кусок последовательности $B$ длиной $n$ содержится в $A$, $A$ имеет период 1995, а $B$ этим свойством не обладает (непериодична или имеет период другой длины)?
Комментарий. Последовательности могут состоять из произвольных символов. Речь идет о минимальном периоде.
Решение:
Пример, когда период последовательности $A$ состоит из одной единицы и 1994 нулей, а $B$ - непериодическая последовательность из нулей и единиц, в которой все единицы расположены на расстоянии, не меньшем 1994 друг от друга, показывает, что условие совпадения всех кусков длины 1994 не является достаточным для периодичности $B$.
Докажем, что если любой кусок длины 1995 последовательности $B$ содержится в $A$, то последовательность $B$ периодична с периодом длины 1995.
Докажем сначала, что 1995 - длина одного из периодов. Пусть это не так, тогда в последовательности $B$ найдется кусок длины 1996, у которого первый и последний символы не совпадают:
$B = \cdots x \underbrace{ \cdots \cdots \cdots}_{1994 \: символа}y \cdots$,
где $x$ и $y$ - разные символы. Обозначим участок последовательности между $x$ и $y$ через $Z$. Пусть символ $x$ встречается в $Z$ ровно $k$ раз. Рассмотрим две последовательности длины 1995: $xZ$ и $Zy$. По предположению, каждая из них встречается в последовательности $A$, значит, каждая из них совпадает со сдвинутым периодом последовательности $A$. Поэтому символ $x$ должен встречаться в каждой из этих последовательностей одинаковое число раз. С другой стороны, в последовательности $xZ$ он встречается $k+1$ раз, а в последовательности $Zy-k$ раз. Противоречие.
Осталось доказать, что 1995 - длина минимального периода. Если бы длина периода последовательности $B$ была меньше, чем 1995, то некоторый кусок последовательности $B$ длины 1995 распадался бы на несколько одинаковых кусков. По условию этот кусок содержится в $A$. Ясно, что в этом случае длина (минимального) периода последовательности $A$ также была бы меньше, чем 1995.
Ответ: 1994.
Для какого наибольшего $n$ можно придумать две бесконечные в обе стороны последовательности $A$ и $B$ такие, что любой кусок последовательности $B$ длиной $n$ содержится в $A$, $A$ имеет период 1995, а $B$ этим свойством не обладает (непериодична или имеет период другой длины)?
Комментарий. Последовательности могут состоять из произвольных символов. Речь идет о минимальном периоде.
Решение:
Пример, когда период последовательности $A$ состоит из одной единицы и 1994 нулей, а $B$ - непериодическая последовательность из нулей и единиц, в которой все единицы расположены на расстоянии, не меньшем 1994 друг от друга, показывает, что условие совпадения всех кусков длины 1994 не является достаточным для периодичности $B$.
Докажем, что если любой кусок длины 1995 последовательности $B$ содержится в $A$, то последовательность $B$ периодична с периодом длины 1995.
Докажем сначала, что 1995 - длина одного из периодов. Пусть это не так, тогда в последовательности $B$ найдется кусок длины 1996, у которого первый и последний символы не совпадают:
$B = \cdots x \underbrace{ \cdots \cdots \cdots}_{1994 \: символа}y \cdots$,
где $x$ и $y$ - разные символы. Обозначим участок последовательности между $x$ и $y$ через $Z$. Пусть символ $x$ встречается в $Z$ ровно $k$ раз. Рассмотрим две последовательности длины 1995: $xZ$ и $Zy$. По предположению, каждая из них встречается в последовательности $A$, значит, каждая из них совпадает со сдвинутым периодом последовательности $A$. Поэтому символ $x$ должен встречаться в каждой из этих последовательностей одинаковое число раз. С другой стороны, в последовательности $xZ$ он встречается $k+1$ раз, а в последовательности $Zy-k$ раз. Противоречие.
Осталось доказать, что 1995 - длина минимального периода. Если бы длина периода последовательности $B$ была меньше, чем 1995, то некоторый кусок последовательности $B$ длины 1995 распадался бы на несколько одинаковых кусков. По условию этот кусок содержится в $A$. Ясно, что в этом случае длина (минимального) периода последовательности $A$ также была бы меньше, чем 1995.
Ответ: 1994.
