Задача 9. а) Найдите наибольшее шестизначное число, у которого каждая из цифр, за исключением двух первых, равна сумме двух соседей слева. б) Найдите наибольшее целое число, у которого каждая из цифр, за исключением двух первых, равна сумме двух соседей слева. (По сравнению с п. а) мы убрали ограничение, что число должно быть шестизначным.)

Обозначим цифры числа подряд \(a_1,a_2,\ldots\). Тогда для каждого \(n\geq3\) должно выполняться \(a_n=a_{n-1}+a_{n-2}\), причём каждая цифра не больше 9.

а) Чтобы число было наибольшим, первая цифра должна быть максимально возможной при допустимых следующих цифрах. Перебор допустимых начальных пар даёт наибольшую последовательность цифр \(2,1,3,4,7,\) после которой следующая цифра равна 11 и уже не является цифрой; она не подходит для шестизначного числа. Для шестизначного числа наибольшая подходящая последовательность — \(1,2,3,5,8\): шестая цифра 13 не подходит. Перебор пар с меньшей второй цифрой даёт максимум \(303369\): цифры \(3,0,3,3,6,9\) удовлетворяют правилу.

б) Наибольшего целого числа не существует. Например, последовательность цифр \(3,0,3,3,6,9\) допустима, но продолжить её нельзя: следующая цифра должна быть 15. При любом допустимом числе условие проверяется только для уже записанных цифр; такие числа имеют ограниченную длину, а максимальную длину даёт последовательность \(1,1,2,3,5,8\). Среди чисел этой длины наибольшее — 112358.

Ответ: а) 303369; б) 112358.