Статья: Сопряжённые числа

7. В вершине A правильного восьмиугольника сидит лягушка. Из любой вершины восьмиугольника, кроме вершины E, противоположной A, она может прыгнуть в любую из двух соседних вершин. Попав в E, лягушка останавливается и остаётся там. Найти количество e_m различных способов, которыми лягушка может попасть из вершины A в E ровно за m прыжков.

Если раскрасить вершины восьмиугольника через одну в чёрный и белый цвет (рис.2), сразу станет ясно, что e_2k–1 = 0 при любом k: цвет вершин при каждом прыжке меняется. Обозначим через a_n и c_n количество способов, которым лягушка может за 2n прыжков, попасть из вершины A, соответственно, в вершину A и в одну из вершин C (из соображений симметрии ясно, что в каждую из вершин, обозначенных на рисунке буквой C, можно попасть одним и тем же числом способов). Как легко проверить (см. рис.2а,б,в,г),

a₁ = 2, c₁ = 1;

 an+1 = 2an + 2cn ,   cn+1 = an + 2cn .

(7)

А интересующее нас число e_2n равно, очевидно, 2c_n–1 (рис. 2д).

а) c1 = 1

б) a1 = 2

в) an+1 = 2an + 2cn

г) cn+1 = an + 2cn

д) e2n = 2cn–1

Рис. 2. а)	Из A в C за два прыжка можно попасть только одним способом: c1 = 1.
б)	Из A в A за два прыжка можно попасть двумя способами: a1 = 2.
в)	В A можно попасть из C двумя способами и из A двумя способами: an+1 = 2an + 2cn .
г)	В C можно попасть из A одним способом и из C — двумя: cn+1 = an + 2cn .
д)	В E можно попасть из C двумя способами: e2n = 2cn–1 .

Как же найти явную формулу для a_n и c_n ? Запишем наше рекуррентное соотношение (7) так:

an+1 + cn+1 √2 = (an + cn √2)(2 + √2)

(8)

и — как вы уже, конечно, догадались — ещё так:

an+1 – cn+1 √2 = (an – cn √2)(2 – √2).

(9)

Отсюда по индукции, пользуясь (7), получаем:

an + cn √2 = (2 + √2)n–1 (a1 + c1 √2) = (2 + √2)n ,

an – cn √2 = (2 – √2)n–1 (a1 – c1 √2) = (2 – √2)n .

Поэтому

cn =

(2 + √2)n – (2 – √2)n 2√2

,

а так как e_2n = 2c_n–1 , получаем окончательно

e2n =

(2 + √2)n–1 – (2 – √2)n–1 √2

, e2n–1 = 0.

Задача решена. Неясно только, как в этой задаче (и в предыдущей задаче6) можно было додуматься до формул, содержащих ±√2, — ведь в задаче речь идёт о целых числах! (Для участников олимпиады и читателей «Кванта» задача7 была облегчена тем, что в формулировке указывался ответ — «Квант», 1979, №11, М595).

Однако «сопряжённые числа» возникли бы совершенно автоматически, если бы мы владели началами линейной алгебры (см.[12]), и применили стандартные правила этой науки к решению уравнений (7). Эти правила предлагают сначала выяснить, какие геометрические прогрессии (a_n = a₀ λⁿ , c_n = c₀ λⁿ ) удовлетворяют данному рекуррентному соотношению. Значения, для которых такие прогрессии существуют, — они называются характеристическими значениями или собственными числами — определяются из некоторого уравнения (оно тоже называется характеристическим). Для (7) характеристическое уравнение имеет вид λ² – 4λ + 2 = 0, его корни — как раз 2 + √2 и 2 – √2. Зная эти корни, любое решение рекуррентного соотношения мы можем получить как «линейную комбинацию» соответствующих геометрических прогрессий ([11]). «Начальное условие» (в нашем случае a₁ = 2, c₁ = 1) определяет нужное нам решение однозначно.

Неудивительно, что даже самые простые рекуррентные целочисленные последовательности, для которых характеристическое уравнение — квадратное с целыми коэффициентами (примеры — те же (6) и (7) или последовательность Фибоначчи 1, 1, 2, 3, 5, 8, ..., F_n+1 = F_n + F_n–1 ; см.[9], [10]), выражаются, как функции номера, с помощью «сопряжённых» квадратичных иррациональностей.

Заметим, что большее характеристическое число определяет скорость роста последовательности: при больши́х n в задаче7 e_n  (2 + √2)ⁿ /√2. Можно сказать это ещё так:

lim n → ∞

en+1 en

= 2 + √2.