Question

Уисполнителя тритон две команды, которым присвоены номера: 1. прибавь 2, 2. умножь на 3. первая из них увеличивает на 2 число на экране, вторая умножает это число на 3. программа для тритона — это последовательность команд. сколько существует программ, которые число 1 преобразуют в число 59?

Answer 1

Составим таблицу (см. прикреплённый рисунок):

«Число» - чисел от 1 до 59;

«Источник» - числа, из которых можно получить текущее число;

количество которыми можно получить текущее число из чисел-источников.  

Тритон никак не сможет получить чётное число из 1, поэтому в первый столбец таблицы запишем все нечётные числа от 1 до 59. Далее заполняем 2-й и 3-й столбцы.

Число 3 можно получить из 1 двумя Команда1 и Команда2. Итого

Число 5 можно получить из 3 одним Команда1. Но поскольку 3 мы получили двумя то всего число 5 мы тоже можем получить

1 + 2 = 3 + 2 = 5

1 * 3 = 3 + 2 = 5

Аналогично для числа 7.

Число 9 можно получить из двух источников:  

7 + 2 = 9

3 * 3 = 9

Соответственно, количество для 9 равно сумме для 7 и для 3 (2+2=4).

Заполнив таблицу до конца, получим для числя 59.