№ 2. У исполнителя Увеличитель две команды, которым присвоены номера: 1. прибавь 1; 2. умножь на 2. Первая из них увеличивает число на экране на 1, вторая умножает его на 2. Программа для Увеличителя — это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 13? Ответ обоснуйте.

Обозначим команду «прибавь 1» буквой А, а команду «умножь на 2» буквой У.

1. Последняя команда не может быть умножением на 2, поскольку 13 не делится на 2. Значит, последней командой обязательно будет А, а перед ней должно получиться 12.
2. Рассмотрим способы получить 12 из 2. Если последней командой перед получением 12 было прибавление 1, то до него нужно было получить 11. Если это было удвоение, то до него нужно было получить 6.
3. Из 2 в 6 можно прийти двумя способами: 2 → 3 → 6 и 2 → 4 → 6. Из 2 в 11 можно прийти только последовательными прибавлениями единицы.

Получаются три программы:

1. А × 9, затем А: девять раз прибавить 1, затем ещё раз прибавить 1. (Прибавить 1 десять раз.)
2. А, У, У, А: 2 → 3 → 6 → 12 → 13.
3. У, А, У, А: 2 → 4 → 6 → 12 → 13.

Здесь первая программа записана как десять команд А; две другие — отдельные последовательности команд.

Ответ: 3 программы.