Разделы 
Дополнительно
Задача по математике - 2900
2019-05-06 
Найдется ли среди 100 000 001 первых чисел Фибоначчи (см. задачу 2897) число, оканчивающееся четырьмя нулями?
Решение:
Оставим в каждом члене ряда Фибоначчи, записывающемся пятью и более цифрами, только последние четыре цифры. У нас получится последовательность чисел, каждое из которых меньше чем $10^4$. Обозначим через $a_k$ член этой последовательности, стоящий на $k$-м месте. Заметим, что если нам известно $a_{k+1}$ и $a_k$, то мы можем вычислить $a_{k-1}$, ибо $(k-1)$-й член ряда Фибоначчи равен разности $(k+1)$-го и $k$-гo членов, а последние четыре цифры разности можно определить по последним четырем цифрам уменьшаемого и вычитаемого. Отсюда следует, что если для некоторых номеров $k$ и $n$ окажется, что $a_k = a_{n+k}$, $a_{k+1} = a_{n+k+1}$ то тогда $a_{k-1} = a_{n+k-1}, a_{k-2} = a_{n+k-2}, \cdots, a_1 = a_{n+1}$. Но так как $a_1 = 0$, то это будет означать, что $a_{n+1} = 0$, т. е. что в ряде Фибоначчи на $(n+1)$-м месте стоит число, оканчивающееся четырьмя нулями.
Остается показать, что среди $10^8 + 1$ пар
$\begin{matrix} a_1, a_2 \\ a_2, a_3 \\ \cdots \\ a_{10^8}, a_{10^8 + 1} \\ a_{10^8 + 1}, a_{10^8 + 2} \end{matrix}$
найдутся хотя бы две одинаковые. Но это непременно будет так, ибо все числа $a_1, a_2, a_3, \cdots, a_{10^8 + 2}$ не превышают $10^4$, а из $10^4$ чисел $0, 1, 2, 3, 4, \cdots, 9999$ можно составить только $10^4$ различных пар (ибо первое число может принимать $10^4$ различных значений и второе число может принимать $10^4$ различных значений).
Найдется ли среди 100 000 001 первых чисел Фибоначчи (см. задачу 2897) число, оканчивающееся четырьмя нулями?
Решение:
Оставим в каждом члене ряда Фибоначчи, записывающемся пятью и более цифрами, только последние четыре цифры. У нас получится последовательность чисел, каждое из которых меньше чем $10^4$. Обозначим через $a_k$ член этой последовательности, стоящий на $k$-м месте. Заметим, что если нам известно $a_{k+1}$ и $a_k$, то мы можем вычислить $a_{k-1}$, ибо $(k-1)$-й член ряда Фибоначчи равен разности $(k+1)$-го и $k$-гo членов, а последние четыре цифры разности можно определить по последним четырем цифрам уменьшаемого и вычитаемого. Отсюда следует, что если для некоторых номеров $k$ и $n$ окажется, что $a_k = a_{n+k}$, $a_{k+1} = a_{n+k+1}$ то тогда $a_{k-1} = a_{n+k-1}, a_{k-2} = a_{n+k-2}, \cdots, a_1 = a_{n+1}$. Но так как $a_1 = 0$, то это будет означать, что $a_{n+1} = 0$, т. е. что в ряде Фибоначчи на $(n+1)$-м месте стоит число, оканчивающееся четырьмя нулями.
Остается показать, что среди $10^8 + 1$ пар
$\begin{matrix} a_1, a_2 \\ a_2, a_3 \\ \cdots \\ a_{10^8}, a_{10^8 + 1} \\ a_{10^8 + 1}, a_{10^8 + 2} \end{matrix}$
найдутся хотя бы две одинаковые. Но это непременно будет так, ибо все числа $a_1, a_2, a_3, \cdots, a_{10^8 + 2}$ не превышают $10^4$, а из $10^4$ чисел $0, 1, 2, 3, 4, \cdots, 9999$ можно составить только $10^4$ различных пар (ибо первое число может принимать $10^4$ различных значений и второе число может принимать $10^4$ различных значений).
