Задача 67490
|
|
 |
Условие
Даны две строго возрастающие последовательности положительных чисел, в которых каждый член, начиная с третьего, равен сумме двух предыдущих. Известно, что каждая последовательность содержит хотя бы одно число, которого нет в другой последовательности. Какое наибольшее количество общих чисел может быть у этих последовательностей?Замечание к условию. Предполагается, что обе последовательности бесконечны, иначе совпадений, очевидно, может быть сколько угодно (можно взять первые $n$ членов последовательности Фибоначчи 1, 2, 3, 5, 8, 13, ... как первую последовательность, и члены со второго по $(n+1)$-й — как вторую).
Решение
Правило построения последовательностей назовём просто правилом. Пусть два совпадения в последовательностях нашлись, рассмотрим второе. Если предыдущие члены тоже равны, то по правилу одна из последовательностей содержится в другой (так как они бесконечны), что запрещено. Пусть они не равны. Будем считать, что последовательности начинаются с них, и докажем, что теперь совпадение ровно одно. Итак, первая последовательность — $a_1, a_2, \ldots$, вторая — $b_1, b_2, \ldots$, причём $$a_1 < b_1 < a_2 = b_2 < a_3.$$Складывая первое и третье сравнения, получаем, что $a_1+a_2 < b_1+b_2$, то есть, по правилу, $a_3 < b_3$. Складывая второе и четвёртое сравнения, получаем, что $b_1+b_2 < a_2+a_3$, то есть, по правилу, $b_3 < a_4$.
Действуя далее аналогично, получаем, что $a_n < b_n$ для каждого $n > 2$ и $b_n < a_{n+1}$ для всех натуральных $n$. Значит, далее совпадений не будет, поскольку последовательности идут так: $$ a_1 < b_1 < a_2 = b_2 < a_3 < b_3 < a_4 < b_4 < a_5 < \ldots$$
Пример. 1, 2, 3, 5, … и 1, 3, 4, ….
Ответ
2.Замечания
1. Рассматривать второе (а не первое) совпадающее число требуется лишь для того, чтобы в обеих последовательностях оно было не первым членом. Поэтому если первый член каждой последовательности не содержится в другой, то у последовательностей не более одного общего числа.2. Если последовательности не обязательно строго возрастают, совпадений может быть три: например, для последовательностей 1, 2, 3, 5, 8, ... и 2, 1, 3, 4, 7, ...
