У исполнителя Увеличитель две команды, которым присвоены номера:
1. Прибавь 2,
2. Увеличь цифру в старшем разряде числа на 1.
Первая из них увеличивает данное число на 2, вторая — увеличивает цифру в старшем разряде числа на 1, например, число 34 с помощью этой команды превратится в число 44. Программа для исполнителя Увеличитель — это последовательность команд.
Определите количество программ, которые число 20 преобразуют в число 44.
Будем решать поставленную задачу последовательно для чисел 20, 21, 22, . . . , 44 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 20 в число n, будем обозначать через R(n). Будем считать, что R(20) = 1. Заметим, что команда 2 для чисел, меньших 90, соответствует условию «прибавь 10». С помощью каждой из команд 1 и 2, применяя их последовательно к числам, получаемым из числа 29, можно получить только чётные числа. Числа 20, 22, . . . , 28 можно получить из предыдущего числа только с помощью команды 1. Значит, количество искомых программ для каждого из таких чисел равно количеству программ для предыдущего числа: R(i) = R(i − 2), i—чётное, 22 ≤ i ≤ 28.
Получаем R(20) = R(22) = · · · = R(28) = 1. Для чисел, больших 28 и не превосходящих 44, вариантов последней команды два: прибавь 2 и прибавь 10, то есть R(i) = R(i − 2) + R(i − 10), i — чётное, 30 ≤ i ≤ 44. Заполним соответствующую таблицу по приведённым формулам слева направо:
| 20 | 22 | 24 | 26 | 28 | 30 | 32 | 34 | 36 | 38 | 40 | 42 | 44 |
| 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 11 | 15 |
Ответ: 15