Задача 76533

Темы:    [ Числа Фибоначчи ] [ Десятичная система счисления ]

Сложность: 5 Классы: 9,10,11

Условие

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

Решение

Да, найдётся. Заменим каждое из данных чисел его остатком от деления на 10000. Пусть a₁ = 0, a₂, ...— полученные в результате числа. Если нам известны числа a_k и a_{k + 1}, то нам известно и a_{k - 1}, поскольку в исходной последовательности (k - 1)-й член равен разности (k + 1)-го и k-го. Следовательно, если для некоторых k и n имеют место равенства a_k = a_{k + n} и a_{k + 1} = a_{k + n + 1}, то тогда a_{k - 1} = a_{k + n - 1}, a_{k - 2} = a_{k + n - 2}, ..., a₁ = a_{n + 1}. Но a₁ = 0, поэтому a_{n + 1} = 0, т.е. в исходной последовательности чисел на (n + 1)-м месте стоит число, оканчивающееся четырьмя нулями. Остаётся доказать, что среди пар (a₁, a₂), (a₂, a₃), ..., (a_10⁸, a_{10⁸ + 1}), (a_{10⁸ + 1}, a_{10⁸ + 2}) найдутся две одинаковые пары. Но из чисел 0, 1, 2, ..., 9999 нельзя составить более 10⁸ различных пар, а мы рассматриваем 10⁸ + 1 пар.

Ответ

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

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	9
Год	1946
вариант
Класс	9,10
Тур	2
задача
Номер	2