===== №68 =====

Это задача не входит в тематический конкурс.\\
Результат учитывется только в основном зачете Марафона.\\
----

** Конкурсная задача №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 балла//**
----