85268 (Сопряжённые числа), страница 2
Описание файла
Документ из архива "Сопряжённые числа", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "математика" в общих файлах.
Онлайн просмотр документа "85268"
Текст 2 страницы из документа "85268"
Перемножив два последних равенства, получим
| x | 2 n | – 2y | 2 n | = (–1)n, |
и интересующее нас выражение попеременно равно то 1, то –1. Складывая и вычитая эти же два равенства, мы получим явное выражение для xn и yn:
| xn = | (1 + √2)n + (1 – √2)n 2 | , |
| yn = | (1 + √2)n – (1 – √2)n 2√2 | . |
Можно ли в решении этой задачи про целые числа обойтись без иррациональных чисел 1 + √2 и 1 – √2? Теперь, зная ответ, мы можем легко выразить (xn+1; yn+1) через предыдущую пару (xn; yn): из xn+1 + yn+1√2 = (xn + yn√2)(1 + √2) вытекает
| xn+1 = xn + 2yn, yn+1 = xn + yn. | (6) |
До этого рекуррентного соотношения можно было, видимо, догадаться по нескольким первым решениям, а потом проверить, что
| | x | 2 n | – 2y | 2 n | | = | x | 2 n+1 | – 2y | 2 n+1 | | . |
Добавив начальное условие x1 = 1, y1 = 1, отсюда (по индукции) можно было бы заключить, что |xn2 – 2yn2| = 1 для любого n. Далее, выразив обратно (xn; yn): через (xn+1; yn+1), «методом спуска» ([8]) можно доказать, что найденной серией исчерпываются все решения уравнения (5) в натуральных числах (x; y). Подобным же образом решается любое «уравнение Пелля» x2 – dy2 = c (а к уравнениям такого типа сводится любое квадратное уравнение в целых числах x, y), но у исходного уравнения может быть несколько серий решений ([7]).
Рекуррентные соотношения типа (6) возникают не только в теории чисел, но и в разных задачах анализа, теории вероятностей. Вот характерный пример комбинаторной задачи такого типа (она предлагалась на последней международной олимпиаде в Лондоне):
7 (М595). В вершине A правильного восьмиугольника сидит лягушка. Из любой вершины восьмиугольника, кроме вершины E, противоположной A, она может прыгнуть в любую из двух соседних вершин. Попав в E, лягушка останавливается и остаётся там. Найти количество em различных способов, которыми лягушка может попасть из вершины A в E ровно за m прыжков.
Если раскрасить вершины восьмиугольника через одну в чёрный и белый цвет (рис. 2), сразу станет ясно, что e2k–1 = 0 при любом k: цвет вершин при каждом прыжке меняется. Обозначим через an и cn количество способов, которым лягушка может за 2n прыжков, попасть из вершины A, соответственно, в вершину A и в одну из вершин C (из соображений симметрии ясно, что в каждую из вершин, обозначенных на рисунке буквой C, можно попасть одним и тем же числом способов). Как легко проверить (см. рис.2а,б,в,г),
a1 = 2, c1 = 1;
| (7) |
А интересующее нас число e2n равно, очевидно, 2cn–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. |
Как же найти явную формулу для an и cn? Запишем наше рекуррентное соотношение (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 | , |
а так как e2n = 2cn–1, получаем окончательно
| e2n = | (2 + √2)n–1 – (2 – √2)n–1 √2 | , e2n–1 = 0. |
Задача решена. Неясно только, как в этой задаче (и в предыдущей задаче 6) можно было додуматься до формул, содержащих ±√2, — ведь в задаче речь идёт о целых числах! (Для участников олимпиады и читателей «Кванта» задача 7 была облегчена тем, что в формулировке указывался ответ — «Квант», 1979, № 11, М595).
Однако «сопряжённые числа» возникли бы совершенно автоматически, если бы мы владели началами линейной алгебры (см. [12]), и применили стандартные правила этой науки к решению уравнений (7). Эти правила предлагают сначала выяснить, какие геометрические прогрессии (an = a0λn, cn = c0λn) удовлетворяют данному рекуррентному соотношению. Значения, для которых такие прогрессии существуют, — они называются характеристическими значениями или собственными числами — определяются из некоторого уравнения (оно тоже называется характеристическим). Для (7) характеристическое уравнение имеет вид λ2 – 4λ + 2 = 0, его корни — как раз 2 + √2 и 2 – √2. Зная эти корни, любое решение рекуррентного соотношения мы можем получить как «линейную комбинацию» соответствующих геометрических прогрессий ([11]). «Начальное условие» (в нашем случае a1 = 2, c1 = 1) определяет нужное нам решение однозначно.
Неудивительно, что даже самые простые рекуррентные целочисленные последовательности, для которых характеристическое уравнение — квадратное с целыми коэффициентами (примеры — те же (6) и (7) или последовательность Фибоначчи 1, 1, 2, 3, 5, 8, ..., Fn+1 = Fn + Fn–1; см. [9], [10]), выражаются, как функции номера, с помощью «сопряжённых» квадратичных иррациональностей.
Заметим, что большее характеристическое число определяет скорость роста последовательности: при больши́х n в задаче 7 en (2 + √2)n/√2. Можно сказать это ещё так:
| en+1 en | = 2 + √2. |
Для задачи 6 аналогичное наблюдение:
| xn yn | = √2. |
Интересное продолжение этого факта мы увидим в следующей задаче с бо́льшим числом «сопряжённых» иррациональностей.
Поочерёдно меняем все знаки
8 (М520). Пусть
(1 + √2 + √3)n = qn + rn√2 + sn√3 + tn√6,
где qn, rn, sn и tn — целые числа. Найти пределы
| rn qn | , |
| sn qn | , |
| tn qn | . |
Конечно, мы здесь можем выразить (qn+1; rn+1; sn+1; tn+1) через (qn; rn; sn; tn), пользуясь тем, что
qn+1 + rn+1√2 + sn+1√3 + tn+1√6 = (1 + √2 + √3)(qn + rn√2 + sn√3 + tn√6),
но, наученные опытом, мы уже знаем, что более простые формулы получаются не для самих чисел qn, rn, sn, tn, a для некоторых их комбинаций. Одну такую комбинацию мы уже знаем: это
qn + rn√2 + sn√3 + tn√6 = (1 + √2 + √3)n.
Нетрудно сообразить, каковы будут другие. Рассмотрим вместе с данным числом
λ1 = 1 + √2 + √3,
ещё три «сопряжённых»:
λ2 = 1 – √2 + √3, λ3 = 1 + √2 – √3, λ4 = 1 – √2 – √3.
Тогда
qn – rn√2 + sn√3 – tn√6 = λ2n,
qn + rn√2 – sn√3 – tn√6 = λ3n,
qn – rn√2 – sn√3 + tn√6 = λ4n.
Мы можем выразить qn, rn, sn, tn через λ1, λ2, λ3, λ4:
| qn = | λ1n + λ2n + λ3n + λ4n 4 | , | sn = | λ1n + λ2n – λ3n – λ4n 4√3 | , | |
| rn = | λ1n – λ2n + λ3n – λ4n 4√2 | , | tn = | λ1n – λ2n – λ3n + λ4n 4√6 | . |
Теперь заметим, что λ1 > |λ2|, λ1 > |λ3|, λ1 > |λ4|. Поэтому
| rn qn | = |
| 1 – (λ2/λ1)n + (λ3/λ1)n – (λ4/λ1)n 1 + (λ2/λ1)n + (λ3/λ1)n + (λ4/λ1)n | · | 1 √2 | = | 1 √2 | . |
Аналогично найдём, что
| sn qn | = | 1 √3 | и |
| tn qn | = | 1 √6 | . |
Мы говорили выше, что сопряжённые числа a ± b√d возникают часто как корни квадратного уравнения с целыми коэффициентами. В связи с последней задачей возникает такое желание:
9. Написать уравнение с целыми коэффициентами, один из корней которого равен 1 + √2 + √3.
Возникает подозрение, что вместе с этим числом λ1 уравнению с целыми коэффициентами удовлетворяют и сопряжённые, которые в решении предыдущей задачи мы обозначили λ2, λ3, λ4. Нужное уравнение можно записать так:
