№ 3. У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1; 2. умножь на 3. (Например, программа 21211 преобразует число 1 в 14.) Запишите порядок команд в программе получения из числа 2 числа 99, содержащей наименьшее количество команд.

Чтобы найти короткую программу, пойдём от 99 назад: если число делится на 3, делим его на 3; иначе вычитаем 1. Обратные действия соответствуют командам умножения на 3 и прибавления 1.

1. 99 делится на 3: получаем 33.
2. 33 делится на 3: получаем 11.
3. 11 не делится на 3: получаем 10, затем 9.
4. 9 делится на 3: получаем 3, затем 1.

Для пути от 2 до 99 последние обратные шаги дают: 2 → 3 → 9 → 10 → 11 → 33 → 99. Это команды 1, 2, 1, 1, 2, 2. Кратчайшесть подтверждается обратным поиском: на каждом шаге при делимости на 3 деление сокращает число одним действием, а при неделимости единственный обратный шаг — вычитание 1.

Ответ: 121122.