Олимпиадная задача по теории чисел: максимальная длина совпадения последовательностей
Задача
Периоды двух последовательностей – 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.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь