Задача 107794

Тема:    [ Периодичность и непериодичность ]

Сложность: 5- Классы: 8,9,10,11

Условие

Авторы: Канель-Белов А.Я., Галочкин А.И.

Для какого наибольшего n можно придумать две бесконечные в обе стороны последовательности A и B такие, что любой кусок последовательности B длиной n содержится в A, A имеет период 1995, а B этим свойством не обладает (непериодична или имеет период другой длины)?

Комментарий. Последовательности могут состоять из произвольных символов. Речь идет о минимальном периоде.

Решение

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

Докажем, что если любой кусок длины 1995 последовательности B содержится в A, то последовательность B периодична с периодом длины 1995.

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

B = ...xy...,

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

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	58
Год	1995
вариант
Класс	11
задача
Номер	5