Последовательность из 𝑘 целых неотрицательных чисел 𝑎1, 𝑎2, . . . , 𝑎𝑘 называется любопытной последовательностью длины 𝑘, если для каждого 𝑛 => 3 выполнено равенство 𝑎𝑛 = 𝑎𝑛−2 − 𝑎𝑛−1. Сколько существует любопытных последовательностей длины 𝑘, для которых 3 <= 𝑘 <= 10, 𝑎𝑘 = 0 и 𝑎1 <= 2023?
1 Ответ
Решение. Для любой любопытной последовательности длины 3 существует обратная последовательность длины 3, состоящая из тех же элементов, но в обратном порядке. Аналогично, имеется обратная любопытная последовательность длины 3: для любого числа a1 длины 3 найдется число a2 длины 3 такое, что an = a2 − a1. Таким образом, найдется обратная последовательность всех чисел длины 3. Рассмотрим любопытную последовательность длины k. Предположим, что она состоит из m нулей и m единиц, т. е. имеет вид 00…00…0. Тогда k = m + m − 1 и k ≤ 10. Так как m ≠ 0, то k < 10 и если m = 1, то это будет один нуль и одна единица, а если m > 1, то две единицы.