Задача 98235

Темы:    [ Периодичность и непериодичность ] [ Деление с остатком ] [ Примеры и контрпримеры. Конструкции ]

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

Условие

Автор: Канель-Белов А.Я.

Периоды двух последовательностей – 7 и 13. Какова максимальная длина начального куска, который может у них совпадать?

Решение

  Пример. Рассмотрим последовательность с периодом 7 и начальными членами  0, 0, 0, 0, 0, 1, 0  и последовательность с периодом 13 и начальными членами  0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1.  У них есть общий начальный кусок  0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0  длины 18.

  Оценка. Если есть общий начальный кусок длины 19, то  a₇ = a₁₄ = a₁ = a₁₅ = a₂ = a₁₆ = a₃ = a₁₇ = a₄ = a₁₈ = a₅ = a₁₉ = a₆,  то есть период первой последовательности не 7, а 1. Противоречие.

Ответ

18.

Замечания

1. 6 баллов.

2. См. также задачу 98246.

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

олимпиада
Название	Турнир городов
Турнир
Номер	16
Дата	1994/1995
вариант
Вариант	осенний тур, основной вариант, 8-9 класс
Задача
Номер	5