Назад
Задача

Дан ряд чисел: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ..., в котором каждое число, начиная с третьего, равно сумме двух предыдущих. Найдётся ли среди первых  108+ 1  членов этого ряда число, оканчивающееся четырьмя нулями?

Решение

Да, найдётся. Заменим каждое из данных чисел его остатком от деления на 10000. Пустьa1= 0,a2, ...— полученные в результате числа. Если нам известны числаakиak + 1, то нам известно иak - 1, поскольку в исходной последовательности (k- 1)-й член равен разности (k+ 1)-го иk-го. Следовательно, если для некоторыхkиnимеют место равенстваak=ak + nиak + 1=ak + n + 1, то тогдаak - 1=ak + n - 1,ak - 2=ak + n - 2, ...,a1=an + 1. Ноa1= 0, поэтомуan + 1= 0, т.е. в исходной последовательности чисел на (n+ 1)-м месте стоит число, оканчивающееся четырьмя нулями.

Остаётся доказать, что среди пар (a1,a2), (a2,a3), ...,(a108,a108 + 1),(a108 + 1,a108 + 2) найдутся две одинаковые пары. Но из чисел 0, 1, 2, ..., 9999 нельзя составить более 108различных пар, а мы рассматриваем 108+ 1 пар.

Ответ

Да, найдётся.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет