Олимпиадная задача по последовательностям: периодические и непериодические последовательности

  Пример, когда период последовательностиAсостоит из одной единицы и 1994 нулей, аB — непериодическая последовательность из нулей и единиц, в которой все единицы расположены на расстоянии, не меньшем 1994 друг от друга, показывает, что условие совпадения всех кусков длины 1994 не является достаточным для периодичностиB. Докажем, что если любой кусок длины 1995 последовательности B содержится в A, то последовательность B периодична с периодом длины 1995.

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

где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.

Комментарий. Из доказательства следует, что если n — длина минимального периода последовательности, то любые два одинаковых куска длины n - 1 находятся на расстоянии, кратном n.

Ответ задачи отсутствует