Содержание

ММ38

Конкурсная задача ММ8 (3 балла)

Обозначим через f(n) количество последовательностей длины n из нулей, единиц и двоек таких, что никакие две единицы и никакие две двойки не могут стоять в них подряд. Найти явную формулу для f(n).

Решение

Обозначим F_0(n) количество таких последовательностей, оканчивающихся на 0, F_1(n) - оканчивающихся на 1, F_2(n) - оканчивающихся на 2.
Тогда f(n)=F_0(n)+F_1(n)+F_2(n).
Так как к любой последовательности можно приписать 0, не нарушив условий задачи, то F_0(n+1)= f(n) = F_0(n) + F_1(n) + F_2(n).

Так как 1 можно приписать только к последовательности, оканчивающейся на 0 или 2, то F_1(n+1) = F_0(n) + F_2(n).
Аналогично F_2(n+1) = F_0(n) + F_1(n).

Складывая, получаем:
f(n+1) = F_0(n+1) + F_1(n+1) + F_2(n+1) = 3*F_0(n) + 2*F_1(n) + 2*F_2(n) = 2f(n) + f(n-1).

Очевидно, что f(1) = 3 и f(2) = 7.
Таким образом, имеем следующую рекуррентное уравнение: f(n+1) = 2f(n) + f(n-1) при n > 2, f(1) = 3, f(2) = 7.
Характеристическое уравнение для полученного линейного рекуррентного соотношения второго порядка имеет вид x^2 - 2x - 1 = 0.
Корни характеристического уравнения: x_1 = 1 + sqrt{2}, x_2 = 1 - sqrt{2}, а общее решение - f(n) =C_1{x_1}^n + C_2{x_2}^n.

Учитывая начальные условия, находим:
C_1 = {1 + sqrt{2}}/2, C_2 = {1 - sqrt{2}}/2.

Окончательно имеем: f(n-1) = {{(1 + sqrt{2})}^n + {(1 - sqrt{2})}^n}/2.

Обсуждение

Последовательность, описная в обсуждаемой задаче, состоит из числителей наилучших рациональных приближений числа sqrt{2}.
С рядом других ситуаций, в которых возникает f(n), можно познакомиться в онлайн-энциклопедии математических последовательностей. Наша f(n) представлена там под номером A001333.

Награды

За правильное решение этой задачи Влад Франк, Мигель Митрофанов и Иван Козначеев получают по 3 призовых балла.