У исполнителя «Вычислитель» есть две команды: 1. Прибавить 2. 2. Умножить на 4. Сколько существует различных программ, позволяющих преобразовать число 2 в число 20?

Рассмотрим возможные последние команды. Если последней была команда «Прибавить 2», перед ней должно было получиться 18. Если последней была команда «Умножить на 4», перед ней должно было получиться 5, но число 5 из 2 получить нельзя: обе команды сохраняют чётность.

До числа 18 можно дойти тремя способами:

1. Прибавить 2 девять раз: 2 → 4 → 6 → 8 → 10 → 12 → 14 → 16 → 18 → 20.
2. Умножить 2 на 4, затем прибавить 2 шесть раз: 2 → 8 → 10 → 12 → 14 → 16 → 18 → 20.
3. Прибавить 2, умножить результат на 4, затем прибавить 2 два раза: 2 → 4 → 16 → 18 → 20.

Ответ: 3.