Это задача не входит в тематический конкурс.
Результат учитывется только в основном зачете Марафона.
Конкурсная задача №68 (5 баллов)
1. Доказать, что для любого натурального n найдется натуральное k такое, что
числа Фибоначчи F(k), F(k+1), …, F(k+n-1) являются составными.
2. Какое наибольшее количество простых чисел может встретиться среди десяти
идущих подряд чисел Фибоначчи?
Примечания:
1. Рекуррентое определение чисел Фибоначчи:
F(1) = F(2) = 1, F(n+1) = F(n) + F(n-1) при n > 2.
2. Напомню, что 1 не является ни простым, ни составным числом.
Решение
Лемма 1: F(m) = F(m-1) + F(m-2) = F(t+1)*F(m-t) + F(t)*F(m-t-1)
Доказательство.
F(m) = F(m-1) + F(m-2) = 2*F(m-2) +F(m-3) = 3*F(m-3) + 2*F(m-4) = …
= F(t+1)*F(m-t) + F(t)*F(m-t-1)
Лемма 2: F(n*s) кратно F(n)
Докажем эту лемму индукцией по s.
При s = 1 утверждение леммы очевидно.
Пусть F(n*s) кратно F(n) для некоторого s.
Подставив в тождество из леммы 1 (s+1)*n вместо m и n вместо t, получим:
F(n*(s+1)) = F(n+1)*F(s*n) + F(n)*F(s*n-1)). Учитывая что F(s*n) кратно F(n),
получим, что и F((s+1)*n) кратно F(n).
1. На основании леммы 2 числа F((n+1)!+2), F((n+1)!+3),…, F((n+1)!+n+1) являются составными при n>1.
2. Ответ - 5.
Среди десяти идущих подряд чисел Фибоначчи пять имеют четные номера.
Поэтому на основании леммы 2 при n>4 среди чисел F(n), F(n+1), …, F(n+9) не
может быть более пяти простых.
Рассматривая десятки идущих подряд чисел Фибоначчи, начинающиеся с F(1), F(2),
F(3) и F(4), выясняем, что больше 5 простых чисел не встречается и в этих
десятках. В то же время, в десятках F(2), …, F(11) и F(3), …, F(12)
обнаруживаем пятерку простых чисел 2, 3, 5, 13, 89, а в десятке
F(4), …, F(13) - пятерку 3, 5, 13, 89, 233.
Обсуждение
Начиная с 5, среди номеров десяти идущих подряд чисел Фибоначчи не может быть более 4 простых (остальные номера оканчиваются четной цифрой или пятеркой). Поэтому приведенными в решении пятерками исчерпываются все пятерки простых чисел, встречающиеся среди десяти идущих подряд чисел Фибоначчи.
На основании леммы 2 можно убедиться, что в каждой десятке идущих подряд чисел Фибоначчи встречается не менее: 3 четных чисел; двух чисел, кратных 3; двух чисел, кратных 5; одного числа, кратного 13; одного числа, кратного 7; одного числа, кратного 17; одного числа, кратного 11.
Награды
За правильное решение этой задачи Сергей Аракчеев, Андрей Бежан, Сергей Беляев, Евгений Машеров, Олег Полубасов, Виктор Филимоненков и Влад Франк получают по 5 призовых баллов.
Эстетическая оценка задачи - 3.2 балла