Обозначим за F(n) количество n-значных чисел, состоящих из двоек и пятёрок, у которых никакие две двойки не стоят рядом. Рассмотрим F(n+2). Как можно построить (n+2)-значное число, обладающее указанным свойством? Можно взять (n+1)-значное число с таким свойством и приписать к нему пятерку (!) или взять (n+1)-значное число с таким свойством, не оканчивающееся на двойку, и приписать к нему двойку () ровно F(n). Тогда F(n+2) = F(n+1) + F(n). Так как F(1) = 2, F(2) = 3, то F(n) на самом деле (n+1)-е число Фибоначчи, тогда F(10) = 89.
Примечания. 1) Последовательность Фибоначчи задаётся соотношением Первые члены последовательности Фибоначчи (начиная с нулевого): 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … 2) Почему чисел со свойством (!!) ровно F(n). Понятно, что пятерку можно приписать к любому числу с заданным свойством, т.е. если X - n-значное число с нужным свойством, то 10X+5 - (n+1)-значное число с нужным свойством. И наоборот, если 10X+5 - (n+1)-значное число с нужным свойством, то X - n-значное число с нужным свойством. Поэтому число (n+1)-значных чисел с нужным свойством, оканчивающихся на 5, равно числу n-значных чисел с нужным свойством.
Рассмотрим F(n+2). Как можно построить (n+2)-значное число, обладающее указанным свойством? Можно взять (n+1)-значное число с таким свойством и приписать к нему пятерку (!) или взять (n+1)-значное число с таким свойством, не оканчивающееся на двойку, и приписать к нему двойку () ровно F(n). Тогда F(n+2) = F(n+1) + F(n). Так как F(1) = 2, F(2) = 3, то F(n) на самом деле (n+1)-е число Фибоначчи, тогда F(10) = 89.
Примечания.
1) Последовательность Фибоначчи задаётся соотношением
Первые члены последовательности Фибоначчи (начиная с нулевого):
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …
2) Почему чисел со свойством (!!) ровно F(n). Понятно, что пятерку можно приписать к любому числу с заданным свойством, т.е. если X - n-значное число с нужным свойством, то 10X+5 - (n+1)-значное число с нужным свойством. И наоборот, если 10X+5 - (n+1)-значное число с нужным свойством, то X - n-значное число с нужным свойством. Поэтому число (n+1)-значных чисел с нужным свойством, оканчивающихся на 5, равно числу n-значных чисел с нужным свойством.