Архив задач олимпиады по математике и криптографии

Период при чередовании

Пусть a1, a2, a3, … и b1, b2, b3, … числовые последовательности периодов 16 и 2006 соответственно. Найдите период последовательности a1, b1, a2, b2, a3, b3, …. (Периодом последовательности x1, x2, x3, … называется наименьшее натуральное число T, такое, что для всех натуральных n верно равенство xn+T = xn ).

  • Решение

    • Решение

    Разобьём последовательность {xn} на пары (х1,х2), (х3,х4).… При записи в терминах исходных последовательностей, полученная последовательность пар имеет вид

    (a1,b1), (a2,b2), ….

    Период этой последовательности пар равен c=НОК(16,2006)=16048, так как равенство пар означает равенство их первых и равенство их вторых элементов. Поэтому, при всех натуральных n верно равенство

    xn=xn+2с

    Покажем, что 2с – наименьшее число с таким условием.

    Пусть период последовательности {xn} равен t. Тогда число 2c должно делиться на число t. (Повторение значений в последовательности со смещением на 2с шагов должно быть получено как несколько смещений с шагом t).

    Если t четно, t=2k, то из верных при всех натуральных m равенств

    x2m-1+t=x2m-1
    x2m+t=x2m

    Следуют равенства

    am+k=am
    bm+k=bm

    Таким образом, k делится на наименьшее общее кратное периодов исходных последовательностей. Отсюда t=2НОК(16, 2006)=32096.

    При нечетном t первая последовательность является «сдвигом» второй, что противоречит различию длин их периодов.

  • Ответ

    • Ответ

    32096