ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98246
Темы:    [ Периодичность и непериодичность ]
[ Деление с остатком ]
[ НОД и НОК. Взаимная простота ]
[ Алгоритм Евклида ]
[ Индукция (прочее) ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

  Пусть  L(m, n)  – искомая длина и  n = qm + r.  Докажем, что  L(m, n) = L(r, m) + n – r.
  Действительно, если есть две последовательности с периодами m и r с общим начальным куском длины l, то, в силу равенства
ai+n = ai+qm+r = ai+r = ai  (i + r < l),  начальный кусок первой последовательности длины  l + n – r  имеет также период n.
  Наоборот, если есть две последовательности длины m и n с общим куском длины L, то в силу того же равенства, начальный кусок первой последовательности длины  L – n + r  имеет период r.
  Доказанное равенство даёт возможность индукцией по алгоритму Евклида получить  L(m, n) = m + n – 2  (база  L(1, k) = k – 1  тривиальна).


Ответ

m + n – 2.

Замечания

6 баллов

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .