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

Последовательность перестановок

Каждое число вида xn=1+2+3+…+n, n ∈ N, заменим последней цифрой sn в его десятичной записи. Из последовательности s1,s2,s3,... выпишем единицу и следующие за ней цифры до тех пор, пока не встретится уже выписанная цифра. Если при этом окажется, что выписаны не все десять цифр, то все отсутствующие допишем в порядке возрастания. Полученный отрезок из 10 различных цифр назовем перестановкой. Обозначим перестановку символом pk, если ее первая цифра является k-ой по счету единицей в последовательности s1,s2,s3,...

    а) Докажите, что цифровая последовательность s1,s2,s3,... является периодической, и найдите ее наименьший период.
    б) Докажите, что последовательность перестановок p1,p2,p3,... является периодической, и найдите ее наименьший период.

  • Решение

    • Решение

    Пусть T - период последовательности sn; тогда разность xn +T - xn должна делиться на 10 при любых натуральных n. Имеем


    xn+T - xn= (n+T)(n+T+1)
    2
    		 - n(n+1)
    2
    		 = T(T+2n+1)
    2
    		 .

    Ясно, что T=20 является периодом. Докажем, что любой другой период не меньше, чем 20. При n=1 находим

    x1 + T - x1 = T(T + 3)
    2
    		 .

    Правая часть делится на 10 при T = 5, 12, 17. Однако при этих значениях T разность

    x2+T - x2= T(T+5)
    2

    на 10 не делится. Следовательно, T = 20 - наименьший период последовательности.

    Используя соотношение xn = xn-1 + n, находим члены последовательности sn:

    1,3,6,0, 5,1,8,6,5,5,6,8,1,5,0,6,3,1,0,0,1,3,6,0,5,...

    Искомые подстановки имеют вид

    p1 = (1360524789),    p2 = (1865023479),    p3 = (1506324789),
    p4 =(1023456789),    p5 = p1,    p6= p2.

    Наименьший период последовательности pn равен 4.

  • Ответ

    • Ответ

    a) 20; б) 4.